Informatika v avtomatizaciji
Levenshteinova razdalja med dvema nizoma znakov

Univerza v Ljubljani
Fakulteta za elektrotehniko

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

V sklopu laboratorijskih vaj smo pri predmetu Informatika v avtomatizaciji opravljali projektno delo. Na razpolago smo imeli več izbirnih projektov/vaj. Izbral sem si 9. vajo z naslovom: Levenshteinova razdalja med dvema nizoma znakov. Projekt spada v razdelek razpoznavanja vzorcev, nizov znakov, s prileganjem. Za izvedbo programa smo lahko sami izbrali programski jezik (npr.: java, C/C++/C#, python) ali pa programirali v okolju Matlab. Odločil sem se za realizacijo v programskem jeziku C++, za izdelavo programa pa sem uporabil Microsoft Visual C++, ker je zelo enostaven za uporabnika. Na vajah smo dobili osnovna navodila za sestavo projekta v izbranem programerskem okolju.

Naloga zahteva program, za realizacijo razvrščanja nizov znakov s prileganjem s pravilom najbližjega soseda 1-NN, pri čemer naj se uporabi Levenshteinovo razdaljo med nizi znakov. Program je potrebno preizkusiti za podani primer učne množice dveh razredov s po štirimi nizi.

U1 = { x i S a, x i S e, x i S i, x i S O }
U2 = { p i s a t i, p i S e, p i S i, p i s a U }

• Program naj prebere vzorce iz datoteke, zapisane v predpisani obliki.
• Razvrsti naj niz x1= x i s a s pravilom najbližji sosed, 1-NN v enega od dveh razredov, pri čemer uporabi Levenshteinovo razdaljo med nizi simbolov.
• Program dopolnimo tako, da bo deloval na večjih množicah besed. Dodatno datoteko z nizi pridobimo/tvorimo sami. Množica mora vsebovati vsaj tisoč besed. Program mora med podano množico besed poiskati tisto, ki je najbližje vtipkani besedi.

Program je možno prikazati še v obliki grafičnega prikaza grafa operacij poravnave dveh izbranih nizov znakov, kar je bila naloga za višjo oceno.

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

 

    SLOhosting.com priporoča :