Redigerer Levenshtein-distanse

{{Kildeløs}}
I [[informasjonsteori]] refererer '''Levenshtein-distansen''' mellom to [[Streng (informatikk)|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 [[Stavekontroll|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 ==

* [https://xlinux.nist.gov/dads/HTML/Levenshtein.html NIST's Dictionary of Algorithms and Data Structures: Levenshtein Distance]
* [http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html Levenshtein Distance - Visualisert versjon]
* [http://www.cut-the-knot.org/do_you_know/Strings.shtml Distance between strings - Levenshtein and Hamming]
* [https://www.cs.unm.edu/~luger/ai-final/code/editdist.html Edit Distance Algorithm Demonstration - Visualisert versjon]
* [http://www.levenshtein.de/ Wie funktioniert der Levenshtein-Algorithmus...?]

{{Autoritetsdata}}

[[Kategori:Informasjonsteori]]
[[Kategori:Algoritmer]]