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:

* “**m**a**j**a” ja “**p**a**d**a” 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:

* "**b**aar" ja "**s**aar**ed**" kaugus on 3.

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

* "**s**aar**ed**" ja "**b**aar" 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 sim_j kahe sõne s_1 ja s_2 vahel on:

: sim_j = \left\{
\begin{array}{l l}
  0 & \text{kui }m = 0\\
  \frac{1}{3}\left(\frac{m} + \frac{m} + \frac{m-t}{m}\right) & \text{vastasel korral} \end{array} \right.

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 sim_w​ on:

: sim_w = sim_j + \ell p (1 - sim_j),

Kus:

* sim_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 - sim_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.

# Pikim ühine alamjada on "aar", ehk LCS(baar, saared) = 3.
# |baar| = 4
# |saared| = 6
# 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.

* "siis**g**i**i**" ja "siis**k**i" 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