String similarity -> Levenshtein distance

string algorithm levenshtein-distance similarity
Fede Lerner picture Fede Lerner · Jul 26, 2012 · Viewed 10k times · Source

I'm using the Levenshtein algorithm to find the similarity between two strings. This is a very important part of the program I'm making, so it needs to be effective. The problem is that the algorithm doesn't find the following examples as similar:

CONAIR
AIRCON

The algorithm will give a distance of 6. So for this word of 6 letters (You look at the word with the highest amount of letters), the difference is of 100% => the similarity is 0%.

I need to find a way to find the similarities between two string, but also taking into consideration cases like the one I presented before.

Is there a better algorithm I can use? Or what do you guys recommend me?

EDIT: I've also looked into the "Damerau–Levenshtein" algorithm, which adds transpositions. The problem is that this transpositions are only for adjacent characters (and not for a number of characters).

Answer

maniek picture maniek · Jul 26, 2012

I would divide the term into unigrams, bigrams and trigrams, then calculate cosine similarity.

Related questions

String similarity metrics in Python

I want to find string similarity between two strings. This page has examples of some of them. Python has an implemnetation of Levenshtein algorithm. Is there a better algorithm, (and hopefully a python library), under these contraints. I want to …

Read More
Fuzzy search algorithm (approximate string matching algorithm)

I wish to create a fuzzy search algorithm. However, upon hours of research I am really struggling. I want to create an algorithm that performs a fuzzy search on a list of names of schools. This is what I have …

Read More
What's the best way to build a string of delimited items in Java?

While working in a Java app, I recently needed to assemble a comma-delimited list of values to pass to another web service without knowing how many elements there would be in advance. The best I could come up with off …

Read More