>> Implementacija >> Implementacija lematizacije

Algoritam lematizacije treba za danu riječ vratiti njenu lemu i MSD (morfosintaktički deskriptor). Lematizacijski rječnik sadrži uređene trojke: (oblik, lema, MSD). Na primjer, rječnik može sadržavati i sljedeće trojke:

• (sveučilišta, sveučilište, N=npa)
• (sveučilišta, sveučilište, N=npg)
• (sveučilišta, sveučilište, N=npn)
• (sveučilišta, sveučilište, N=npv)
• (sveučilišta, sveučilište, N=nsg)

Riječ sveučilišta ima samo jednu moguću lemu, sveučilište. Javlja se kao imenica srednjeg roda u genitivu (Noun=neuter plural genitiv), nominativu i vokativu množine, te u genitivu jednine. Za lematizaciju hrvatskog jezika korišten je automatski generiran morfološki rječnik opisan u [20], a za lematizaciju engleskog jezika korišten je javno dostupan morfološki rječnik [21].

Problem se javlja pri izboru strukture u koju će se zapisati rječnik, tj. uređene trojke rječnika. Na primjer, hrvatski rječnik koji je korišten u sustavu sadrži preko 500 tisuća različitih oblika riječi, oko 700 tisuća različitih parova oblika (oblik, lema), te oko 3,1 milijun uređenih trojki. Veliki broj različitih riječi i uređenih trojki postavlja nemale memorijske zahtjeve. Kako je potrebna i brza pretraga rječnika, tj. za brzo izabiranje svih trojki čiji je prvi element jednak zadanoj riječi, problem odabira strukture nije trivijalan. Ako se koristi jednostavnija struktura podataka (raspršeno adresiranje po prvoj riječi) potrebne su vrlo velike količine memorije.

Možemo primijetiti da je za potrebe lematizacije dovoljna struktura kojom bi se učinkovito mogli naći svi nizovi znakova kojima je zadani niz znakova prefiks. Svaka uređena trojka (oblik, lema, MSD) dodavala bi se u strukturu kao jedan niz znakova, s elementima odvojenim zarezom (pretpostavljamo da nijedan element trojke ne sadrži zarez). Na primjer ta bi struktura sadržavala niz znakova "sveučilišta,sveučilište,N=npa". Traženjem svih nizova znakova kojima je prefiks niz znakova "sveučilišta," mogu se naći sve leme i MSD-ovi riječi "sveučilišta". Radi lakšeg zapisa od sada ćemo upotrebljavati riječ umjesto niz znakova.

Ostaje pitanje načina spremanja strukture koja bi omogućila spremanje skupa riječi uz uvjet da se mogu učinkovito naći sve riječi kojima je zadana riječ prefiks. Traženu strukturu možemo jednostavno zapisati u obliku nedeterminističkog konačnog automata koji prihvaća samo skup riječi koje sadrži rječnik (slika 14). Ako je potrebno lematizirati riječ w, tada je rezultat lematizacije skup svih riječi koje automat prihvaća od skupa stanja ?(?(S,w),','), gdje je S početno stanje. Na primjer, ako se želi lematizirati riječ vode, rezultat lematizacije jest skup riječi { vod, voda, voditi }.

Slika 14. Nedeterministički automat koji prihvaća sljedeće riječi (nizove znakova): "voda,vod", "voda,voda", "vode,vod", "vode,voda", "vode,voditi". MSD-ovi su izostavljeni radi jednostavnosti.

Odabirom nedeterminističkog automata kao strukture nisu se smanjili memorijski zahtjevi, a pretraživanje je neučinkovito jer je ?(?(S,w),',') skup stanja. Brže pretraživanje, kao i smanjenje memorijskih zahtjeva postiže se pretvaranjem rječnika iz nedeterminističkog automata u deterministički, tj. u automat u kojem ne postoji stanje s dva prijelaza označena istim završnim znakom (slika 15). Možemo primijetiti da se na ovaj način iskoristila činjenica da veliki broj riječi u rječniku ima zajedničke prefikse koji su neznatno kraći od samih riječi.

Slika 15. Pretvaranjem nedeterminističkog automata sa slike 14 u deterministički znatno se smanjio broj stanja. Rezultati su vidljiviji na stvarnim rječnicima koji sadrže veliki broj vrlo sličnih riječi.

Ipak, još nije iskorištena činjenica da mnogo riječi u rječniku dijeli zajedničke sufikse, pogotovo u slučaju kada se bilježi MSD riječi (skup svih MSD-ova znatno je manji od broja riječi). Problem se može djelomično riješiti minimalizacijom automata sa slike 15 kako je prikazano na slici 16.

Slika 16. Minimalizacijom automata sa slike 15 dodatno se smanjuje broj stanja.

Dodatno smanjenje broja stanja postiže se posebnim kodiranjem druge riječi uređene trojke (oblik, lema, MSD). Druga riječ može se dobiti ispuštanjem zadnjih k znakova prve, te dodavanjem proizvoljnog niza znakova na kraj. Ako se broj k kodira kao npr. 0='A', 1='B', itd., onda se npr. trojka (sveučilišta, sveučilište, N=npa) može zapisati kao "sveučilišta,Be,N=npa" (riječi sveučilišta zamijenjen je zadnji znak a sa znakom e).

Slika 17. Umjesto nizova znakova "voda,vod", "voda,voda", "vode,vod", "vode,voda", "vode,voditi" u automat se spremaju nizovi znakova u kojima je lema kodirana prema obliku: "voda,B", "voda,A", "vode,B", "vode,Ba", "vode,Biti".

Svako stanje može se predstaviti kao skup prijelaza. Svi prijelazi mogu se zapisati u listu na način da svako stanje sadrži sve prijelaze u nekom intervalu. Ako se informacija o tome je li sljedeće stanje završno ili nezavršno doda svakom prijelazu, te ako se označi zadnji prijelaz nekog stanja, onda nije potrebno nigdje eksplicitno držati informacije o stanjima, tj. ne mora se pamtiti interval liste prijelaza za svako stanje. Nadalje, pamteći automat na ovaj način tijekom minimalizacije dodatno se može smanjiti ukupni broj prijelaza. Na tablici 1 vidi se konačan zapis automata.

Tablica 1. Automat sa slike 17 zapisan je u obliku liste prijelaza. Stanje koje počinje s prijelazom broj 0 nema niti jedan prijelaz.

Svaki prijelaz može se zapisati u 4 okteta – 1 oktet za završni znak, 2 bita za zastavice, te 22 bita za redni broj sljedećeg prijelaza. Time je veličina automata ograničena na otprilike 4000000 prijelaza, što se pokazuje kao dovoljno veliko ograničenje. Na primjeru hrvatskog rječnika, automat se može smanjiti s oko 70 milijuna stanja i prijelaza na oko 105 tisuća stanja i 220 tisuća prijelaza. Veličina takvog automata u radnoj memoriji je oko 220K • 4B=880 KB.

Kako se rječnik ne generira niti ne mijenja za vrijeme izvršavanja programa, vrijeme izvršavanja minimalizacije nije toliko bitno. Praktičan problem nastaje s radnom memorijom potrebnom za izvršavanje algoritma minimalizacije. Jednostavniji algoritam koji drži cijeli početni rječnik u memoriji zahtijeva preko 500 MB radne memorije, pa je pravo rješenje inkrementalni algoritam [16] koji održava minimalni automat nakon dodavanja svake riječi.

Mali memorijski zahtjevi ovako zapisanog rječnika omogućavaju dodavanje velikog broja novih riječi, te lakšu i bržu zamjenu rječnika za vrijeme izvršavanja programa.