Login Register
Frontpage Code library Pastebin

Levenshtein()

Author: Jare
Added: 26.7.2012 23:46
Edited: 27.7.2012 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 all
 1
 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.