Redigeringsafstand (Levenshtein-afstand)
Skriv recieve, og din telefon foreslår receive. Den ved, at du var tæt på, fordi de to ord kun ligger et par ændringer fra hinanden. At måle den nærhed, redigeringsafstanden, er en klassisk opgave for dynamisk programmering.
Problemet
En ændring ændrer et ord med ét bogstav: indsæt et bogstav, slet et bogstav, eller erstat et bogstav med et andet. Redigeringsafstanden mellem to ord er det mindste antal ændringer, der gør det ene til det andet. Mellem cat og cut er afstanden 1, mellem cat og cast også 1, og mellem cat og act 2. Den kaldes også Levenshtein-afstanden efter den sovjetiske matematiker Vladimir Levenshtein, som undersøgte den i 1965.
Tabellen
Lad d[i][j] være redigeringsafstanden mellem de første i bogstaver i det ene ord og de første j bogstaver i det andet. At gøre et ord til ingenting kræver én sletning pr. bogstav, så d[i][0] = i, og at bygge et ord op fra ingenting kræver én indsættelse pr. bogstav, så d[0][j] = j. Hvis bogstav i er lig med bogstav j, er d[i][j] = d[i − 1][j − 1]. Ellers er d[i][j] = 1 + den mindste af d[i − 1][j − 1] (erstat), d[i − 1][j] (slet) og d[i][j − 1] (indsæt).
Et eksempel
For kitten og sitting har tabellen 7 rækker og 8 kolonner. Cellen nederst til højre er 3, og når man læser baglæns derfra, får man: Erstat k med s, behold i, t og t, erstat e med i, behold n, og indsæt g. Fra kitten til sitten, så sittin, så sitting: tre ændringer, og tabellen beviser, at der ikke findes nogen kortere liste.
At læse ændringerne baglæns
Start i cellen nederst til højre, og spørg, hvilken nabo dens værdi kom fra. Hvis bogstaverne er ens, og cellen er lig med naboen oppe til venstre, blev bogstavet bevaret: Gå diagonalt. Hvis den er én mere end naboen oppe til venstre, var det en erstatning; én mere end cellen ovenover, en sletning; én mere end cellen til venstre, en indsættelse. Flere stier kan stå lige, og hver af dem giver en korteste liste af ændringer.
Historie og anvendelser
Levenshtein indførte afstanden i 1965, mens han arbejdede med fejlrettende koder. Tabelmetoden blev offentliggjort af flere, mest kendt af Robert Wagner og Michael Fischer i 1974, så den kaldes ofte Wagner–Fischer-algoritmen. I dag rangerer redigeringsafstande staveforslag, finder navne med tastefejl i databaser, sammenligner DNA- og proteinsekvenser og bedømmer talegenkendelse.
Udforsk den
Åbn appen, og tryk på Trin. De to bogstaver, der sammenlignes, lyser op i overskrifterne; ens bogstaver kopierer den blå celle oppe til venstre, og forskellige bogstaver læser alle tre blå naboer og lægger én til den mindste. Til sidst løber den orange sti tilbage fra hjørnet, og ændringerne vises under tabellen.
Ofte stillede spørgsmål
Er redigeringsafstand en metrik?
Ja. Den er aldrig negativ, den er kun 0 for ens ord, den er den samme i begge retninger, og en omvej via et tredje ord kan aldrig gøre den kortere: d(a, c) ≤ d(a, b) + d(b, c). Det gør den nyttig til at søge efter ord, der ligner hinanden.
Hvad er Damerau–Levenshtein-afstanden?
Redigeringsafstanden med én ekstra ændring: at bytte om på to nabobogstaver. Frederick Damerau fandt i 1964 ud af, at indsæt, slet, erstat og byt tilsammen dækker over 80 % af alle stavefejl. Med ombytninger ligger recieve og receive 1 fra hinanden i stedet for 2.
Kan redigeringsafstand beregnes hurtigere end O(m·n)?
Ikke meget. I 2015 viste Arturs Backurs og Piotr Indyk, at en metode, der tager O(n^(2 − ε)) tid for et eller andet ε > 0, ville modbevise den stærke eksponentialtidshypotese, som de fleste forskere tror på. For ord, der ligner hinanden, er der dog kun brug for et smalt bånd omkring tabellens diagonal.
Hvordan bruges redigeringsafstand til at sammenligne DNA?
Biologer bruger den samme tabel med point i stedet for antal: Match giver point, og erstatninger og huller koster point, der afhænger af bogstaverne. Det er Needleman–Wunsch-algoritmen fra 1970 for hele sekvenser og Smith–Waterman-algoritmen fra 1981 for de stykker, der passer bedst sammen.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv redigeringsafstand