Levenshtein()
Author: Jare
Added: 26. heinäkuuta 2012 kello 23.46
Edited: 27. heinäkuuta 2012 kello 8.20
Category: Algoritmi
Description
Arkistojen kätköistä: Funktio joka vertaa kahta merkkijonoa ja laskee niiden välisen editointietäisyyden. Mitä pienemmän lukeman funktio palauttaa, sitä lähempänä merkkijonot ovat toisiaan.
Funktio lienee noin vuodelta 2006 ja muistelisin että sen on tehnyt Bagard, mutta en ole varma.
Edit: Koodissa oli jostain syystä typo, vaikka en ollut itse tehnyt siihen muutoksia (tietääkseni). Taulukko d:n ensimmäinen ulottuvuus varattiin väärän kokoiseksi (joissain tapauksissa liian pieneksi), mikä aiheutti MAVailua ja muuta inhottavaa kaatuilua.
Code
Select all1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | Function levenshtein(Str1$,Str2$)
'Varataan taulukko tarvittaville arvoille
Dim d(Len(Str1$),Len(Str2$))
'Käydään läpi taulukot
For i=0 to Len(Str1$)
d(i,0)=d(i,0)+i
Next i
'Sama toisen merkkijonon kanssa
For j=0 to Len(Str2$)
d(0,j)=d(0,j)+j
Next j
For i=1 to Len(Str1$)
For j=1 to Len(Str2$)
'Jos kirjaimet ovat eri, niin lisätään matka
If Mid(Str1$,i,1)=Mid(Str2$,j,1) Then Cost=0 Else Cost=1
x=d(i-1,j)+1 'Poisto
y=d(i,j-1)+1 'Lisäys
z=d(i-1,j-1)+Cost 'Korvaus
'Kaikki lisätään yhteen, jotta pienimmän arvon selvittämisessä ei tule ongelmia
c=x+y+z
'Selvitetään mikä arvoista on pienin
If x<c Then c=x
If y<c Then c=y
If z<c Then c=z
d(i,j)=c
Next j
Next i
'Palautetaan saatu arvo. Se kertoo editointietäisyyden kahden merkkijonon välillä
Return d(Len(Str1$),Len(str2$))
End Function
|
Comments
No comments. You can be first!
Leave a comment
You must be logged in to comment.