Teisenduskaugus

Teisenduskaugus (inglise keeles edit distance) on mõõt, mis näitab, kui erinevad on kaks sõne üksteisest. Seda mõõdetakse vähima teisenduste arvuga, mis on vajalik ühest sõnest teise saamiseks. Teisenduskaugust kasutatakse näiteks arvutilingvistikas õigekirjavigade automaatseks parandamiseks.

Erinevad teisenduskauguse algoritmid lubavad erinevaid teisenduse operatsioone. Hammingi kaugus lubab ainult tähemärkide asendusi, Levenshteini kaugus lubab tähemärkide lisamist, eemaldamist ja asendusi.

Teisenduskauguse algoritmid

Hammingi kaugus

Hammingi kaugus kahe võrdse pikkusega sõne vahel on positsioonide arv, kus vastavad sümbolid on erinevad. Algoritm sai endale nime USA matemaatiku Richard Hammingi järgi, kes esitles seda mõistet oma artiklis Hammingi koodide kohta 1950. aastal.

Näiteid:

• “maja” ja “pada” kaugus on 2.
• “maja” ja “kuur” kaugus on 4.
• “maja” ja “maja” kaugus on 0.

Levenshteini kaugus

Levenshteini kaugus kahe sõne vahel mõõdab erinevust, mis väljendub ühe sõne teisendamises teiseks minimaalsete sümbolite lisamiste, kustutamiste või asendamiste kaudu. Selle algoritmi töötas välja Nõukogude Liidu matemaatik Vladimir Levenshtein, kes defineeris selle mõõdiku 1965. aastal.

Näide:

• "baar" ja "saared" kaugus on 3.

1. Tähe "b" asendasime tähega "s". (+1)
2. Lisasime tähe "e". (+1)
3. Lisasime tähe "d". (+1)

• "saared" ja "baar" kaugus on 3.

1. Tähe "s" asendasime tähega "b". (+1)
2. Eemaldasime tähe "e". (+1)
3. Eemaldasime tähe "d". (+1)

Jaro-Winkleri kaugus

Jaro-Winkleri kaugus on kahe sõne vaheline mõõdik, mis hindab erinevusi sümbolite järjekorras ja asukohas. Algoritm sai endale nime USA teadlaste Matthew A. Jaro ja William E. Winkleri järgi, kes arendasid seda meetodit andmete sidumise ja veatuvastuse probleemide lahendamiseks. Meetod võeti kasutusele 1990. aastal, tuginedes eelnevale Jaro kauguse meetodile.

Jaro sarnasus

Jaro sarnasus $si{m}_j$ kahe sõne $s_1$ ja $s_2$ vahel on:

$si{m}_j=\{\begin{array}{cc}0& \text{kui }m=0\\ \frac{1}{3}(\frac{m}{|s_1|}+\frac{m}{|s_2|}+\frac{m-t}{m})& \text{vastasel korral}\end{array}$

Kus:

• $|s_i|$ on sõne $s_i$ pikkus
• $m$ on kattuvate sümbolite arv
• $t$ transpositsioonide arv

Jaro-Winkleri sarnasus

Jaro-Winkleri sarnasuse meetod kasutab konstanti $p$, mis annab kõrgemaid hinnanguid sõnedele, mille prefiks ühtib pikkuseni $\ell$. Kui on antud kaks sõne $s_1$​ ja $s_2$​, siis nende Jaro-Winkleri sarnasus $si{m}_w$​ on:

$si{m}_w=si{m}_j+\ell p(1-si{m}_j),$

Kus:

• $si{m}_j$ on sõnede $s_1$ ja $s_2$ Jaro sarnasus
• $\ell$ on ühtiva prefiksi pikkus (kuni maksimaalselt 4 tähemärki)
• $p$ on konstant, mis määrab kui palju skoori tõstetakse ühise prefiksi pikkuse põhjal. $p$ ei tohiks ületada väärtust 0,25, vastasel juhul võib sarnasus minna suuremaks kui 1. Winkleri originaaltöös on $p=0.1$.

Jaro-Winkleri kaugus $d_w$ on defineeritud kui $d_w=1-si{m}_w$.

Pikim ühine alamjada

Pikim ühine alamjada (inglise keeles Longest Common Subsequence) määrab kahe sõne suurima pikkusega alamhulga, mis esineb mõlemas sõnes samas järjekorras, kuid ei pea olema järjestikune.

Pikima ühise alamjada kaugus $d_{LCS}$ kahe sõne $s_1$ ja $s_2$ vahel on:

$d_{LCS}=|s_1|+|s_2|-2\cdot LCS(s_1,s_2)$

Kus:

• $|s_i|$ on sõne $s_i$ pikkus
• $LCS(s_1,s_2)$ on sõne $s_1$ ja $s_2$ pikim ühine alamjada.

Näide:

• "baar" ja "saared" kaugus on 4.

1. Pikim ühine alamjada on "aar", ehk $LCS(baar,saared)=3$.
2. $|baar|=4$
3. $|saared|=6$
4. $4+6-2*3=4$

Kaalud teisenduskauguses

Kaalude kasutamine teisenduskauguses võimaldab valitud teisendustele anda teistsuguse väärtuse. See aitab tulemusi täpsustada vastavalt rakenduse vajadustele.

Näiteks ligikaudse sõne sobitamisel võib klaviatuuril lähestikku asuvatele tähtedele või sarnastele tähtedele anda väiksema kaalu. Näide:

• Määrame tähtede "g" ja "k" asendamise kaaluks 0,8.

• "siisgii" ja "siiski" kaugus on 1,8.

1. Tähe "g" asendasime tähega "k". (+0,8)
2. Eemaldasime tähe "i". (+1)

Kasutusalad

Bioinformaatika

Bioinformaatikas kasutatakse teisenduskaugust geneetilise kauguse leidmiseks, mõõtes nukleotiidide erinevuste arvu kahe geneetilise järjestuse vahel. Lisaks sellele rakendatakse teisenduskaugusi ka valkude domeenide võrdlemisel.

Arvutilingvistika

Arvutilingvistikas rakendatakse teisenduskaugust näiteks optilises märgituvastuses, automaatses õigekirjavigade paranduses, kus arvutatakse minimaalset teisenduskaugust kandidaat sõnade ja valesti kirjutatud sõnade vahel, et leida võimalikke parandusi ja ligikaudse sõne sobitamiseks (nt. Otsingumootor).

Krüptograafia

Teisenduskaugusel põhinevaid meetodeid kasutatakse ka krüptograafias. Näiteks käsitleti uurimuses "Secure Hamming Distance Based Computation and Its Applications" Hamming-kauguse rakendust protokollides, kus kaks osapoolt saavad privaatselt võrrelda kahte sisendit. See meetod võimaldab arvutada funktsioone, mille tulemus sõltub üksnes Hamming-kaugusest kahe sisendi vahel, ilma et kumbki osapool avaldaks oma tegelikku sisendit teisele osapoolele.