PureBasic Forumhttps://www.purebasic.fr/english/ Damerau–Levenshtein distancehttps://www.purebasic.fr/english/viewtopic.php?f=27&t=73283 Page 1 of 1

 Author: Thorsten1867 [ Sat Jul 27, 2019 7:18 pm ] Post subject: Damerau–Levenshtein distance Damerau–Levenshtein distanceYou can use the Damerau–Levenshtein distance as a string metric for measuring the edit distance between two sequences (e.g. for correction suggestions).Code:Macro D(i,j)  D_(i+1,j+1)EndMacroProcedure 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;- Testingn = DamerauLevenshteinDistance("kitten", "sitting")MessageRequester("Info","Levenshtein Distance= "+Str(n))

 Author: HeX0R [ Tue Jul 30, 2019 1:55 pm ] Post subject: Re: Damerau–Levenshtein distance For completeness, here is a Levenshtein distance code:https://www.purebasic.fr/german/viewtop ... 59#p173559

 Page 1 of 1 All times are UTC + 1 hour Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Grouphttp://www.phpbb.com/