# PureBasic Forum

 It is currently Wed Feb 19, 2020 6:31 pm

 All times are UTC + 1 hour

 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Damerau–Levenshtein distancePosted: Sat Jul 27, 2019 7:18 pm
 Addict

Joined: Wed Aug 24, 2005 4:02 pm
Posts: 1109
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

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

Top

 Post subject: Re: Damerau–Levenshtein distancePosted: Tue Jul 30, 2019 1:55 pm
 Enthusiast

Joined: Mon Sep 20, 2004 7:12 am
Posts: 536
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: No registered users and 1 guest

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

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite

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