Ooops
March 05, 2021, 07:39:06 AM

Author Topic: [bb] LevenshteinDistance by Charrua [ 1+ years ago ]  (Read 474 times)

Offline BlitzBot

[bb] LevenshteinDistance by Charrua [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : LevenshteinDistance
Author : Charrua
Posted : 1+ years ago

Description : for an example of use see:
<a href="codearcs465b.html?code=2880#comments" target="_blank">http://blitzbasic.com/codearcs/codearcs.php?code=2880#comments[/url]


Code :
Code: BlitzBasic
  1. Function LevenshteinDistance(String1$, String2$)
  2.        
  3.         ;calculates the minimun amount of basic operations required to transmorm String1 into String2
  4.         ;3 basic operations are considered: Character Delet, Insert, Substitution
  5.        
  6.         Local Len1=Len(String1)
  7.         Local Len2=Len(String2)
  8.         Dim Ld(Len1, Len2)
  9.  
  10.         Local i, j, Cost, s1$, s2$
  11.  
  12.         If Len1 = 0 Then Return Len2
  13.         If Len2 = 0 Then Return Len1
  14.        
  15.         For i=0 To Len1
  16.                 Ld(i,0)=i
  17.         Next
  18.         For j=0 To Len2
  19.                 Ld(0,j)=j
  20.         Next
  21.  
  22.         For i=1 To Len1
  23.        
  24.                 For j=1 To Len2
  25.                
  26.                         s1$ = Mid(String1,i,1)
  27.                         s2$ = Mid(String2,j,1)
  28.                         If s1 = s2 Then
  29.                                 Cost=0
  30.                         Else
  31.                                 Cost=1
  32.                         End If
  33.                        
  34.                         Ld(i,j) = Min( Min( Ld(i-1,j)+1 , Ld(i,j-1)+1 ), Ld(i-1,j-1)+Cost)      ;deletion, insertion, substitution
  35.                        
  36.                 Next
  37.         Next
  38.        
  39.         Return Ld(Len1, Len2)
  40.  
  41. End Function


Comments :


Charrua(Posted 1+ years ago)

 the Min(float1, float2) is the classical one:
Code: [Select]
Function Min#(a#, b#)

If a<b Then
Return a
Else
Return b
End If

End Function

(forgot to include it, sorry)Juan


Noobody(Posted 1+ years ago)

 Lovely application of dynamic programming. Well done!


Charrua(Posted 1+ years ago)

 oops!didn't saw this one!:<a href="codearcs78a0.html?code=2439" target="_blank">http://blitzbasic.com/codearcs/codearcs.php?code=2439[/url]Juan


Warpy(Posted 1+ years ago)

 I thought I'd already done this! Oh well, it's a fun programming exercise. [/i]

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal