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.

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

 "saared" ja "baar" kaugus on 3.

 Tähe "s" asendasime tähega "b". (+1)
 Eemaldasime tähe "e". (+1)
 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  kahe sõne  ja  vahel on:



Kus:

  on sõne  pikkus
  on kattuvate sümbolite arv
  transpositsioonide arv

 Jaro-Winkleri sarnasus 
Jaro-Winkleri sarnasuse meetod kasutab konstanti , mis annab kõrgemaid hinnanguid sõnedele, mille prefiks ühtib pikkuseni . Kui on antud kaks sõne ​ ja ​, siis nende Jaro-Winkleri sarnasus ​ on:



Kus:

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

Jaro-Winkleri kaugus  on defineeritud kui .

 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  kahe sõne  ja  vahel on:



Kus:

  on sõne  pikkus
  on sõne  ja  pikim ühine alamjada.

Näide:

 "baar" ja "saared" kaugus on 4.

 Pikim ühine alamjada on "aar", ehk .




 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.

 Tähe "g" asendasime tähega "k". (+0,8)
 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.

 Viited 

Kategooria:Keeleteadus