It is currently Wed Sep 18, 2019 7:46 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: Damerau–Levenshtein distance
PostPosted: Sat Jul 27, 2019 7:18 pm 
Offline
Addict
Addict
User avatar

Joined: Wed Aug 24, 2005 4:02 pm
Posts: 892
Location: Germany
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))

_________________
Sorry for my English. My language is German.
(Translated with http://www.DeepL.com/Translator)

Download of PureBasic - Modules (GitHub)

[Windows 10 x64] [PB V5.7x]


Top
 Profile  
Reply with quote  
 Post subject: Re: Damerau–Levenshtein distance
PostPosted: Tue Jul 30, 2019 1:55 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Mon Sep 20, 2004 7:12 am
Posts: 518
Location: Hell
For completeness, here is a Levenshtein distance code:
https://www.purebasic.fr/german/viewtop ... 59#p173559

_________________
Link dead?
Change h3x0r.ath.cx into hex0rs.coderbu.de and all will be fine.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye