[bmx] Levenshtein distance by Warpy [ 1+ years ago ]

[BlitzBot]

Title : Levenshtein distance
Author : Warpy
Posted : 1+ years ago

Description : The Levenshtein distance is the minimum number of single-character substitutions, deletions or insertions to transform one string into another. It can be used as a metric of 'similarity' of strings.

Code :

Code: BlitzMax

1. 'long-winded version, makes a Len(s)xLen(t) array
2. Function levenshtein(s$,t$)
3.         Local d[Len(s)+1,Len(t)+1]
4.         For i=0 To Len(s)
5.                 d[i,0]=i
6.         Next
7.         For j=0 To Len(t)
8.                 d[0,j]=j
9.         Next
10.         For i=1 To Len(s)
11.                 dbg$=""
12.                 For j=1 To Len(t)
13.                         If s[i-1]=t[j-1] Then cost=0 Else cost=1
14.                         d[i,j]=Min(Min(d[i-1,j]+1,d[i,j-1]+1),d[i-1,j-1]+cost)
15.                         If dbg dbg:+" "
16.                         dbg:+d[i,j]
17.                 Next
18.                 Print dbg
19.         Next
20.         Return d[Len(s),Len(t)]
21. End Function
22.  
23. 'small version, just remembers the current and previous rows of the distance matrix
24. Function levenshtein2(s$,t$)
25.         Local row1[],row2[]
26.         row1=New Int[Len(t)+1]
27.         For j=0 To Len(t)
28.                 row1[j]=j
29.         Next
30.         For i=1 To Len(s)
31.                 row2=New Int[Len(t)+1]
32.                 row2[0]=i
33.                 dbg$=""
34.                 For j=1 To Len(t)
35.                         If s[i-1]=t[j-1] Then cost=0 Else cost=1
36.                         row2[j]=Min(Min(row1[j]+1,row2[j-1]+1),row1[j-1]+cost)
37.                         If dbg dbg:+" "
38.                         dbg:+row2[j]
39.                 Next
40.                 Print dbg
41.                 row1=row2
42.         Next
43.         Return row2[Len(t)]
44. End Function
45.  
46.  
47. While 1
48.         s$=Input(">")
49.         t$=Input(">")
50.         Print levenshtein(s,t)
51.         Print "--"
52.         Print levenshtein2(s,t)
53. Wend

Comments :


xlsior(Posted 1+ years ago)

 Interesting...