streamalism.org

1. Inleiding

In dit artikel beschrijven we de levenshteinafstand, ook wel de bewerkingsafstand genoemd. Het algoritme dat hier wordt uitgelegd, is in 1965 bedacht door een Russische wetenschapper, Vladimir Levenshtein.

We bieden een iteratieve en een recursieve Java-implementatie van dit algoritme.

2. Wat is de levenshteinafstand?

De levenshteinafstand is een maat voor de ongelijkheid tussen twee Snaren. Wiskundig gezien twee SnarenX en ymeet de afstand het minimum aantal tekenbewerkingen dat nodig is om te transformeren X in y.

Meestal zijn drie soorten bewerkingen toegestaan:

1. Invoegen van een karakter c
2. Schrapping van een teken c
3. Vervanging van een personage c met c‘

Voorbeeld: Als x = ‘schot ' en y = ‘spot ', de bewerkingsafstand tussen de twee is 1 omdat 'schot' kan worden geconverteerd naar 'plek' door ‘h' naar 'p‘.

In bepaalde subklassen van het probleem kunnen de kosten die aan elk type bewerking zijn verbonden, verschillen.

Bijvoorbeeld lagere kosten voor vervanging door een teken in de buurt op het toetsenbord en anders meer. Voor het gemak beschouwen we alle kosten in dit artikel als gelijk.

Enkele van de toepassingen van bewerkingsafstand zijn:

1. Spellingcontrole - spellingfouten in tekst detecteren en de dichtstbijzijnde correcte spelling in het woordenboek vinden
2. Plagiaatdetectie (zie - IEEE-papier)
3. DNA-analyse - gelijkenis vinden tussen twee sequenties
4. Spraakherkenning (verwijs - Microsoft Research)

3. Algoritme formulering

Laten we er twee nemen Snaren x en y van lengtes m en n respectievelijk. We kunnen elk aanduiden Draad net zo x [1: m] en y [1: n].

We weten dat beide aan het einde van de transformatie Snaren zal even lang zijn en overeenkomende tekens op elke positie hebben. Dus als we het eerste karakter van elk beschouwen Draad, we hebben drie opties:

1. Vervanging:
   1. Bepaal de kosten (D1) van vervanging x [1] met y [1]. De kosten van deze stap zouden nul zijn als beide karakters hetzelfde zijn. Zo niet, dan zijn de kosten er één
   2. Na stap 1.1 weten we dat beide Snaren begin met hetzelfde karakter. Daarom zouden de totale kosten nu de som zijn van de kosten van stap 1.1 en de kosten voor het transformeren van de rest van het Tekenreeks x [2: m] in y [2: n]
2. Invoeging:
   1. Voeg een teken in X om overeen te komen met het eerste teken in y, zouden de kosten van deze stap één zijn
   2. Na 2.1 hebben we één karakter verwerkt van y. Daarom zijn de totale kosten nu de som van de kosten van stap 2.1 (d.w.z. 1) en de kosten voor het transformeren van de volledige x [1: m] om te blijven y (y [2: n])
3. Schrapping:
   1. Verwijder het eerste teken van X, zouden de kosten van deze stap één zijn
   2. Na 3.1 hebben we één personage verwerkt van X, maar de volledige y moet nog worden verwerkt. De totale kosten zijn de som van de kosten van 3,1 (d.w.z. 1) en de resterende transformatiekosten X ten volle y

Het volgende deel van de oplossing is om erachter te komen welke optie je uit deze drie moet kiezen. Omdat we niet weten welke optie uiteindelijk tot minimale kosten zou leiden, moeten we alle opties proberen en de beste kiezen.

4. Naïeve recursieve implementatie

We kunnen zien dat de tweede stap van elke optie in sectie # 3 meestal hetzelfde bewerkingsafstandsprobleem is, maar op de substrings van het origineel Snaren. Dit betekent dat we na elke iteratie met hetzelfde probleem eindigen, maar met kleinere Snaren.

Deze observatie is de sleutel om een ​​recursief algoritme te formuleren. De herhalingsrelatie kan worden gedefinieerd als:

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

D (x [2: m], y [2: n]) + kosten voor het vervangen van x [1] naar y [1],

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

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

}

We moeten ook basisscases definiëren voor ons recursieve algoritme, in ons geval wanneer een of beide Snaren leeg worden:

1. Wanneer beiden Snaren leeg zijn, dan is de afstand tussen hen nul
2. Wanneer een van de Snaren leeg is, dan is de bewerkingsafstand tussen hen de lengte van de andere Draad, omdat we zoveel aantal invoegingen / verwijderingen nodig hebben om de een in de ander te transformeren:
   • Voorbeeld: als een Draad is "hond" en andere Draad is “” (leeg), we hebben ofwel drie lege invoegingen nodig Draad het maken "hond", of we hebben drie verwijderingen nodig in "hond" om het leeg te maken. Daarom is de bewerkingsafstand tussen hen 3

Een naïeve recursieve implementatie van dit algoritme:

openbare klasse EditDistanceRecursive {statische int berekenen (String x, String y) {if (x.isEmpty ()) {return y.length (); } if (y.isEmpty ()) {return x.length (); } int substitutie = bereken (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); int invoeging = berekenen (x, y.substring (1)) + 1; int schrapping = berekenen (x.substring (1), y) + 1; terug min (vervanging, invoeging, verwijdering); } 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); }}

Dit algoritme heeft de exponentiële complexiteit. Bij elke stap vertakken we ons in drie recursieve oproepen, waarbij we een O (3 ^ n) complexiteit.

In de volgende sectie zullen we zien hoe we dit kunnen verbeteren.

5. Dynamische programmeeraanpak

Bij het analyseren van de recursieve aanroepen zien we dat de argumenten voor subproblemen achtervoegsels zijn van het origineel Snaren. Dit betekent dat er alleen maar kan zijn m * n unieke recursieve aanroepen (where m en n zijn een aantal achtervoegsels van X en y). Daarom moet de complexiteit van de optimale oplossing kwadratisch zijn, O (m * n).

Laten we eens kijken naar enkele van de subproblemen (volgens de herhalingsrelatie gedefinieerd in sectie # 4):

1. Deelproblemen van D (x [1: m], y [1: n]) zijn D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) en D (x [2: m], y [1: n])
2. Deelproblemen van D (x [1: m], y [2: n]) zijn D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) en D (x [2: m], y [2: n])
3. Deelproblemen van D (x [2: m], y [1: n]) zijn D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) en D (x [3: m], y [1: n])

In alle drie de gevallen is een van de deelproblemen D (x [2: m], y [2: n]). In plaats van dit driemaal te berekenen zoals we dat in de naïeve implementatie doen, kunnen we dit een keer berekenen en het resultaat hergebruiken wanneer dat nodig is.

Dit probleem heeft veel overlappende deelproblemen, maar als we de oplossing voor de deelproblemen kennen, kunnen we gemakkelijk het antwoord op het oorspronkelijke probleem vinden. Daarom hebben we beide eigenschappen die nodig zijn voor het formuleren van een dynamische programmeeroplossing, d.w.z. overlappende deelproblemen en optimale onderstructuur.

We kunnen de naïeve implementatie optimaliseren door memoization te introduceren, d.w.z. het resultaat van de subproblemen opslaan in een array en de resultaten in de cache hergebruiken.

Als alternatief kunnen we dit ook iteratief implementeren door een tabelgebaseerde benadering te gebruiken:

statische int berekenen (String x, String y) {int [] [] dp = nieuwe 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; } else if (j == 0) {dp [i] [j] = i; } anders {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); }}} retourneer dp [x.length ()] [y.length ()]; } 

Dit algoritme presteert aanzienlijk beter dan de recursieve implementatie. Het brengt echter een aanzienlijk geheugengebruik met zich mee.

Dit kan verder worden geoptimaliseerd door te observeren dat we alleen de waarde van drie aangrenzende cellen in de tabel nodig hebben om de waarde van de huidige cel te vinden.

6. Conclusie

In dit artikel hebben we beschreven wat Levenshtein-afstand is en hoe deze kan worden berekend met behulp van een recursieve en een op dynamische programmering gebaseerde benadering.

Levenshtein-afstand is slechts een van de maten van snaarovereenkomst, enkele van de andere metrieken zijn Cosinus-gelijkenis (die een op token gebaseerde benadering gebruikt en de strings als vectoren beschouwt), Dobbelsteencoëfficiënt, enz.

Zoals altijd is de volledige implementatie van voorbeelden te vinden op GitHub.