KA AUTOMATSKOJ SINTAKSNOJ ANALIZI REČENICE NA SRPSKOM JEZIKU

1. UVOD

1.1. O formalnim jezicima i gramatikama

Sintaksa definiše ustrojstvo u okviru rečenice jednog jezika. Jezik se, u tom smislu, može definisati kao skup svih sintaksno ispravnih rečenica obrazovanih na osno-vu dozvoljenog skupa reči. Ovo ustrojstvo može se opisati pravilima, koja organizujemo u gramatike. Postoji, dakle, samo jedna sintaksa za svaki jezik, a moguće ju je opisati mnoštvom različitih gramatika. Težnja je da se jezik, kao beskonačan skup, opiše ko-nač-nim brojem gramatičkih pravila [2].
Šezdesetih godina ovog veka, Noam Chomsky defi-nisao je transformaci-ono-generativne gramatike, čiji je osnovni princip da se svaka rečenica može generisati iz početnog simbola R koristeći konačno mnogo pravila zamena (produkcija) i konačan broj transformacija koje se primenjuju na stabla izvođenja. Uveo je koncepte terminalnih simbola - onih koji se direktno mogu javiti u rečenici, i neterminalnih - onih koji mogu da se prevedu u terminalne i druge neterminalne simbole, kao i njihove grupe. Primera radi, terminalni simboli mogu biti reči poput pas i laje, dok bi neterminalni simboli mogle biti imenička sintagma ili predloška fraza. Pravila produkcije defi-nišu koje se kombinacije termi-nal-nih i neterminalnih simbola mogu prevesti u koje druge, i postavljanjem određenih restrikcija na oblike tih pravila definisana je tzv. hijerarhija Chomskog [4]. Za opisivanje prirodnih jezi-ka najčešće se koriste gramatike tipa II u hijerarhiji Chomskog, tzv. kontekstno slobodne gramatike (engl. context-free grammars), čija su pro-duk-ciona pravila isključivo oblika

A -> alfa

pri čemu A označava neterminalan simbol, a ? bilo koju kombinaciju terminalnih i neterminalnih simbola. Ovaj tip gramatika je dovoljno jednostavan, ali i dovoljno moćan -- pomoću njega je moguće opisati koncepte prirodnog jezika kao što su nizanje i ugnežđivanje. Osim toga, problem pripadanja je za kontekstno slobod-ne jezike algoritamski odlučiv, što znači da uvek postoji algoritam koji u konačnom vremenu daje odgovor na pitanje da li data rečenica pripada jeziku opisanom datom gramatikom. Problem određivanja niza pravila koja su primenjena za generisanje date rečenice naziva se raščlanjivanje. Algoritam za raščlanjivanje bi, dakle, na osnovu rečenice Pas laje na decu i date gra-ma-tike trebalo da rekonstruiše sintaksno stablo prika-zano na slici 1.

Slika 1. Primer stabla izvođenja

Ovde treba pomenuti i problem dvosmislenosti, odnosno, mogućnosti da se na osnovu iste gramatike generiše više različitih stabala izvođenja iste rečenice, pri čemu to može dovesti i do semantičke dvosmisleno-sti. Primera radi, ako se u rečenici Vidim čoveka bez naočara predloška fraza bez naočara protumači kao modifikativni dodatak glagola vidim, rečenica dobija potpuno drugo značenje u odnosu na slučaj da se ista predloška fraza protumači kao adverbijalni dodatak uz imenicu čoveka. U prvom slučaju, onaj koji vidi je bez naočara, a u drugom onaj koji je viđen. Treba, pored toga, naglasiti i da kod čoveka rečenica kao što je Vidim čoveka bez šešira ne bi izazvala sintaksnu dvosmisle-nost, dok kod računara bî, osim ukoliko na neki način nije naučen da se može videti uz pomoć naočara.
Složenost prirodnih jezika je mahom tolika da oni izmi-ču mogućnosti potpunog matematiziranja. Uz veo-ma moćan skup produkcionih pravila (ali ne preobiman, jer njegova veličina i složenost direktno utiču na trajanje raščlanjivanja), potrebno je, da bi se algoritam što više približio praktičnoj upotrebi, pre svega posedovati i kvalitetan rečnik prirodnog jezika sa označenim morfo-loškim kate-go-rijama reči. Sledeći korak bio bi uključiti podatke o rekciji pojedinih vrsta reči (npr. može se biti žedan nečega, ali veran nečemu), kao i nekim jednostav-nijim semantičkim konceptima. Sveobuhvatno rešenje pro-ble-ma bilo bi naučiti računar da razmišlja kao čovek, ali taj problem je još uvek daleko od rešenja.

---

1.2. Sintaksna analiza i govorne tehnologije

Uloga sintaksne analize u automatskoj sintezi govo-ra na osnovu teksta jeste u otklanjanju nedoumica u pogledu toga koju leksičku reč, sa kojim vrednostima morfoloških kategorija, predstavlja dati niz grafema. Posmatrajmo sledeće dve rečenice:

Lasta leti na jug.
Lasta leti odlazi na jug.

Reč leti je u prvoj glagol a u drugoj prilog, i drukčije se naglašava u izgovoru, pa bi sistem za sintezu govora koji ne vrši kompletnu sintaksnu analizu, već se oslanja samo na akcenatski rečnik, mogao pogrešiti u izgovoru. Štaviše, sistem koji se oslanja na jednostavnije seman-tičke kon-cepte opisane u prethodnom odeljku (npr. lasta je ptica, pa prema tome najverovatnije leti) sasvim sigurno bi pogrešio u drugoj rečenici.
Sistem za automatsko prepoznavanje govora nalazi se pred još većom preprekom. On ima zadatak da izvrši i leksičku segmentaciju, koja često nije jedno-značna. Na primer, ako je prepoznati niz fonema [lasta-leti-najug], on bi se leksički mogao segmentirati i na sledeći način: lasta | letina | jug, i tek bi sintaksna analiza presudila u korist prave segmentacije. Pored toga, i sistem za automatsko prepoznavanje govora može se osloniti na već pomenuti akcenatski rečnik, pa bi mogao iskoristiti i znanja o tome kako bi ispravno trebalo akcentovati rečenicu koja je rezultat sintaksne analize, te koliko se to poklapa sa akcentuacijom koju je pri izgovoru imao govornik. Ovo se može pokazati korisnim čak i za leksičku segmentaciju, jer se značajan deo sintaksnih dvosmislenosti opisanih u prethodnom odeljku može razlikovati po akcentuaciji. Posmatrajmo četiri ra-zli-čite leksičke segmentacije (od mnoštva mogućih) koje odgo-varaju prepoznatom nizu fonema [brânkaleči-ne?-pre-bol-nera?ne]:

Prva varijanta je sintaksno ispravna, ali njena akcen-tu-acija ne odgovara prepoznatoj. Kod druge varijante je obrnuto - akcenatska struktura odgovara onoj koju je upotrebio govornik, ali rečenica nije sintaksno ispravna. U trećoj varijanti niti je rečenica sintaksno ispravna, niti je akcenatska struktura odgovarajuća. Jedino je četvrta varijanta ispravna po oba kriterijuma. Dakle, u ovom slučaju bi sistem za prepoznavanje govora koji je u stanju da prepozna i akcenatsku strukturu, oslanja se na akcenat-ski rečnik i sintaksnu analizu, doneo pravu odlu-ku. Situacija je u praksi, naravno, znatno složenija, jer sistem za prepoznavanje govora po pravilu ne donosi odluku o prepoznatim fonemima odmah, već operiše po-dacima o verovatnoći prepoznavanja svakog od njih, a isto se odnosi i na prepoznavanje pojedinih tipova akce-nata, ukoliko je ono uopšte predviđeno.

---

2. GRAMATIKA I ALGORITMI ZA RAŠČLANJIVANJE

2.1. Gramatika

Isključivo za potrebe poređenja algoritama za raščla-njivanje u pogledu brzine, definisan je sledeći, veoma uprošćen spisak produkcionih pravila određenog, uskog skupa rečenica srpskog jezika, u skladu sa zahtevima kontekstno-slobodne gra-matike:

gde oznaka "|" služi za kraći zapis više pravila u okviru jednog, a R je početni neterminalni simbol koji ozna-čava rečenicu. Ovom prostom gramatikom mogu se generisati rečenice poput Pas laje na decu, ali isto tako i Mali ali opasan pas laje na decu i prolaznike a kiša pada bez prestanka, pa i znatno širi skup rečenica proizvoljno složene strukture. Pod složenošću strukture rečenice ovde se podrazumeva broj primenjenih pravila u njenoj konstrukciji, ali je, naravno, dozvoljeno ponav-ljati primenu istih pravila.

---

2.2. Backtracking algoritam

Backtracking algoritam je jedan od najstarijih, naj-po-zna-tijih i najjednostavnijih algoritama za raščlanjiva-nje. Pripada klasi usmerenih bottom-up algoritama, što znači da polazi od line-arne strukture rečenice u terminalnom obliku, analizira terminalne simbole na koje sukcesivno nailazi i pokušava da ih kombinuje u neterminalne simbole. Dozvoljeni koraci ovog algoritma su prihvata-nje novog simbola (nove reči) i primena pravila na već prihvaćene simbole. Ukoliko su svi simboli prihvaćeni, a primenom pravila se nije stiglo do neterminalnog simbola R, znači da su neka pravila bila greškom primenjena, kada je umesto toga trebalo primeniti neka druga pravila ili prihvatiti novi simbol. Zato ovaj algori-tam uvek ume da se vrati na mesto poslednje potenci-jalne greške i da isproba sledeću mogućnost. Back-trackingom se, dakle, sigurno nailazi na rešenje ako ono postoji, ali se pre toga najčešće mora prevaliti veoma dug put. Može se uspostaviti analogija između raščlanji-vanja rečenice backtracking algoritmom i traženja izlaza iz lavirinta, kao što je prikazano na slici 2. Pri tome se algoritam ne mora zaustaviti kad naiđe na jedno rešenje, već se može modifikovati tako da nađe sva moguća rešenja.

Slika 2. Analogija sa backtracking algoritmom
(a) traženje jednog rešenja, (b) traženje svih rešenja

Sporost ovog algoritma u najvećoj meri je posledica činjenice da on dolazi u situaciju da donosi pogrešne odluke, a da to otkriva tek mnogo kasnije. Osim toga, za razliku od kretanja u prikazanom lavi-rin-tu, kod back-tracking algoritma se mnogo puta mora preći isti put. Razlog tome je što se pri vraćanju unazad vrlo često raski-daju sintaksne strukture koje će kasnije morati ponovo da budu konstruisane. Drugim rečima, algo-ri-tam neće upamtiti da je određena grupa terminal-nih simbola mogla da se objedi-ni u jedan ne-ter-mi-nalni simbol u trenutku kad poništava pravilo koje se na to odnosi, već će svaki sledeći put morati ponovo sve da ispituje. Zbog svega ovoga, algoritam radi u eksponencijalnom vreme-nu, što ga čini primenljivim samo za rečenice relativno male dužine.

---

2.3. CYK algoritam

U ovom odeljku biće opisan metod do kog su, neza-vi-sno jedan od drugog, došla trojica istraživača, J. Cocke, D. H. Younger i T. Kasami, po kojima je i dobio ime. Algoritam se odvija u dve faze - u prvoj fazi, koja se još naziva i faza prepoznavanja, određuje se koji neterminalni simboli mogu da generišu koje podnizove reči u okviru polazne rečenice. Rezultat ove faze je od-go-vor na pitanje da li polazna rečenica pripada jeziku koji generiše data gramatika. U drugoj fazi određuju se sva stabla izvođenja [1].
Na primeru rečenice Pas laje na decu, faza prepo-znavanja odvijala bi se na sledeći način. Prvo bi se za svaki terminalni simbol utvrdilo iz kojih neterminalnih simbola može da se dobije, pa bi se tako utvrdilo, primera radi, da se pas dobija iz simbola IM, a preko IM indirektno i iz simbola IM_SINT, a laje iz simbola GL i indirektno iz GL_SINT. Zatim bi se analizi-ralo iz kojih se neterminalnih simbola mogu dobiti dvočlani podni-zovi polazne rečenice, na osnovu već dobijenih rezul-tata. Primera radi, podniz pas laje mogao bi se dobiti iz neterminalnog simbola R, jer postoji pravilo R -> IM_SINT + G_SINT, a već smo videli da se pas može dobiti iz IM_SINT, a laje iz G_SINT. Na sličan način analiza se sprovodi za sve podnizove polazne rečenice, zaključno sa samom rečenicom, kao najdužim podni-zom same sebe. Ukoliko se pokaže da ju je moguće generisati iz simbola R, odgovor na pitanje da li je rečenica sintaksno ispravna je potvrdan. Celokupan tok CYK prepoznavanja prikazan je u tabeli 1.

Tabela 1. CYK prepoznavanje

U praktičnoj implementaciji algoritma druga faza nije ni potrebna jer ako dopustimo ponavljanje sim-bola u poljima i zajedno sa svakim netermi-nalnim sim-bo-lom u tabeli pamtimo i parcijalno stablo izvođenja koje je do njega dovelo, tada ćemo u posled-njem polju tabele dobiti onoliko simbola R koliko je uspešnih izvo-đenja pronađeno, i sva izvođenja biće već na raspo-laganju.
Ovaj algoritam bi po samoj konstrukciji morao raditi u polinomijal-nom vremenu, to jest, brže od backtrack-ing algoritma. Može se, konkretno, pokazati da CYK algo-ritam radi u vremenu O(n3). U slučaju da je grama-tika prevedena u tzv. normalnu formu Chomskog (engl. CNF - Chomsky Normal Form), s pravilima oblika:

1. A->BC
2. A->a

odnosno, gde jedan neterminalni simbol može da pro-izve-de tačno dva neterminalna simbola ili tačno jedan terminalni simbol, CYK algoritam se može implemen-tirati mnogo efikasnije. U slučaju konkretne gramatike, potrebno je eliminisati pravila tipa A->B i A->BCD, što se može izvesti relativno jednostavno.

---

3. EKSPERIMENT

3.1. Polazne postavke

Cilj eksperimenta je bio testiranje brzine rada back-tracking i CYK algoritma, pri različitim dužinama ulaz-ne rečenice, za istu gramatiku. Kod backtracking algo-rit-ma je posmatrano vreme posle kog dolazi do prvog rešenja, kao i vreme posle kog završava pretragu našav-ši sva rešenja. Kod CYK parsera ta dva vremena su prakično ista. Posmatrane su rečenice dužine od 6 do 30 reči, generisane tako što je na osnovnu rečenicu Pas laje na decu i prolaznike (dužine 6) potreban broj puta doda-to a kiša pada. Nisu korišćene slučajno generisane rečenice, iz razloga što bi, pogotovo za veće dužine, bio znatan broj rečenica koje nije moguće raščlaniti datom gramatikom (na primer, bilo koja u kojoj se bilo gde javljaju dva uzastopna predloga ili dva uzastopna vezni-ka). Na takvim rečenicama CYK parser bi znatno brže završio postupak, jer broj operacija kod njega direktno zavisi od broja dobijenih međurezultata u prethodnom koraku, dok bi backtracking algoritam morao, bez obzira na to, da prođe kompletnu pretragu da bi utvrdio da nema rešenja (mada bi i on ređe dolazio u priliku da "zaluta").

---

3.2. Rezultati

Rezultati eksperimenta prikazani su u tabeli 2. i na grafiku na slici 3.

Tabela 2. Rezultati eksperimenta

Slika 3. Grafički prikaz rezultata eksperimenta

Eksperiment pokazuje mnogo veću efikasnost CYK algoritma u odnosu na backtracking. Efikasnija ili manje efikasna računarska implementacija algoritama, kao i uprošćavanje ili usložnjavanje gra-matike, imali bi utica-ja samo na verti-kal-no pomeranje prika-zanih krivih, a ne i na njihov nagib, tako da bi u svakom slučaju bilo moguće naći dužinu reči na kojoj će CYK algoritam biti unapred zadat broj puta efikasniji od backtracking algo-ritma, ali, nažalost, i dužinu na kojoj će čak i CYK algoritam biti neprihvatljivo spor.
Da bi gramatika koliko-toliko opisala prirodan jezik, ona će, jasno, morati da se znatno usložni, i pre svega uzme u obzir morfološke kategorije, koje su ovde zane-ma-rene. To je imalo direktan uticaj i na moć gramatike da razdvaja sintaksno ispravne od sin-taksno neispravnih rečenica. Primera radi, za rečenicu Pas laje na decu i prolaznike a kiša pada dužine 9, bila su nađena dva stabla izvođenja, ali samo je jedno od njih odgovaralo stvarnom stablu izvođenja te rečenice u srpskom jeziku. Drugo stablo je sadržalo "imeničku sintagmu" prolaz-nike a kiša, koja, gledajući strogo po pravilima nave-dene gramatike jeste imenička sintagma, ali to, na-rav-no, ne odgovara našem jezičkom osećaju zbog nesla-ganja padeža i korišćenja rastavnog veznika a, koji povezuje isključivo rečenice, između dve imenice.
CYK algoritam je znatno pogodniji za primene ve-zane za govorne tehnologije zbog svoje efikasnosti, ali i zato što, primera radi, omogućava da se vrši raščlanjiva-nje ne samo pojedinačne rečenice, već i istovremeno raščlanjivanje skupa rečenica u kojima figurišu reči koje se isto pišu ali na osnovu zapisa nije moguće odrediti njihovu sintaksnu kategoriju. Osim toga, ovaj algoritam bi bilo moguće postaviti i na probabilističkim osnova-ma. Naime, pojava rečenice Pas laje na decu verovat-nija je od pojave rečenice Na decu laje pas, mada su obe rečenice sintaksno ispravne. Ipak, intuitivno je jasno da ih ne treba potpuno ravnopravno tretirati, i da bi se taj problem mogao rešiti dodeljivanjem jedinstvene vero-vatnoće svakom produkcionom pravilu. To, opet, znači da bi u toku raščlanjivanja moglo da se vrši i odbaciva-nje premalo verovatnih mogućnosti.

---

4. ZAKLJUČAK

U radu su upoređena dva algoritma za raščla-njivanje rečenice srpskog jezika na osnovu date grama-tike, i utvrđeno je da je CYK algoritam, pored mnogih dobrih strana u pogledu primene u okviru govornih tehnologija, daleko efikasniji od backtracking algoritma. Međutim, i vreme rada CYK algoritma ipak prebrzo raste sa duži-nom rečenice da bi se bez ikakvih modifikacija mogao koristiti. Najbolje bi bilo opredeliti se za neki od još efika-snijih algoritama, sa vreme-nom rada bližim O(n), i razmotriti mogućnosti njegove adaptacije specifičnim potrebama govornih tehnologija. Ne treba zaboraviti ni da vreme rada algoritma u izvesnoj meri zavisi i od gramatike, te da gramatika napisana isključivo tako da najprirodnije opi-še prirodni jezik verovatno neće dopu-štati raščlanjivanje u linearnom vremenu, te da je i nju potrebno donekle linearizovati [1].

---

LITERATURA

[1] D. Grune, C. Jacobs: Parsing Techniques: A Practical Guide, Ellis Horwood ltd., Chichester, 1990.
[2] Rozália Sz. Madarász, Siniša Crvenković: Uvod u teoriju automata i formalnih jezika, Prirodno-matematički fakultet - Novi Sad, MP "STYLOS", 1995.
[3] T. Dutoit: An Introduction to Text-to-Speech Synthesis, Kluwer Academic Publishers, Dordrecht/ Boston/London, 1997.
[4] N. Chomsky: Syntactic structures, Mouton, The Hague, 1975.
[5] P. Mrazović, Z. Vukadinović: Gramatika srpsko-hrvatskog jezika za strance, Izdavačka knjižarnica Zorana Stojanovića, Sr. Karlovci, 1990.

ABSTRACT

This paper is a step towards an automatic syntax analysis of sentences in Serbian language, and it describes and compares two parsing algorithms used on a subset of Serbian language described by a formally introduced grammar. The paper also discusses require-ments placed upon parsing algorithms to be used within speech synthesis and speech recognition systems.

Preuzeto sa http://www.ftn.ns.ac.yu/dogs/dogs2004.htm