Hvordan man beregner Levenshtein Distance i Java?

1. Introduktion

I denne artikel beskriver vi Levenshtein-afstanden, alternativt kendt som Rediger afstanden. Den forklarede algoritme blev udtænkt af en russisk videnskabsmand, Vladimir Levenshtein, i 1965.

Vi giver en iterativ og en rekursiv Java-implementering af denne algoritme.

2. Hvad er Levenshtein Distance?

Levenshtein afstanden er et mål for ulighed mellem to Strenge. Matematisk givet to Strengex og y, måler afstanden det mindste antal tegnredigeringer, der kræves for at transformere x ind i y.

Typisk er tre typer redigeringer tilladt:

  1. Indsættelse af et tegn c
  2. Sletning af et tegn c
  3. Udskiftning af et tegn c med c

Eksempel: Hvis x = 'skud' og y = 'plet', redigeringsafstanden mellem de to er 1 fordi 'skud' kan konverteres til 'få øje på' ved at erstatte 'h' til 's‘.

I visse underklasser af problemet kan omkostningerne forbundet med hver type redigering være forskellige.

For eksempel lavere omkostninger ved erstatning med et tegn, der ligger i nærheden på tastaturet, og ellers koster det flere. For enkelheds skyld betragter vi alle omkostninger som lige i denne artikel.

Nogle af anvendelserne af redigeringsafstand er:

  1. Stavekontrol - registrerer stavefejl i tekst og find den nærmeste korrekte stavning i ordbogen
  2. Plagiatdetektion (se - IEEE Paper)
  3. DNA-analyse - finde lighed mellem to sekvenser
  4. Talegenkendelse (se - Microsoft Research)

3. Algoritmeformulering

Lad os tage to Strenge x og y af længder m og n henholdsvis. Vi kan betegne hver Snor som x [1: m] og y [1: n].

Vi ved det i slutningen af ​​transformationen, begge Strenge har samme længde og har matchende tegn på hver position. Så hvis vi overvejer den første karakter af hver Snor, vi har tre muligheder:

  1. Udskiftning:
    1. Bestem omkostningerne (D1) at erstatte x [1] med y [1]. Omkostningerne ved dette trin er nul, hvis begge tegn er ens. Hvis ikke, ville omkostningerne være en
    2. Efter trin 1.1 ved vi, at begge dele Strenge start med den samme karakter. Derfor vil de samlede omkostninger nu være summen af ​​omkostningerne ved trin 1.1 og omkostningerne ved at transformere resten af Streng x [2: m] ind i y [2: n]
  2. Indskud:
    1. Indsæt et tegn i x for at matche det første tegn i y, ville omkostningerne ved dette trin være en
    2. Efter 2.1 har vi behandlet et tegn fra y. Derfor vil de samlede omkostninger nu være summen af ​​omkostningerne i trin 2.1 (dvs. 1) og omkostningerne ved at transformere det fulde x [1: m] til resterende y (y [2: n])
  3. Sletning:
    1. Slet det første tegn fra x, ville omkostningerne ved dette trin være en
    2. Efter 3.1 har vi behandlet et tegn fra x, men det fulde y mangler at blive behandlet. De samlede omkostninger vil være summen af ​​omkostningerne på 3,1 (dvs. 1) og de resterende transformationsomkostninger x fuldt ud y

Den næste del af løsningen er at finde ud af, hvilken mulighed der skal vælges ud af disse tre. Da vi ikke ved, hvilken mulighed der vil føre til minimale omkostninger i slutningen, skal vi prøve alle muligheder og vælge den bedste.

4. Naiv rekursiv implementering

Vi kan se, at det andet trin i hver indstilling i afsnit # 3 for det meste er det samme redigeringsafstandsproblem, men på understrenge af originalen Strenge. Dette betyder, at efter hver iteration ender vi med det samme problem, men med mindre Strenge.

Denne observation er nøglen til at formulere en rekursiv algoritme. Gentagelsesforholdet kan defineres som:

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

D (x [2: m], y [2: n]) + Omkostninger ved erstatning af x [1] til y [1],

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

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

}

Vi skal også definere basissager for vores rekursive algoritme, hvilket i vores tilfælde er, når den ene eller begge Strenge blive tom:

  1. Når begge Strenge er tomme, så er afstanden mellem dem nul
  2. Når en af ​​de Strenge er tom, så er redigeringsafstanden mellem dem længden på den anden Snor, da vi har brug for så mange antal indsættelser / sletninger for at omdanne den ene til den anden:
    • Eksempel: hvis en Snor er "hund" og andre Snor er “” (tom), har vi brug for enten tre indsættelser i tomme Snor At lave det "hund", eller vi har brug for tre sletninger i "hund" at gøre det tomt. Derfor er redigeringsafstanden mellem dem 3

En naiv rekursiv implementering af denne algoritme:

offentlig klasse EditDistanceRecursive {statisk int beregne (String x, String y) {if (x.isEmpty ()) {return y.length (); } hvis (y.isEmpty ()) {return x.length (); } int substitution = beregne (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int-indsættelse = beregne (x, y.substring (1)) + 1; int-sletning = beregne (x.substring (1), y) + 1; retur min (erstatning, indsættelse, sletning); } offentlig statisk int costOfSubstitution (char a, char b) {return a == b? 0: 1; } offentlige statiske int min (int ... numre) {return Arrays.stream (numbers) .min (). ellerElse (Integer.MAX_VALUE); }}

Denne algoritme har den eksponentielle kompleksitet. Ved hvert trin forgrener vi os i tre rekursive opkald, der bygger et O (3 ^ n) kompleksitet.

I det næste afsnit vil vi se, hvordan vi kan forbedre dette.

5. Dynamisk programmeringsmetode

Når vi analyserer de rekursive opkald, bemærker vi, at argumenterne for underproblemer er suffikser af originalen Strenge. Dette betyder, at der kun kan være m * n unikke rekursive opkald (hvor m og n er et antal suffikser af x og y). Derfor bør kompleksiteten af ​​den optimale løsning være kvadratisk, O (m * n).

Lad os se på nogle af underproblemerne (ifølge gentagelsesforhold defineret i afsnit # 4):

  1. Underproblemer med 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])
  2. Underproblemer med 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])
  3. Underproblemer med 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 tilfælde er et af underproblemerne D (x [2: m], y [2: n]). I stedet for at beregne dette tre gange, som vi gør i den naive implementering, kan vi beregne dette en gang og genbruge resultatet, når det er nødvendigt igen.

Dette problem har mange overlappende underproblemer, men hvis vi kender løsningen på underproblemerne, kan vi let finde svaret på det oprindelige problem. Derfor har vi begge de egenskaber, der er nødvendige for at formulere en dynamisk programmeringsløsning, dvs. overlappende underproblemer og optimal underkonstruktion.

Vi kan optimere den naive implementering ved at indføre memoization, dvs. gemme resultatet af delproblemerne i en matrix og genbruge de cachelagrede resultater.

Alternativt kan vi også implementere dette iterativt ved hjælp af en tabelbaseret tilgang:

statisk int beregne (String x, String y) {int [] [] dp = ny int [x.længde () + 1] [y.længde () + 1]; for (int i = 0; i <= x.længde (); i ++) {for (int j = 0; j <= y.længde (); j ++) {hvis (i == 0) {dp [i] [j] = j; } ellers hvis (j == 0) {dp [i] [j] = i; } andet {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 algoritme fungerer betydeligt bedre end den rekursive implementering. Det indebærer dog et betydeligt hukommelsesforbrug.

Dette kan yderligere optimeres ved at observere, at vi kun har brug for værdien af ​​tre tilstødende celler i tabellen for at finde værdien af ​​den aktuelle celle.

6. Konklusion

I denne artikel beskrev vi, hvad der er Levenshtein-afstand, og hvordan den kan beregnes ved hjælp af en rekursiv og en dynamisk programmeringsbaseret tilgang.

Levenshtein-afstand er kun et af målene for strenglighed, nogle af de andre målinger er Cosine-lighed (som bruger en tokenbaseret tilgang og betragter strengene som vektorer), Terningskoefficient osv.

Som altid kan den fulde implementering af eksempler findes på GitHub.


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