Levenshteinavstånd

Levenshteinavståndet, eller Levenshtein distance, är ett mått på hur lika eller olika två strängar är. Det definieras som det minsta antalet redigeringssteg som krävs för att förvandla en sträng till den andra. Ett redigeringssteg består av insättning, borttagning eller ersättning av ett tecken. Avståndet används för att mäta stavfel, jämföra namn och ord i sökverktyg samt inom textbehandling och bioinformatik för jämförelse av DNA- eller proteinsekvenser.

Historik: Metoden introducerades av Vladimir Levenshtein 1965 och har blivit ett standardmått inom flera områden där likhet mellan strängar behöver kvantifieras.

Beräkning: Den vanligaste beräkningen görs med dynamisk programmering. För två strängar av längderna m respektive n byggs en m+1 gånger n+1 matris d där d[i][j] är avståndet mellan de första i tecknen av den första strängen och de första j tecknen av den andra. Antag att tecknen är a[i-1] och b[j-1]. Kostnaden är 0 om tecknen är lika och 1 annars. Rekursionen är: d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + kost). Startvärdena är d[i][0] = i och d[0][j] = j. Tid är vanligtvis O(mn) och minne O(mn) i standardimplementationer; det finns optimeringar som minskar minnebruket till O(min(m,n)).

Varianter och egenskaper: Damerau-Levenshtein tillåter transposition av närliggande tecken; viktade versioner ger olika kostnader för olika operationer. Levenshteinavståndet uppfyller ofta egenskaperna hos en metrisk avståndsmått (icke-negativt, identitet, symmetri, triangelolikhet), vilket underlättar jämförelser och sökträffar.

Användningar: vanlig i stavningskontroll, fuzzy sökning, automatisk korrigering, OCR-efterbehandling och analys av biologiska sekvenser.