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
 
  Koda programa  
 

Spodaj sem podrobneje opisal pomembnejši del programske kode. Na dnu pa je prikazan del seznama vzorcev - slovar. Izgled programa v delovanju in nekaj primerov iskanih besed najdete tukaj.

Programiranje

Slika1: V tem delu programske kode inicializoramo spremenljivko "razdelja", ki ji priredimo vrednost 100, da je po pregledu prve besede Levenshteinova razdalja takoj manjša. Inicializiramo tudi spremenljivko "tekoca", ta vsebuje vrednost trenutno preverjene besede. Program vsebuje zanko while, ki teče dokler ne zmanjka besed v slovarju. Slovar je sestavljen tako, da je vsaka beseda napisana v svoji vrstici. Pomembno je, da na koncu seznama kurzor postavimo v novo prazno vrstico, v nasprotnem primeru program razume zadnjo besedo kot neskončno dolgo. Sledi še izpis poročila Levenshteinove razdalje.

Programiranje2

Slika2: V tem delu vnesemo v prvo vodoravno in navpično vrstico matrike zaporedne številke (začnemo z 0 in štejemo do števila dolžine besede). Matriko izdelamo s pomočjo Matrika.h. V nadeljevanju sledi določevanje "cen" za brisanje, vrivanje in zamenjavo črk v besedi. S pomočjo podprograma Funkcija.cpp določimo minimalno možno ceno med besedama. Spodnja, desna celica matrike nam poda Levenshteinovo razdaljo za trenutno obdelano besedo.

Vzorci.txt

Slika3: Na sliki je prikazan del seznama vzorcev - slovar, iz katerega program pobira besede in preverja Levenshteinovo razdaljo.
Prikazana je tudi zgoraj omenjena, zadnja, prazna vrstica, ki je potrebna za pravilno delovanje programa.

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

 

    SLOhosting.com priporoča :