Levenshtein Distance

[Sparticuz]

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

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

[CharlesParker]

I prefer taxicab geometry - because no matter what it will take me forever to figure out complex math...in it's simplest form