URN_NBN_SI_doc-CKREDCV0

Knjižnica 46(2002)1-2, 111-136 116 2 Optimalni algoritem Za eksperimente, ki so opisani v nadaljevanju, smo uporabili algoritem, ki so ga avtorji (Dimec et al., 1999) preprosto poimenovali Optimalni algoritem, kajti njegov namen je, naj bi v vsakem trenutku oblikoval najbolj optimalen krn. Podrobno sta ga opisala Vilarjeva in Dimec (2000), tu bomo omenili le nekaj najpomembnejših značilnosti. Algoritem sodi v družino algoritmov, ki odstranjujejo pone, natančneje besedne končnice. Deluje po načelu najdaljšega ujemanja, a tako, da poskuša vedno ohraniti najdaljši možni niz znakov, ki nato zastopa oblikoslovne različice se- mantično povezanih besed. Pri najkrajši možni različici namreč prehitro lahko pride do premočnega krnjenja. Dodatna ideja avtorjev je bila, da je potrebno krnjenje bolj prilagoditi strokovnim podjezikom. Iz tega drugega razloga je za delovanje algoritma vedno v začetku potrebna t. i. učna faza, v kateri pridobi- mo nabor krnov, ki izvirajo iz terminologije nekega področja. Tako zgradimo sestavne dele algoritma, ki jih moramo v nadaljnjih postopkih seveda redno dopolnjevati in vzdrževati. V sistemu tako sodelujejo trije seznami krnov: - veljavni krni; - imenski krni; - novi krni. Prvi seznam vključuje optimalne oblike krnov podjezika, v drugem se nahaja- jo krni, ki ne sodijo v podjezik, a so pomembni kot vsebinski predstavniki dokumentov (osebna, geografska imena, kratice…). V tretjem se nahajajo vsi krni, ki nastanejo v postopku, in jih še ni med veljavnimi in imenskimi. Zato se imenuje seznam novih krnov. Delovanje algoritma je naslednje (Vilar in Dimec, 2000): “V nasprotju z algo- ritmi z najdaljšim ujemanjem, Optimalni algoritem načne besedo na koncu. Od desne proti levi išče pare soglasnik-samoglasnik. Pri vsakem paru opravi popolni postopek krnjenja – odrez končnice, obdelavo soglasniških parov in uporabo pravil za popravljanje krnov. Krn, ki nastane, sistem poskuša najti v seznamih veljavnih in imenskih krnov. Če ga najde, je postopek opravljen, si- cer poišče naslednji par soglasnik-samoglasnik v smeri proti začetku besede in ponovi krnjenje. Algoritem torej deluje iterativno, z vedno daljšimi in daljšimi končnicami.” Če se iskanje krna v seznamih veljavnih in imenskih krnov nikoli ne izteče pozitivno, je rezultat zadnji krn, ki je nastal v postopku.” Slika 1 na simboličen način predstavlja delovanje Optimalnega algoritma.