Levenshtein-distanse
 | Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. |
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[rediger | rediger kilde]
- 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...?