streamalism.org

1. Úvod

V tomto článku popisujeme Levenshteinovu vzdialenosť, ktorá je alternatívne známa ako Editova vzdialenosť. Tu opísaný algoritmus navrhol ruský vedec Vladimir Levenshtein v roku 1965.

Poskytneme iteratívnu a rekurzívnu implementáciu Java tohto algoritmu.

2. Aká je vzdialenosť Levenshtein?

Levenshteinova vzdialenosť je mierou odlišnosti medzi dvoma Struny. Matematicky dané dva StrunyX a r, vzdialenosť meria minimálny počet úprav znakov potrebných na transformáciu X do r.

Spravidla sú povolené tri typy úprav:

1. Vloženie znaku c
2. Vymazanie znaku c
3. Nahradenie znaku c s c‘

Príklad: Ak x = „výstrel“ a y = „miesto“, vzdialenosť úprav medzi nimi je 1, pretože 'strela' možno previesť na „Spot“ nahradením „h„Do“p‘.

V určitých podtriedach problému môžu byť náklady spojené s každým typom úpravy odlišné.

Napríklad nižšie náklady na nahradenie znakom umiestneným v blízkosti klávesnice a vyššie náklady inak. Pre zjednodušenie budeme v tomto článku považovať všetky náklady za rovnaké.

Niektoré z aplikácií úpravy vzdialenosti sú:

1. Kontrola pravopisu - zisťovanie pravopisných chýb v texte a nájdenie najbližšieho správneho pravopisu v slovníku
2. Detekcia plagiátorstva (pozri - IEEE Paper)
3. Analýza DNA - nájdenie podobnosti medzi dvoma sekvenciami
4. Rozpoznávanie reči (odkaz - Microsoft Research)

3. Formulácia algoritmu

Zoberme si dve Struny x a r dĺžok m a n resp. Môžeme označiť každý String ako x [1: m] a y [1: n].

Vieme, že na konci transformácie obaja Struny budú rovnako dlhé a budú mať na každej pozícii zodpovedajúce znaky. Ak teda vezmeme do úvahy prvý znak každého z nich Reťazec, máme tri možnosti:

1. Striedanie:
   1. Určte cenu (D1) striedania x [1] s r [1]. Cena tohto kroku by bola nulová, ak sú oba znaky rovnaké. Ak nie, potom by cena bola jedna
   2. Po kroku 1.1 vieme, že oboje Struny začnite rovnakým znakom. Preto by celkové náklady boli teraz súčtom nákladov na krok 1.1 a nákladov na transformáciu zvyšku Reťazec x [2: m] do y [2: n]
2. Vloženie:
   1. Vložte znak do X aby sa zhodoval s prvým znakom v r, náklady na tento krok by boli jedny
   2. Po 2.1 sme spracovali jeden znak z r. Preto by celkové náklady boli teraz súčtom nákladov na krok 2.1 (t. J. 1) a nákladov na transformáciu celého x [1: m] na zostávajúce y (y [2: n])
3. Vymazanie:
   1. Vymazať prvý znak z X, náklady na tento krok by boli jedny
   2. Po 3.1 sme spracovali jeden znak z X, ale úplné r zostáva spracovať. Celkové náklady by boli súčtom nákladov na 3,1 (t. J. 1) a nákladov na transformáciu zostávajúcich X naplno r

Ďalšou časťou riešenia je prísť na to, ktorú z týchto troch možností zvoliť. Pretože nevieme, ktorá možnosť by na konci viedla k minimálnym nákladom, musíme vyskúšať všetky možnosti a zvoliť tú najlepšiu.

4. Naivná rekurzívna implementácia

Vidíme, že druhý krok každej možnosti v časti # 3 je väčšinou rovnaký problém s vzdialenosťou úprav, ale na podreťazcoch pôvodného Struny. To znamená, že po každej iterácii skončíme s rovnakým problémom, ale s menším Struny.

Toto pozorovanie je kľúčom k formulovaniu rekurzívneho algoritmu. Vzťah opakovania možno definovať ako:

D (x [1: m], y [1: n]) = min {

D (x [2: m], r [2: n]) + náklady na výmenu x [1] za r [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

Musíme tiež definovať základné prípady pre náš rekurzívny algoritmus, ktorým je v našom prípade jeden alebo obidva Struny stať sa prázdnym:

1. Keď oboje Struny sú prázdne, potom je vzdialenosť medzi nimi nulová
2. Keď jeden z Struny je prázdny, potom vzdialenosť medzi úpravami predstavuje dĺžku druhého Reťazec, pretože potrebujeme toľko čísel na vloženie / vymazanie, aby sme mohli transformovať jedno do druhého:
   • Príklad: ak jeden String je "pes" a ďalšie String je “” (prázdny), potrebujeme buď tri vloženia prázdne String urobiť to "pes"alebo potrebujeme tri vymazania "pes" aby to bolo prázdne. Preto je vzdialenosť úprav medzi nimi 3

Naivná rekurzívna implementácia tohto algoritmu:

verejná trieda EditDistanceRecursive {statický int vypočítať (reťazec x, reťazec y) {if (x.isEmpty ()) {návrat y.length (); } if (y.isEmpty ()) {return x.length (); } int substitúcia = vypočítať (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int vloženie = vypočítať (x, y.substring (1)) + 1; int deletion = vypočítať (x.substring (1), y) + 1; návrat min (substitúcia, vloženie, vymazanie); } public static int costOfSubstitution (char a, char b) {return a == b? 0: 1; } public static int min (int ... numbers) {return Arrays.stream (numbers) .min (). orElse (Integer.MAX_VALUE); }}

Tento algoritmus má exponenciálnu zložitosť. V každom kroku sa rozdelíme na tri rekurzívne volania a zostavíme an O (3 ^ n) zložitosť.

V nasledujúcej časti uvidíme, ako to vylepšiť.

5. Prístup dynamického programovania

Pri analýze rekurzívnych volaní pozorujeme, že argumenty pre čiastkové problémy sú príponami originálu Struny. To znamená, že môže byť iba m * n jedinečné rekurzívne volania (kde m a n je niekoľko prípon X a r). Zložitosť optimálneho riešenia by preto mala byť kvadratická, O (m * n).

Pozrime sa na niektoré z čiastkových problémov (podľa vzťahu opakovania definovaného v časti # 4):

1. Čiastkové problémy D (x [1: m], y [1: n]) sú D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) a D (x [2: m], y [1: n])
2. Čiastkové problémy D (x [1: m], y [2: n]) sú D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) a D (x [2: m], y [2: n])
3. Čiastkové problémy D (x [2: m], y [1: n]) sú D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) a D (x [3: m], y [1: n])

Vo všetkých troch prípadoch je jedným z čiastkových problémov D (x [2: m], y [2: n]). Namiesto toho, aby sme to vypočítali trikrát, ako to robíme v naivnej implementácii, to môžeme vypočítať raz a znova použiť výsledok, kedykoľvek to bude potrebné.

Tento problém má veľa prekrývajúcich sa čiastkových problémov, ale ak poznáme riešenie týchto čiastkových problémov, môžeme ľahko nájsť odpoveď na pôvodný problém. Preto máme obe vlastnosti potrebné na formulovanie dynamického programovacieho riešenia, t. J. Prekrývajúce sa čiastkové problémy a optimálna podštruktúra.

Naivnú implementáciu môžeme optimalizovať zavedením memoizácie, t. J. Uložiť výsledok čiastkových problémov do poľa a znova použiť výsledky uložené v pamäti.

Prípadne to môžeme implementovať aj iteratívne pomocou prístupu založeného na tabuľkách:

static int count (String x, String y) {int [] [] dp = new int [x.length () + 1] [y.length () + 1]; pre (int i = 0; i <= x.length (); i ++) {for (int j = 0; j <= y.length (); j ++) {if (i == 0) {dp [i] [j] = j; } else if (j == 0) {dp [i] [j] = i; } else {dp [i] [j] = min (dp [i - 1] [j - 1] + costOfSubstitution (x.charAt (i - 1), y.charAt (j - 1)), dp [i - 1] [j] + 1, dp [i] [j - 1] + 1); }}} vratit dp [x.length ()] [y.length ()]; } 

Tento algoritmus funguje podstatne lepšie ako rekurzívna implementácia. Zahŕňa to však značnú spotrebu pamäte.

To je možné ďalej optimalizovať pozorovaním, že na nájdenie hodnoty aktuálnej bunky potrebujeme iba hodnotu troch susedných buniek v tabuľke.

6. Záver

V tomto článku sme popísali, čo je Levenshteinova vzdialenosť a ako sa dá vypočítať pomocou rekurzívneho prístupu založeného na dynamickom programovaní.

Levenshteinova vzdialenosť je iba jedným z meradiel podobnosti reťazcov, niektoré ďalšie metriky sú Cosine Podobnosť (ktorá využíva prístup založený na tokenoch a považuje reťazce za vektory), Kockový koeficient atď.

Úplnú implementáciu príkladov nájdete ako vždy na serveri GitHub.