Levenshtein-distanse

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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]