>> Implementacija >> Unutarnja struktura

Unutarnja reprezentacija učitanog dokumenta od ključne je važnosti za učinkovitost sustava.

Postavljajući brzinu pretrage po strukturi te što manje zahtjeve za memorijom kao prioritete, razvijena je specifična struktura podataka koja je temelj čitavog sustava [13].

Slika 10. Jednostavan primjer ulazne XLM datoteke.

Za objašnjenje unutarnje strukture poslužit ćemo se jednostavnim primjerom, danim na slici 10. Ulazna datoteka sastoji se od samo jednog elementa zaglavlje, kojeg sačinjavaju dva podelementa naslov i podnaslov. Grafička apstrakcija unutarnje strukture podataka koja bi se izgradila unutar sustava nakon učitavanja tog dokumenta prikazana je na slici 11.

Slika 11. Apstrakcija unutarnje strukture podatka izgrađene nakon učitavanja primjera XML dokumenta sa slike10.

Sama struktura XML dokumenta čuva se implementacijom varijacije standardnog stabla na principu prvo dijete – sljedeći brat. Za svaki čvor u stablu čuvaju se dvije informacije koje se odnose na strukturu :

• Pokazivač na prvi čvor podređen promatranom čvoru, tzv. prvo dijete. Analognim pojmom u XML formatu zapisa smatramo prvim podelementom promatranog elementa. Konkretno u primjeru element naslov je prvo dijete elementa zaglavlje.
• Pokazivač na sljedeći čvor na istoj razini kao promatrani čvor, tzv. sljedeći brat. Analognim pojmom u XML formatu zapisa smatramo slijedeći element koji se pojavljuje unutar istog nadređenog elementa. U konkretnom primjeru, čvor podnaslov je slijedeći element čvora naslov.

Na grafičkoj apstrakciji na slici 11, čvorovi su prikazani pravokutnicima zaobljenih rubova, dok su pokazivači prikazani usmjerenim strelicama.

Unutar stabla razlikujemo nezavršne i završne čvorove. Nezavršni čvor je čvor koji ima bar jedno dijete, dok je završni čvor, koji se još naziva i listom, čvor bez djece. Nezavršni čvorovi apstrakcija su XML oznaka i imaju uglavnom semantičko značenje, dok završni čvorovi predstavljaju sam sadržaj dokumenta.

Osim stabla, dio strukture podataka su i dva rječnika. Rječnikom u našem konkretnom rješenju smatramo skupom uređenim parova pojavnice odnosno leme, te pripadne frekvencije pojavljivanja.

Listovi stabla od velike su važnosti i prilikom razvoja strukture podataka uvedene su optimizacije tog dijela strukture podataka. Umjesto spremanja riječi i interpunkcija kao dodatnih informacija unutar listova, iste se čuvaju u rječniku pojavnica, dok se u listovima stabla pamte samo pokazivači na pripadne uređene parove unutar rječnika. Ovakvom implementacijom dolazi do redukcije potrošnje memorije, budući se riječ mora pamtiti samo jednom, bez obzira na njen broj pojavljivanja u dokumentu.

Tokom gradnje unutarnje strukture, za svaku pronađenu pojavnicu poveća se pripadni brojač frekvencija pojavljivanja.

Zbog morfološke kompleksnosti hrvatskog jezika nužno je bilo razviti brz i učinkovit način nalaženja leme za svaku danu pojavnicu iz dokumenta. Ova informacija bitna je za mnoge funkcionalnosti sustava. Neke od tih funkcionalnosti su pretraživanje po lemi i ekstrakcija n-grama. Leme pojavnica u dokumentu čuvaju se u zasebnom rječniku. Unutar rječnika pojavnica uveden je dodatni atribut koji predstavlja skup pokazivača na pripadnu lemu u rječniku lema. Pokazivači na leme nužno čine skup, budući jedna pojavnica može imati više mogućih lema. Na ovaj način, vremenska složenost nalaženja leme dane pojavnice tokom rada sa sustavom jest konstantna,

O (1).

Ostali detalji unutarnje strukture ključni su za brzinu generiranja vizualne reprezentacije učitanog dokumenta unutar sustava, tj. generiranje RTF zapisa.

Kao prvo, listovi stabla povezani su međusobno u jednu vezanu listu, čime je moguće izravno pregledavati sam sadržaj dokumenta, ignorirajući na trenutak XML strukturu.

Nadalje, za svaki čvor strukture čuva se dodatna informacija udaljenosti od početka dokumenta, u znakovima. Ova informacija potrebna je zbog specifičnosti ciljnog operativnog sustava koji zahtjeva učinkovito nalaženje elementa na zadanoj poziciji od početka dokumenta. Zbog uvedene redundancije, vremenska složenost ovakve pretrage jest

O (d * n).

gdje je d prosječna dubina XML strukture, a n prosječan broj riječi odnosno interpunkcija unutar jednog XML elementa.

Spomenute posebnosti također su prikazane u grafičkoj apstrakciji danoj na slici 11.