Informatika v avtomatizaciji
Levenshteinova razdalja med dvema nizoma znakov

Univerza v Ljubljani
Fakulteta za elektrotehniko

Logo FE
 
Tipka1 Opis naloge
Tipka2 Teoretično ozadje
Tipka2 Zgodovina
Tipka2 O programskem jeziku
Tipka2 Koda programa
Tipka2 Delovanje programa
Tipka2 Komentar
Tipka2 Viri
   
  Logo LUKS
 
  Teoretično ozadje  
 

V računalništvu je Levenshteinova razdalja (LR/LD) mera podobnosti med dvema nizoma. Označimo prvi niz z x in drugega z y. V tem primeru je Levenshteinova razdalja minimalno število brisanj, vrivanj in zamenjav, ki so potrebne, da prvi niz pretvorimo v drugega. Večja kot je Levenshteinova razdalja, bolj se niza razlikujeta.

Levenshteinova razdalja je poimenovana po ruskem znanstveniku Vladimiru Levenshteinu, ki je leta 1965 razvil alogritem za izračun tako definirane razdalje med dvema nizoma. Levenshteinova razdalja se uporablja na mnogih področjih računalništva, na primer: preverjanje črkovanja, prepoznavanje govora, analiza DNK in ugotavljanje plagiatorstva.

 
     
| © 2010 Peter Škrab | Informatika v avtomatizaciji | pjero_s@hotmail.com |

 

    SLOhosting.com priporoča :