1. ## Levenshtein Distance

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```

2. ## 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•