Levenšteinin etäisyys

Article on other languages:

• Levenshteinafstand
• Levenshtein-Distanz
• Levenshtein_distance
• Distancia_de_Levenshtein
• Distance_de_Levenshtein
• Distanza_di_Levenshtein
• Levenšteina_attālums
• Levenshteinafstand
• レーベンシュタイン距離
• Levenshtein-distanse
• Odległość_Levenshteina
• Distância_Levenshtein
• Расстояние_Левенштейна
• Левенштајново_растојање
• Khoảng_cách_Levenshtein
• Масофаи_Левенштейн
• Відстань_Левенштейна
• 編輯距離

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Kahden merkkijonon välinen Levenšteinin etäisyys eli editointietäisyys on pienin määrä operaatioita, joiden avulla toinen merkkijono voidaan muuttaa toiseksi. Sallittuja operaatioita ovat tavallisimmin yhden merkin lisääminen, poistaminen tai korvaaminen muulla merkillä. Joskus sallitaan myös kahden vierekkäisen merkin paikan vaihtaminen.

Editointietäisyyden käsitteen esitti venäläinen matemaatikko Vladimir Levenštein vuonna 1965. Siitä on hyötyä sovelluksissa, joiden pitää selvittää, miten lähellä toisiaan annetut merkkijonot ovat, esimerkiksi oikeinkirjoituksen tarkistimissa tai DNA-sekvenssien vertailussa.

Editointietäisyyden erikoistapaus on Hammingin etäisyys, missä merkkijonot ovat samanpituisia ja vain merkkien korvaaminen on sallittua.

Esimerkki

Merkkijonojen urheilija ja murheilta välinen editointietäisyys on 3, koska merkkijonon muuttaminen toiseksi vaatii vähintään kolme operaatiota, esimerkiksi seuraavat:

1. urheilija
2. murheilija (lisättiin m)
3. murheilia (poistettiin j)
4. murheilta (korvattiin i t:llä)

Algoritmi

Levenšteinin etäisyyden laskeva dynaamisen ohjelmoinnin algoritmi käyttää (n + 1) × (m + 1) -kokoista matriisia, missä n ja m ovat merkkijonojen pituudet. Alla on funktion LevenshteinDistance pseudokoodi. Funktio saa syötteeksi kaksi merkkijonoa, str1, jonka pituus on lenStr1, ja str2, jonka pituus on lenStr2, ja laskee niiden välisen editointietäisyyden.

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d on taulukko, jossa on lenStr1+1 riviä ja lenStr2+1 saraketta
   declare int d[0..lenStr1, 0..lenStr2]
   // i ja j käyvät läpi merkkijonot str1 ja str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,     // poisto
                                d[i  , j-1] + 1,     // lisäys
                                d[i-1, j-1] + cost   // korvaus
                            )
 
   return d[lenStr1, lenStr2]