Redigeringsavstånd (Levenshteinavstånd)
Skriv recieve så föreslår telefonen receive. Den vet att du var nära, eftersom de två orden bara skiljer sig med ett par ändringar. Att mäta den närheten, redigeringsavståndet, är en klassisk uppgift för dynamisk programmering.
Problemet
En ändring ändrar ett ord med en bokstav: infoga en bokstav, ta bort en bokstav eller ersätt en bokstav med en annan. Redigeringsavståndet mellan två ord är det minsta antalet ändringar som gör det ena till det andra. Mellan cat och cut är avståndet 1, mellan cat och cast också 1 och mellan cat och act 2. Det kallas också Levenshteinavstånd, efter den sovjetiske matematikern Vladimir Levenshtein, som studerade det 1965.
Tabellen
Låt d[i][j] vara redigeringsavståndet mellan de första i bokstäverna i det ena ordet och de första j bokstäverna i det andra. Att göra ett ord till ingenting kräver en borttagning per bokstav, så d[i][0] = i, och att bygga upp ett ord från ingenting kräver en infogning per bokstav, så d[0][j] = j. Om bokstav i är lika med bokstav j är d[i][j] = d[i − 1][j − 1]. Annars är d[i][j] = 1 + den minsta av d[i − 1][j − 1] (ersätt), d[i − 1][j] (ta bort) och d[i][j − 1] (infoga).
Ett exempel
För kitten och sitting har tabellen 7 rader och 8 kolumner. Cellen längst ned till höger är 3, och när man läser baklänges därifrån får man: ersätt k med s, behåll i, t och t, ersätt e med i, behåll n och infoga g. Från kitten till sitten, sedan sittin, sedan sitting: tre ändringar, och tabellen bevisar att det inte finns någon kortare lista.
Läsa ändringarna baklänges
Börja i cellen längst ned till höger och fråga dig vilken granne dess värde kom från. Om bokstäverna stämmer överens och cellen är lika med grannen uppe till vänster behölls bokstaven: gå diagonalt. Om den är ett mer än grannen uppe till vänster var det en ersättning; ett mer än cellen ovanför, en borttagning; ett mer än cellen till vänster, en infogning. Flera vägar kan vara lika bra, och var och en ger en kortaste lista med ändringar.
Historia och användning
Levenshtein införde avståndet 1965 när han arbetade med felrättande koder. Tabellmetoden publicerades av flera personer, mest känt av Robert Wagner och Michael Fischer 1974, så den kallas ofta Wagner–Fischer-algoritmen. I dag rangordnar redigeringsavstånd stavningsförslag, hittar namn med skrivfel i databaser, jämför DNA- och proteinsekvenser och bedömer taligenkänning.
Utforska det
Öppna appen och tryck på Steg. De två bokstäverna som jämförs lyser upp i rubrikerna; lika bokstäver kopierar den blå cellen uppe till vänster, och olika bokstäver läser alla tre blå grannar och lägger till ett till den minsta. Till sist löper den orange stigen tillbaka från hörnet, och ändringarna visas under tabellen.
Ofta ställda frågor
Är redigeringsavstånd en metrik?
Ja. Det är aldrig negativt, det är 0 bara för lika ord, det är detsamma i båda riktningarna, och en omväg via ett tredje ord kan aldrig göra det kortare: d(a, c) ≤ d(a, b) + d(b, c). Det gör det användbart för att söka efter ord som ligger nära.
Vad är Damerau–Levenshteinavstånd?
Redigeringsavståndet med en extra ändring: att byta plats på två intilliggande bokstäver. Frederick Damerau fann 1964 att infoga, ta bort, ersätta och byta tillsammans täcker mer än 80 procent av stavfelen. Med byten ligger recieve och receive 1 ifrån varandra i stället för 2.
Kan redigeringsavstånd beräknas snabbare än O(m·n)?
Inte mycket. År 2015 visade Arturs Backurs och Piotr Indyk att en metod som tar O(n^(2 − ε)) tid för något ε > 0 skulle motbevisa den starka exponentialtidshypotesen, som de flesta forskare tror på. För ord som ligger nära varandra behövs dock bara ett smalt band runt tabellens diagonal.
Hur används redigeringsavstånd för att jämföra DNA?
Biologer använder samma tabell med poäng i stället för antal: matchningar ger poäng, och ersättningar och luckor kostar poäng som beror på bokstäverna. Det är Needleman–Wunsch-algoritmen från 1970 för hela sekvenser och Smith–Waterman-algoritmen från 1981 för de bäst matchande delarna.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Testa redigeringsavstånd