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

## Bookmarks