Damerauova–Levenštejnova vzdálenost je v teorii informace a matematické informatice metrika řetězců pojmenovaná po Fredericku J. Damerauovi a Vladimiru Iosifoviči Levenštejnovi. sloužící k měření editační vzdálenosti mezi dvěma řetězci (nebo posloupnostmi). Je to minimální počet operací (vložení znaku, smazání znaku, nahrazení jednoho znaku jiným nebo prohození dvou sousedních znaků), které jsou nutné k přeměně jednoho řetězce na druhý.

Na rozdíl od Levenštejnova vzdálenost umožňuje prohození dvou sousedních znaků.

Demerau ve své průkopnické práci uvedl, že při zkoumání pravopisných chyb v systému pro vyhledávání informací bylo více než 80 % z nich výsledkem jediné chyby jednoho ze čtyř typů. Damerauova práce zohledňovala pouze pravopisné chyby, které bylo možné opravit maximálně jednou editační operací. Ačkoli původním záměrem bylo měřit vzdálenost mezi lidskými pravopisnými chybami za účelem vylepšení aplikací, jako jsou korektory překlepů, Damerauova–Levenštejnova vzdálenost se používá také v biologii k měření variace mezi sekvencemi proteinů.

Odkazy

Reference

Literatura

Související články Ispell – Nabízí opravy, které mají Damerauovu–Levenštejnovu vzdálenost 1

Kategorie:Teorie informace Kategorie:Dynamické programování