Take the 2-minute tour ×





I plan on implementing this into multiple languages including VB.net, Lua, and JavaScript. At this point, pseudo code is acceptable. If you can provide an example for a specific language, this is appreciated too!

share|improve this question
Algorithms that typically do this type of stuff work on determining how many changes it takes to turn an examined string into the target string. Those types of algorithms don't work well at all in a situation like this. I think getting a computer to pull this off will be very tough. –  Matt Greer May 2 '11 at 16:28
Levenshtein distance source code in many languages: Java, Ruby, Python, PHP, etc. en.wikibooks.org/wiki/Algorithm_Implementation/Strings/… –  joelparkerhenderson May 4 '12 at 1:26
In general, what counts as "closest string" will depend on the similarity measure used, and the penalties used for introducing gaps in the alignment. For example, do you consider "cow" and "chicken" more similar than "cow" and "red" (because they are related concepts), or is it the other way around (because "chicken" has more letters than "cow")? But given a similarity measure and gap penalty, it can be shown that the Levenshtein algorithm below is guaranteed to find you the closest string. Same is true of Needleman-Wunsch and Smith-Waterman (further below). –  Sten L May 4 '12 at 9:56

8 Answers 8

up vote 630 down vote accepted











    ReDim D(0 To L1, 0 To L2)

    For j = 1 To L2
        For i = 1 To L1
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            If cI <= cD Then 'Insertion or Substitution
            Else 'Deletion or Substitution
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function


valueWords, valuePhrase, and Split function:

    valuePhrase = LevenshteinDistance(S1, S2)
End Function

    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

' SplitMultiDelims
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' element array if the Text is successfully split into substrings.
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If

    Elements = 0: ElemStart = 1
    For N = 1 To lText
            If IgnoreConsecutiveDelimiters Then
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N

    SplitMultiDelims = Arr
End Function

Measures of Similarity



Fuzzy String Matching Permutations

Fuzzy String Matching Value Phrase

Fuzzy String Matching Value Words





Fuzzy String Matching Optimized Metric







Fuzzy String Matching Benchmark

Further Applications




share|improve this answer
Bonus: If anyone wants to include additional metrics into their weighted heuristic, (since I only provided 3 which weren't all that linearly independent) - here is a whole list on wikipedia: en.wikipedia.org/wiki/String_metric –  Alain Apr 9 '12 at 20:22
Awesome! You may be able to speed this up quite a bit by replacing the 2D-matrix-based code in LevenshteinDistance() with something like the 1D approach as used in Chas Emerick’s Java implementation. –  JanX2 May 4 '12 at 18:46
If S2 has a lot of words (and creating many small objects is not prohibitively slow in your language of choice) a trie can speed things up. Fast and Easy Levenshtein distance using a Trie is a great article about tries. –  JanX2 May 4 '12 at 19:20
You win the internet for this answer. Game over. –  Scott Beeson Apr 17 '13 at 19:12

This problem turns up all the time in bioinformatics. The accepted answer above (which was great by the way) is known in bioinformatics as the Needleman-Wunsch (compare two strings) and Smith-Waterman (find an approximate substring in a longer string) algorithms. They work great and have been workhorses for decades.

But what if you have a million strings to compare? That's a trillion pairwise comparisons, each of which is O(n*m)! Modern DNA sequencers easily generate a billion short DNA sequences, each about 200 DNA "letters" long. Typically, we want to find, for each such string, the best match against the human genome (3 billion letters). Clearly, the Needleman-Wunsch algorithm and its relatives will not do.

This so-called "alignment problem" is a field of active research. The most popular algorithms are currently able to find inexact matches between 1 billion short strings and the human genome in a matter of hours on reasonable hardware (say, eight cores and 32 GB RAM).

Most of these algorithms work by quickly finding short exact matches (seeds) and then extending these to the full string using a slower algorithm (for example, the Smith-Waterman). The reason this works is that we are really only interested in a few close matches, so it pays off to get rid of the 99.9...% of pairs that have nothing in common.

How does finding exact matches help finding inexact matches? Well, say we allow only a single difference between the query and the target. It is easy to see that this difference must occur in either the right or left half of the query, and so the other half must match exactly. This idea can be extended to multiple mismatches and is the basis for the ELAND algorithm commonly used with Illumina DNA sequencers.

There are many very good algorithms for doing exact string matching. Given a query string of length 200, and a target string of length 3 billion (the human genome), we want to find any place in the target where there is a substring of length k that matches a substring of the query exactly. A simple approach is to begin by indexing the target: take all k-long substrings, put them in an array and sort them. Then take each k-long substring of the query and search the sorted index. Sort and search can be done in O(log n) time.

But storage can be a problem. An index of the 3 billion letter target would need to hold 3 billion pointers and 3 billion k-long words. It would seem hard to fit this in less than several tens of gigabytes of RAM. But amazingly we can greatly compress the index, using the Burrows-Wheeler transform, and it will still be efficiently queryable. An index of the human genome can fit in less than 4 GB RAM. This idea is the basis of popular sequence aligners such as Bowtie and BWA.

Alternatively, we can use a suffix array, which stores only the pointers, yet represents a simultaneous index of all suffixes in the target string (essentially, a simultaneous index for all possible values of k; the same is true of the Burrows-Wheeler transform). A suffix array index of the human genome will take 12 GB of RAM if we use 32-bit pointers.

The links above contain a wealth of information and links to primary research papers. The ELAND link goes to a PDF with useful figures illustrating the concepts involved, and shows how to deal with insertions and deletions.

Finally, while these algorithms have basically solved the problem of (re)sequencing single human genomes (a billion short strings), DNA sequencing technology improves even faster than Moore's law, and we are fast approaching trillion-letter datasets. For example, there are currently projects underway to sequence the genomes of 10,000 vertebrate species, each a billion letters long or so. Naturally, we will want to do pairwise inexact string matching on the data...

share|improve this answer
Really good run-down. A couple of corrections: Sorting the infixes takes O(n) at least, not O(log n). And since O(log n) search is actually too slow in practice, you’d normally build an additional table to get O(1) lookup (q-gram index). Furthermore, I’m not sure why you treat this differently from the suffix array – it’s just an optimisation of the latter, no (sorting fixed-length infixes instead of suffixes since we don’t actually need more than a fixed length). –  Konrad Rudolph May 4 '12 at 8:52
Furthermore, these algorithms are still impractical for de novo sequencing. They’ve solved the sequencing of human genomes only insofar as we have a reference sequence that can be used to map against. But for de novo assembly other algorithms are needed (well, there are some aligners which are based on mapping but stitching the contigs together is a whole ’nother problem). Finally, shameless plug: my bachelor thesis contains a detailed description of the ELAND algorithm. –  Konrad Rudolph May 4 '12 at 8:55
Thanks. I edited out the error. The reason I started by describing the fixed-length array was because it's easy to understand. Suffix arrays and BWT are a bit harder to grasp, but actually we do sometimes want to use an index with different values of k. For example, STAR uses suffix arrays to efficiently find spliced alignments. This is of course useful for aligning RNA to the genome. –  Sten L May 4 '12 at 9:16

I contest that choice B is closer to the test string, as it's only 4 characters(and 2 deletes) from being the original string. Whereas you see C as closer because it includes both brown and red. It would, however, have a greater edit distance.

There is an algorithm called Levenshtein Distance which measures the edit distance between two inputs.

Here is a tool for that algorithm.

  1. Rates choice A as a distance of 15.
  2. Rates choice B as a distance of 6.
  3. Rates choice C as a distance of 9.

EDIT: Sorry, I keep mixing strings in the levenshtein tool. Updated to correct answers.

share|improve this answer
Ok, I guess that is true. I'll take a look at this. I personally don't care how close it is to the target as long as it is pretty dang close. No need for perfection ;) Points for you until I can verify the results of your answer :) –  Xander May 2 '11 at 16:31

Lua implementation, for posterity:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
    return distance[len1][len2]
share|improve this answer

You might be interested in this blog post.


Fuzzywuzzy is a Python library that provides easy distance measures such as Levenshtein distance for string matching. It is built on top of difflib in the standard library and will make use of the C implementation Python-levenshtein if available.


share|improve this answer

You might find this library helpful! http://code.google.com/p/google-diff-match-patch/

It is currently available in Java, JavaScript, Dart, C++, C#, Objective C, Lua and Python

It works pretty well too. I use it in a couple of my Lua projects.

And I don't think it would be too difficult to port it to other languages!

share|improve this answer

If you're doing this in the context of a search engine or frontend against a database, you might consider using a tool like Apache Solr, with the ComplexPhraseQueryParser plugin. This combination allows you to search against an index of strings with the results sorted by relevance, as determined by Levenshtein distance.

We've been using it against a large collection of artists and song titles when the incoming query may have one or more typos, and it's worked pretty well (and remarkably fast considering the collections are in the millions of strings).

Additionally, with Solr, you can search against the index on demand via JSON, so you won't have to reinvent the solution between the different languages you're looking at.

share|improve this answer

A very, very good resource for these kinds of algorithms is Simmetrics: http://sourceforge.net/projects/simmetrics/

Unfortunately the awesome website containing a lot of the documentation is gone :( In case it comes back up again, its previous address was this: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (courtesy of "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

You can study the code source, there are dozens of algorithms for these kinds of comparisons, each with a different trade-off. The implementations are in Java.

share|improve this answer

protected by minitech May 4 '12 at 14:06


Would you like to answer one of these unanswered questions instead?
