PureBasic Forums - English

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