Levenshtein-distanse

I informasjonsteori refererer Levenshtein-distansen mellom to strenger (f.eks. to ordformer) til det minste antallet operasjoner som trengs for å endre den ene strengen til en annen, hvor operasjonene er innsetting, sletting eller erstatning. Levenshtein-distansen har fått navnet sitt etter den russiske forskeren Vladimir Levenshtein, som satte opp mål for redigeringsdistanse i 1965. Levenshtein-distansen er nyttig for å finne ut hvor like to strenger er, og blir brukt bl.a. i retteprogram, men han har også blitt brukt i bioinformatikk for å sammenligne DNA-strenger. I dataprogrammering – og særlig webprogrammering – er Levenshtein-distansen brukt mye i søkemotorer og søkefunksjoner. Man bruker Levenshtein-distansen for å finne resultat som likner på f.eks. søkerens inntasting. Wikipedia, for eksempel, bruker denne funksjonen.

Bakgrunnsstoff

• NIST's Dictionary of Algorithms and Data Structures: Levenshtein Distance
• Levenshtein Distance - Visualisert versjon
• Distance between strings - Levenshtein and Hamming
• Edit Distance Algorithm Demonstration - Visualisert versjon
• Wie funktioniert der Levenshtein-Algorithmus...?

Autoritetsdata