Damerau–Levenshtein distance

Applications, Games, Tools, User libs and useful stuff coded in PureBasic
User avatar
Thorsten1867
Addict
Addict
Posts: 1366
Joined: Wed Aug 24, 2005 4:02 pm
Location: Germany

Damerau–Levenshtein distance

Post by Thorsten1867 »

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: 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))
Translated with http://www.DeepL.com/Translator

Download of PureBasic - Modules
Download of PureBasic - Programs

[Windows 11 x64] [PB V5.7x]
User avatar
HeX0R
Addict
Addict
Posts: 980
Joined: Mon Sep 20, 2004 7:12 am
Location: Hell

Re: Damerau–Levenshtein distance

Post by HeX0R »

For completeness, here is a Levenshtein distance code:
https://www.purebasic.fr/german/viewtop ... 59#p173559
Post Reply