PureBasic Forum
https://www.purebasic.fr/english/

Damerau–Levenshtein distance
https://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 distance

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:
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))

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 Group
http://www.phpbb.com/