String Matching Algorithms

I have a python app with a database of businesses and I want to be able to searc开发者_高级运维h for businesses by name (for autocomplete purposes).

For example, consider the names "best buy", "mcdonalds", "sony" and "apple".

I would like "app" to return "apple", as well as "appel" and "ple". "Mc'donalds" should return "mcdonalds". "bst b" and "best-buy" should both return "best buy".

Which algorithm am I looking for, and does it have a python implementation?

Thanks!

The Levenshtein distance should do.

Look around - there are implementations in many languages.

Levenshtein distance will do this.

Note: this is a distance, you have to calculate it to every string in your database, which can be a big problem if you have a lot of entries.

If you have this problem then record all the typos the users make (typo=no direct match) and offline build a correction database which contains all the typo->fix mappings. some companies do this even more clever, eg: google watches how users correct their own typos and learns the mappings from this.

Soundex or Metaphone might work.

I think what you are looking for is a huge field of Data Quality and Data Cleansing. I fear if you could find a python implementation regarding this as it has to be something which cleanses considerable amount of data in db which could be of business value.

Levensthein distance goes in the right direction but only half the way. There are several tricks to get it to use the half matches as well.

One would be to use a subsequence dynamic time warping (DTW is actually a generalization of levensthein distance). For this you relax the start and end cases when calcualting the cost matrix. If you only relax one of the conditions you can get autocompletion with spell checking. I am not sure if there is a python implementation available, but if you want to implement it for yourself it should not be more than 10-20 LOC.

The other idea would be to use a Trie for speed up, which can do DTW/Levensthein on multiple results simultaniously (huge speedup if your database is large). There is a paper on Levensthein on Tries at IEEE, so you can find the algorithm there. Again for this you would need to relax the final boundary condition, so you get partial matches. However since you step down in the trie you just need to check when you have fully consumed the input and then return all leaves.

check this one http://docs.python.org/library/difflib.html it should help you