# Levenshtein Distance

• 06-14-2016, 02:20 PM
Sparticuz
Levenshtein Distance
Quote:

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.
from https://en.wikipedia.org/wiki/Levenshtein_distance

The following is based on the pseudocode for the 'Iterative with two matrix rows' version

Code:

```FUNCTION LevenshteinDistance AS N (string_1 AS C, string_2 AS C )         ' Degenerate Cases     if strequal(string_1,string_2) then         LevenshteinDistance = 0         end     end if     if len(string_1) == 0 then         LevenshteinDistance = len(string_2)         end     end if     if len(string_2) == 0 then         LevenshteinDistance = len(string_1)         end     end if         dim v0[0..len(string_2)+1] as n     dim v1[0..len(string_2)+1] as n         'initialize v0 (the previous row of distances)     'this row is A[0][i]: edit distance for an empty string_1     'the distance is just the number of characters to delete from string_2     for i = 0 to v0.size()-1         v0[i] = i     next         for i = 0 to len(string_1)         'calculate v1 (current row distances) from the previous row v0         'first element of v1 is A[i+1][0]         'edit distance is delete (i+1) chars from string_1 to match empty string_2         v1[0] = i + 1                 'use formula to fill in the rest of the row         for j = 0 to len(string_2)             if substr(string_1,i,1) == substr(string_2,j,1) then                 dim cost as n = 0             else                 dim cost as n = 1             end if                         dim minList as c             minList = alltrim(str(v1[j]+1)) + crlf() + alltrim(str(v0[j+1]+1)) + crlf() + alltrim(str(v0[j]+cost))             v1[j+1] = *min(minList)         next j                 'copy v1 (current row) to v0 (previous row) for next iteration         for j = 0 to v0.size()-1             v0[j] = v1[j];         next j             next i         LevenshteinDistance = v1[len(string_2)]+1     END FUNCTION```
• 06-18-2016, 05:40 PM
CharlesParker
Re: Levenshtein Distance
I prefer taxicab geometry - because no matter what it will take me forever to figure out complex math...in it's simplest form