Ooops
November 28, 2020, 01:55:46 PM

Author Topic: [bmx] Levenshtein distance by Warpy [ 1+ years ago ]  (Read 610 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Levenshtein distance by Warpy [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
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...


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal