Kako izračunati udaljenost Levenshteina na Javi?

1. Uvod

U ovom članku opisujemo Levenshteinovu udaljenost, poznatu i kao Uredi udaljenost. Ovdje objašnjeni algoritam osmislio je ruski znanstvenik Vladimir Levenshtein 1965.

Pružit ćemo iterativnu i rekurzivnu Java implementaciju ovog algoritma.

2. Kolika je Levenshteinova udaljenost?

Levenshteinova udaljenost mjera je različitosti između njih dvoje Žice. Matematički, s obzirom na dva Žicex i g, udaljenost mjeri minimalni broj izmjena znakova potrebnih za transformaciju x u g.

Uobičajeno su dopuštene tri vrste uređivanja:

  1. Umetanje lika c
  2. Brisanje lika c
  3. Zamjena lika c s c

Primjer: Ako x = "pucanj" i y = "mjesto", udaljenost za uređivanje između njih je 1 jer 'Pucao' može se pretvoriti u 'mjesto' zamjenom "h"Do"str‘.

U određenim podklasama problema, troškovi povezani sa svakom vrstom uređivanja mogu biti različiti.

Primjerice, manji troškovi zamjene znakom koji se nalazi u blizini na tipkovnici, a veći troškovi inače. Radi jednostavnosti, u ovom ćemo članku sve troškove smatrati jednakima.

Neke od primjena uređivanja udaljenosti su:

  1. Provjere pravopisa - otkrivanje pravopisnih pogrešaka u tekstu i pronalaženje najbližeg ispravnog pravopisa u rječniku
  2. Otkrivanje plagijarizma (pogledajte - IEEE papir)
  3. DNA analiza - pronalaženje sličnosti između dvije sekvence
  4. Prepoznavanje govora (pogledajte - Microsoft Research)

3. Formulacija algoritma

Uzmimo dvije Žice x i g duljina m i n odnosno. Možemo označiti svaku Niz kao x [1: m] i y [1: n].

To znamo na kraju transformacije, oboje Žice bit će jednake duljine i imati odgovarajuće znakove na svakom položaju. Dakle, ako uzmemo u obzir prvi lik svakog od njih Niz, imamo tri mogućnosti:

  1. Zamjena:
    1. Odredite trošak (D1) zamjene x [1] s y [1]. Trošak ovog koraka bio bi nula ako su oba znaka ista. Ako ne, tada bi trošak bio jedan
    2. Nakon koraka 1.1, znamo i jedno i drugo Žice započnite s istim likom. Stoga bi ukupni trošak sada bio zbroj troškova koraka 1.1 i troškova transformiranja ostatka Niz x [2: m] u y [2: n]
  2. Umetanje:
    1. Umetni znak u x kako bi se podudarao s prvim znakom u g, trošak ovog koraka bio bi jedan
    2. Nakon 2.1 obradili smo jedan znak od g. Stoga bi ukupni trošak sada bio zbroj troškova koraka 2.1 (tj. 1) i troškova transformiranja punog x [1: m] da ostane y (y [2: n])
  3. Brisanje:
    1. Izbriši prvi znak iz x, trošak ovog koraka bio bi jedan
    2. Nakon 3.1 obradili smo jedan znak iz x, ali puni g ostaje na obradi. Ukupni trošak bio bi zbroj troškova 3,1 (tj. 1) i preostalog troška pretvorbe x u potpunosti g

Sljedeći je dio rješenja smisliti koju opciju odabrati od ove tri. Budući da ne znamo koja bi opcija na kraju dovela do minimalnih troškova, moramo isprobati sve opcije i odabrati najbolju.

4. Naivna rekurzivna provedba

Možemo vidjeti da je drugi korak svake opcije u odjeljku # 3 uglavnom isti problem uređivanja udaljenosti, ali na podnizima izvornika Žice. To znači da nakon svake iteracije imamo isti problem, ali s manjim Žice.

Ovo je zapažanje ključno za formuliranje rekurzivnog algoritma. Odnos ponavljanja može se definirati kao:

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

D (x [2: m], y [2: n]) + Trošak zamjene x [1] na y [1],

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

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

}

Moramo također definirati osnovne slučajeve za naš rekurzivni algoritam, a to je u našem slučaju kada je jedan ili oba Žice postati prazan:

  1. Kad oboje Žice su prazni, tada je udaljenost između njih jednaka nuli
  2. Kad je jedan od Žice je prazno, tada je udaljenost za uređivanje između njih duljina druge Niz, jer nam treba toliki broj umetanja / brisanja da bismo transformirali jedno u drugo:
    • Primjer: ako jedan Niz je "pas" i druge Niz je “” (prazno), trebaju nam tri umetanja u prazno Niz da bi to uspjelo "pas", ili nam trebaju tri brisanja u "pas" da bude prazno. Stoga je udaljenost između njih 3

Naivna rekurzivna implementacija ovog algoritma:

javna klasa EditDistanceRecursive {static int izračun (niz x, niz y) {if (x.isEmpty ()) {return y.length (); } if (y.isEmpty ()) {return x.length (); } int supstitucija = izračunaj (x.supstring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int umetanje = izračunaj (x, y.supstring (1)) + 1; brisanje int = izračunaj (x.supstring (1), y) + 1; povrat min (zamjena, umetanje, brisanje); } javni statički int costOfSubstitution (char a, char b) {return a == b? 0: 1; } javni statički int min (int ... brojevi) {return Arrays.stream (numbers) .min (). orElse (Integer.MAX_VALUE); }}

Ovaj algoritam ima eksponencijalnu složenost. Na svakom koraku granamo se na tri rekurzivna poziva, gradeći O (3 ^ n) složenost.

U sljedećem ćemo odjeljku vidjeti kako to poboljšati.

5. Pristup dinamičkom programiranju

Analizirajući rekurzivne pozive, uočavamo da su argumenti za pod-probleme sufiksi izvornika Žice. To znači da može biti samo m * n jedinstveni rekurzivni pozivi (gdje m i n su brojni sufiksi od x i g). Stoga bi složenost optimalnog rješenja trebala biti kvadratna, O (m * n).

Pogledajmo neke od potproblema (prema relaciji recidiva definiranoj u odjeljku # 4):

  1. Podproblemi D (x [1: m], y [1: n]) jesu D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) i D (x [2: m], y [1: n])
  2. Podproblemi D (x [1: m], y [2: n]) jesu D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) i D (x [2: m], y [2: n])
  3. Podproblemi D (x [2: m], y [1: n]) jesu D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) i D (x [3: m], y [1: n])

U sva tri slučaja jedan od potproblema je D (x [2: m], y [2: n]). Umjesto da ovo izračunamo tri puta kao što to činimo u naivnoj implementaciji, možemo to izračunati jednom i ponovno upotrijebiti rezultat kad god je to potrebno.

Ovaj problem ima puno preklapajućih podproblema, ali ako znamo rješenje za potprobleme, lako možemo pronaći odgovor na izvorni problem. Stoga imamo oba svojstva potrebna za formuliranje rješenja za dinamičko programiranje, tj. Preklapajući podproblemi i optimalna podstruktura.

Možemo optimizirati naivnu implementaciju uvođenjem pamćenja, tj. Pohraniti rezultat potproblema u niz i ponovno upotrijebiti predmemorirane rezultate.

Alternativno, to također možemo iterativno implementirati koristeći pristup temeljen na tablici:

statički int izračunati (Niz x, Niz y) {int [] [] dp = novi int [x.length () + 1] [y.length () + 1]; for (int i = 0; i <= x.length (); i ++) {for (int j = 0; j <= y.length (); j ++) {if (i == 0) {dp [i] [j] = j; } inače 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.length ()] [y.length ()]; } 

Ovaj algoritam izvodi znatno bolje od rekurzivne implementacije. Međutim, uključuje značajnu potrošnju memorije.

To se dalje može optimizirati opažanjem da nam je potrebna samo vrijednost tri susjedne ćelije u tablici da bismo pronašli vrijednost trenutne ćelije.

6. Zaključak

U ovom smo članku opisali što je Levenshteinova udaljenost i kako se može izračunati pomoću rekurzivnog pristupa i pristupa temeljenog na dinamičkom programiranju.

Levenshteinova udaljenost samo je jedna od mjera sličnosti žica, neke od ostalih mjernih vrijednosti su Cosine sličnost (koja koristi pristup zasnovan na žetonu i žice smatra vektorima), koeficijent kockica itd.

Kao i uvijek, puna implementacija primjera može se naći na GitHubu.


$config[zx-auto] not found$config[zx-overlay] not found