Levenshteinavstånd
Levenshteinavståndet är inom informationsteorin och datavetenskapen ett mått på hur stor skillnaden är mellan två strängar av symboler. Avståndet beräknas som summan av det antal raderingar, infogningar och substitueringar av tecken som krävs för att transformera den ena strängen till den andra. Det har fått sitt namn efter Vladimir Levensjtejn, som beskrev avståndet 1965.[1]
Levenshteinavståndet har många tillämpningar, inte minst sådana där likheten mellan två strängar eller ord betraktas, som i stavningskontroller.
Avståndet går att generalisera, till exempel så att olika raderingar, infogningar och substitueringar ger olika kostnad. I en stavningskontroll skulle detta kunna innebära att bokstäver som ligger nära varandra på tangentbordet har lägre kostnad. På ett qwerty-tangentbord skulle detta medföra att det felstavade ordet aoa ligger närmare apa än ana, och apa skulle därför föreslås som rättstavat ord.
Referenser[redigera | redigera wikitext]
- ^ В.И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845–848.
Se även[redigera | redigera wikitext]
Levenshtein distance (engelska) på Wikibooks.
