You can use the Damerau–Levenshtein distance as a string metric for measuring the edit distance between two sequences (e.g. for correction suggestions).
Code: Select all
Macro D(i,j)
D_(i+1,j+1)
EndMacro
Procedure DamerauLevenshteinDistance(String1$, String2$)
Define.i m, n, i, j, k, l, db, min, value, cost, maxDist
NewMap DA.i()
m = Len(String1$)
n = Len(String2$)
Dim D_(m+1,n+1)
maxDist = m + n
D(-1,-1) = maxDist
For i=0 To m
D( i,-1) = maxDist
D( i, 0) = i
Next
For j=0 To n
D(-1, j) = maxDist
D( 0, j) = j
Next
For i=1 To m
db = 0
For j=1 To n
k = DA(Mid(String2$, j, 1))
l = db
If Mid(String1$, i, 1) = Mid(String2$, j, 1)
cost = 0
db = j
Else
cost = 1
EndIf
min = D(i-1,j-1) + cost ; a substitution
value = D(i ,j-1) + 1 ; an insertion
If value < min : min = value : EndIf
value = D(i-1,j ) + 1 ; a deletion
If value < min : min = value : EndIf
value = D(k-1,l-1) + (i-k-1) + 1 + (j-l-1) ; transposition
If value < min : min = value : EndIf
D(i,j) = min
Next
DA(Mid(String1$, i, 1)) = i
Next
ProcedureReturn D(m,n)
EndProcedure
;- Testing
n = DamerauLevenshteinDistance("kitten", "sitting")
MessageRequester("Info","Levenshtein Distance= "+Str(n))