streamalism.org

1. Bemutatkozás

Ebben a cikkben leírjuk a Levenshtein távolságot, más néven a Szerkesztés távolságot. Az itt ismertetett algoritmust egy orosz tudós, Vladimir Levenshtein találta ki 1965-ben.

Biztosítunk egy iteratív és egy rekurzív Java implementációt ennek az algoritmusnak.

2. Mekkora a Levenshtein távolság?

A Levenshtein-távolság a kettő közötti különbség mértéke Húrok. Matematikailag adott kettő Húrokx és y, a távolság az átalakításhoz szükséges karakterszerkesztések minimális számát méri x -ba y.

Általában háromféle szerkesztés engedélyezett:

1. Karakter beszúrása c
2. Karakter törlése c
3. Karakter cseréje c val vel c‘

Példa: Ha x = „lövés” és y = „folt”, a kettő közötti szerkesztési távolság 1, mert 'lövés' konvertálható 'folt' a „h' nak nek 'o‘.

A probléma bizonyos alosztályaiban az egyes szerkesztéstípusokhoz kapcsolódó költségek eltérőek lehetnek.

Például kevesebb költsége van a billentyűzet közelében lévő karakterrel való helyettesítésnek, máskülönben több. Az egyszerűség kedvéért ebben a cikkben az összes költséget egyenlőnek tekintjük.

A szerkesztési távolság néhány alkalmazása a következő:

1. Helyesírás-ellenőrző - a szöveg helyesírási hibáinak észlelése és a szótárban megtalálja a legközelebbi helyesírást
2. Plágium észlelése (hivatkozás - IEEE papír)
3. DNS-elemzés - hasonlóság megtalálása két szekvencia között
4. Beszédfelismerés (hivatkozás - Microsoft Research)

3. Algoritmus megfogalmazása

Vegyünk kettőt Karakterláncok x és y hosszúságúak m és n illetőleg. Jelölhetjük mindegyiket Húr mint x [1: m] és y [1: n].

Tudjuk, hogy az átalakulás végén mindkettő Húrok azonos hosszúságúak lesznek, és minden pozícióban megfelelő karakterek lesznek. Tehát, ha figyelembe vesszük mindegyik első karakterét Húr, három lehetőségünk van:

1. Helyettesítés:
   1. Határozza meg a költséget (D1) helyettesítés x [1] val vel y [1]. Ennek a lépésnek a költsége nulla lenne, ha mindkét karakter azonos. Ha nem, akkor a költség egy lenne
   2. Az 1.1 lépés után tudjuk, hogy mindkettő Húrok ugyanazzal a karakterrel kezdje. Ezért a teljes költség most az 1.1 lépés költségeinek és a többi elem átalakításának költsége lesz Karakterlánc x [2: m] -ba y [2: n]
2. Beillesztés:
   1. Karakter beszúrása ide x hogy illeszkedjen az első karakterhez y, ennek a lépésnek a költsége egy lenne
   2. 2.1 után egy karaktert dolgoztunk fel a y. Ezért az összköltség most a 2.1 lépés költségeinek (azaz az 1. lépésnek) és a teljes x [1: m] hogy maradjon y (y [2: n])
3. Törlés:
   1. Törölje az első karaktert a x, ennek a lépésnek a költsége egy lenne
   2. 3.1 után egy karaktert dolgoztunk fel a x, de a teljes y még feldolgozásra vár. A teljes költség a 3,1 (azaz 1) költségének és a fennmaradó átalakítás költségének összege lenne x teljes mértékben y

A megoldás következő része az, hogy kitaláljuk, melyik opció közül válasszon ebből a háromból. Mivel nem tudjuk, melyik megoldás vezetne minimális költséghez a végén, ki kell próbálnunk az összes lehetőséget, és ki kell választanunk a legjobbat.

4. Naiv rekurzív megvalósítás

Láthatjuk, hogy a 3. szakasz minden egyes opciójának második lépése többnyire ugyanaz a távolság szerkesztési probléma, de az eredeti részhúrjain Húrok. Ez azt jelenti, hogy minden iteráció után ugyanaz a probléma jelentkezik, de kisebb Húrok.

Ez a megfigyelés a kulcs a rekurzív algoritmus megfogalmazásához. Az ismétlődési összefüggés a következőképpen határozható meg:

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

D (x [2: m], y [2: n]) + Az x [1] y [1] -re cseréjének költsége,

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

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

}

Meg kell határoznunk a rekurzív algoritmusunk alapeseteit is, amely esetünkben az, ha az egyik vagy mindkettő Húrok kiürül:

1. Amikor mindkettő Húrok üresek, akkor a köztük lévő távolság nulla
2. Amikor az egyik Húrok üres, akkor a köztük lévő szerkesztési távolság megegyezik a másik hosszával Húr, mivel annyi számú beszúrásra / törlésre van szükségünk egymás átalakításához:
   • Példa: ha egy Húr van "kutya" és egyéb Húr van “” (üres), vagy három beillesztésre van szükségünk üresen Húr hogy elkészítsem "kutya", vagy három törlésre van szükségünk a "kutya" hogy üres legyen. Ezért a köztük lévő szerkesztési távolság 3

Az algoritmus naiv, rekurzív megvalósítása:

public class EditDistanceRecursive {static int calc (String x, String y) {if (x.isEmpty ()) {return y.length (); } if (y.isEmpty ()) {return x.length (); } int szubsztitúció = kiszámítás (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int beillesztés = számítás (x, y.szubstring (1)) + 1; int törlés = számítás (x.substring (1), y) + 1; visszatérési perc (helyettesítés, inszerció, törlés); } public static int costOfSubstitution (char a, char b) {return a == b? 0: 1; } public static int min (int ... számok) {return tömbök.stream (számok) .min (). vagyElse (egész szám.MAX_VALUE); }}

Ennek az algoritmusnak van exponenciális összetettsége. Minden lépésben három rekurzív hívásra bontunk szét egy épületet O (3 ^ n) bonyolultság.

A következő részben megtudjuk, hogyan lehetne ezen javítani.

5. Dinamikus programozási megközelítés

A rekurzív hívások elemzésénél megfigyelhetjük, hogy az alproblémák argumentumai az eredeti utótagjai Húrok. Ez azt jelenti, hogy csak ilyenek lehetnek m * n egyedi rekurzív hívások (ahol m és n számos utótagja x és y). Ezért az optimális megoldás komplexitásának kvadratikusnak kell lennie, O (m * n).

Vizsgáljuk meg néhány részproblémát (a 4. szakaszban meghatározott ismétlődési reláció szerint):

1. A részproblémák D (x [1: m], y [1: n]) vannak D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) és D (x [2: m], y [1: n])
2. A részproblémák D (x [1: m], y [2: n]) vannak D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) és D (x [2: m], y [2: n])
3. A részproblémák D (x [2: m], y [1: n]) vannak D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) és D (x [3: m], y [1: n])

Mindhárom esetben az egyik részprobléma az D (x [2: m], y [2: n]). Ahelyett, hogy ezt háromszor kiszámolnánk, mint a naiv megvalósításban, egyszer kiszámíthatjuk ezt, és szükség esetén újra felhasználhatjuk az eredményt.

Ennek a problémának sok átfedő részproblémája van, de ha ismerjük az alproblémák megoldását, könnyen megtalálhatjuk a választ az eredeti problémára. Ezért mindkettőnk rendelkezik a dinamikus programozási megoldás megfogalmazásához szükséges tulajdonságokkal, azaz Átfedő részproblémák és Optimális alstruktúra.

Optimalizálhatjuk a naiv megvalósítást a memoizálás bevezetésével, vagyis az alproblémák eredményét egy tömbben tárolhatjuk, és a gyorsítótárazott eredményeket újra felhasználhatjuk.

Alternatív megoldásként ezt iteratív módon is megvalósíthatjuk táblázatos megközelítés használatával:

statikus int kiszámítása (String x, String y) {int [] [] dp = új int [x.hossz () + 1] [y.length () + 1]; for (int i = 0; i <= x.hossz (); i ++) {for (int j = 0; j <= y.hossz (); 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); }}} return dp [x.hossz ()] [y.hossz ()]; } 

Ez az algoritmus lényegesen jobban teljesít, mint a rekurzív megvalósítás. Jelentős memóriafogyasztással jár azonban.

Ez tovább optimalizálható annak megfigyelésével, hogy a táblázatban csak három szomszédos cella értékére van szükségünk az aktuális cella értékének megtalálásához.

6. Következtetés

Ebben a cikkben leírtuk, hogy mi a Levenshtein távolság, és hogyan lehet kiszámítani rekurzív és dinamikus programozáson alapuló megközelítéssel.

A Levenshtein távolság csak a húr hasonlóságának egyik mérőszáma, a többi mutató egy része a Kozinusz hasonlóság (amely token alapú megközelítést alkalmaz és a húrokat vektoroknak tekinti), Dice Coefficient stb.

Mint mindig, a példák teljes megvalósítása megtalálható a GitHub oldalon.