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:
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:
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 formula_1 kahe sõne formula_2 ja formula_3 vahel on:
 formula_4
Kus:
Jaro-Winkleri sarnasus.
Jaro-Winkleri sarnasuse meetod kasutab konstanti formula_9, mis annab kõrgemaid hinnanguid sõnedele, mille prefiks ühtib pikkuseni formula_10. Kui on antud kaks sõne formula_2​ ja formula_3​, siis nende Jaro-Winkleri sarnasus formula_13​ on:
 formula_14
Kus:
Jaro-Winkleri kaugus formula_22 on defineeritud kui formula_23.
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 formula_24 kahe sõne formula_2 ja formula_3 vahel on:
 formula_27
Kus:
Näide:
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:
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.