Hvordan beregne Levenshtein Distance i Java?

1. Introduksjon

I denne artikkelen beskriver vi Levenshtein-avstanden, alternativt kjent som Edit-avstanden. Algoritmen forklart her ble utviklet av en russisk forsker, Vladimir Levenshtein, i 1965.

Vi gir en iterativ og en rekursiv Java-implementering av denne algoritmen.

2. Hva er Levenshtein Distance?

Levenshtein-avstanden er et mål på ulikhet mellom to Strenger. Matematisk gitt to Strengerx og ymåler avstanden minimum antall tegnendringer som kreves for å transformere x inn i y.

Vanligvis er tre typer redigeringer tillatt:

Innsetting av et tegn c
Sletting av et tegn c
Erstatning av en karakter c med c‘

Eksempel: Hvis x = ‘skutt’ og y = ‘spot ', er redigeringsavstanden mellom de to 1 fordi 'skudd' kan konverteres til 'få øye på' ved å erstatte ‘h' til 's‘.

I visse underklasser av problemet kan kostnadene forbundet med hver type redigering være forskjellige.

For eksempel, mindre kostnad for erstatning med et tegn som ligger i nærheten på tastaturet og ellers mer kostnad. For enkelhets skyld vil vi vurdere alle kostnadene som like i denne artikkelen.

Noen av applikasjonene for redigeringsavstand er:

Stavekontroll - oppdager stavefeil i tekst og finner den nærmeste riktige stavemåten i ordboken
Plagiarism Detection (refer - IEEE Paper)
DNA-analyse - finne likhet mellom to sekvenser
Talegjenkjenning (referer - Microsoft Research)

3. Algoritmeformulering

La oss ta to Strenger x og y av lengder m og n henholdsvis. Vi kan betegne hver String som x [1: m] og y [1: n].

Det vet vi på slutten av transformasjonen, begge deler Strenger vil være like lange og ha matchende tegn på hver posisjon. Så hvis vi vurderer den første karakteren til hver Streng, vi har tre alternativer:

Bytte:
1. Bestem kostnaden (D1) for å erstatte x [1] med y [1]. Kostnaden for dette trinnet vil være null hvis begge tegnene er like. Hvis ikke, vil kostnadene være en
2. Etter trinn 1.1 vet vi at begge deler Strenger start med samme karakter. Derfor vil den totale kostnaden nå være summen av kostnaden for trinn 1.1 og kostnaden for å transformere resten av Streng x [2: m] inn i y [2: n]
Innsetting:
1. Sett inn et tegn i x for å matche det første tegnet i yvil kostnaden for dette trinnet være en
2. Etter 2.1 har vi behandlet ett tegn fra y. Derfor vil den totale kostnaden nå være summen av kostnaden for trinn 2.1 (dvs. 1) og kostnaden for å transformere den fulle x [1: m] til gjenværende y (y [2: n])
Sletting:
1. Slett det første tegnet fra xvil kostnaden for dette trinnet være en
2. Etter 3.1 har vi behandlet ett tegn fra x, men den fulle y gjenstår å behandle. Den totale kostnaden vil være summen av kostnaden på 3,1 (dvs. 1) og gjenværende transformasjonskostnad x til det fulle y

Den neste delen av løsningen er å finne ut hvilket alternativ du skal velge blant disse tre. Siden vi ikke vet hvilket alternativ som vil føre til minimale kostnader på slutten, må vi prøve alle alternativene og velge den beste.

4. Naiv rekursiv implementering

Vi kan se at det andre trinnet i hvert alternativ i seksjon # 3 stort sett er det samme redigeringsavstandsproblemet, men på understrenger av originalen Strenger. Dette betyr at etter hver iterasjon ender vi med det samme problemet, men med mindre Strenger.

Denne observasjonen er nøkkelen til å formulere en rekursiv algoritme. Gjentakelsesforholdet kan defineres som:

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

D (x [2: m], y [2: n]) + Kostnad for å erstatte x [1] til y [1],

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

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

}

Vi må også definere basissaker for vår rekursive algoritme, som i vårt tilfelle er når en eller begge deler Strenger bli tom:

Når begge deler Strenger er tomme, så er avstanden mellom dem null
Når en av Strenger er tom, så er redigeringsavstanden mellom dem lengden på den andre Streng, da vi trenger så mange antall innsettinger / slettinger for å transformere hverandre til den andre:
- Eksempel: hvis en String er "hund" og annen String er “” (tom), trenger vi enten tre innsettinger i tomme String å klare det "hund", eller vi trenger tre slettinger i "hund" for å gjøre det tomt. Derfor er redigeringsavstanden mellom dem 3

En naiv rekursiv implementering av denne algoritmen:

offentlig klasse EditDistanceRecursive {static int calc (String x, String y) {if (x.isEmpty ()) {return y.length (); } hvis (y.isEmpty ()) {return x.length (); } int erstatning = beregne (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int innsetting = beregne (x, y.substring (1)) + 1; int-sletting = beregne (x.substring (1), y) + 1; retur min (erstatning, innsetting, sletting); } offentlig statisk int costOfSubstitution (char a, char b) {return a == b? 0: 1; } offentlige statiske int min (int ... tall) {return Arrays.stream (numbers) .min (). orElse (Integer.MAX_VALUE); }}

Denne algoritmen har den eksponentielle kompleksiteten. Ved hvert trinn forgrener vi oss til tre rekursive samtaler, og bygger en O (3 ^ n) kompleksitet.

I neste avsnitt vil vi se hvordan vi kan forbedre dette.

5. Dynamisk programmeringsmetode

Når vi analyserer de rekursive anropene, observerer vi at argumentene for delproblemer er suffikser av originalen Strenger. Dette betyr at det bare kan være m * n unike rekursive samtaler (hvor m og n er et antall suffikser av x og y). Derfor bør kompleksiteten til den optimale løsningen være kvadratisk, O (m * n).

La oss se på noen av delproblemene (i henhold til gjentakelsesrelasjon definert i seksjon 4):

Delproblemer av D (x [1: m], y [1: n]) er D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) og D (x [2: m], y [1: n])
Delproblemer av D (x [1: m], y [2: n]) er D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) og D (x [2: m], y [2: n])
Delproblemer av D (x [2: m], y [1: n]) er D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) og D (x [3: m], y [1: n])

I alle tre tilfeller er det et av underproblemene D (x [2: m], y [2: n]). I stedet for å beregne dette tre ganger som vi gjør i den naive implementeringen, kan vi beregne dette en gang og bruke resultatet når det trengs igjen.

Dette problemet har mange overlappende delproblemer, men hvis vi kjenner løsningen på delproblemene, kan vi enkelt finne svaret på det opprinnelige problemet. Derfor har vi begge egenskapene som trengs for å formulere en dynamisk programmeringsløsning, dvs. overlappende underproblemer og optimal underkonstruksjon.

Vi kan optimalisere den naive implementeringen ved å introdusere notater, dvs. lagre resultatet av underproblemene i en matrise og bruke de hurtigbufrede resultatene på nytt.

Alternativt kan vi også implementere dette iterativt ved å bruke en tabellbasert tilnærming:

statisk int beregne (streng x, streng y) {int [] [] dp = ny int [x.lengde () + 1] [y.lengde () + 1]; for (int i = 0; i <= x.length (); i ++) {for (int j = 0; j <= y.length (); j ++) {if (i == 0) {dp [i] [j] = j; } annet hvis (j == 0) {dp [i] [j] = i; } annet {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); }}} returner dp [x.length ()] [y.length ()]; }

Denne algoritmen fungerer betydelig bedre enn den rekursive implementeringen. Imidlertid innebærer det betydelig minneforbruk.

Dette kan videre optimaliseres ved å observere at vi bare trenger verdien av tre tilstøtende celler i tabellen for å finne verdien til den nåværende cellen.

6. Konklusjon

I denne artikkelen beskrev vi hva som er Levenshtein-avstand, og hvordan den kan beregnes ved hjelp av en rekursiv og en dynamisk programmeringsbasert tilnærming.

Levenshtein-avstand er bare ett av målingene for strenglikhet, noen av de andre beregningene er Cosine Similarity (som bruker en tokenbasert tilnærming og anser strengene som vektorer), Terningskoeffisient, etc.

Som alltid finner du full implementering av eksempler på GitHub.

streamalism.org