Doktorska disertacija P. Jakopina, str. 89 - 114

6. poglavje

Entropija

Če je informacija obvestilo tistemu, ki jo je prejel, da se je nekaj zgodilo, je entropija mera za nedoločenost nekega sistema sporočil. Večja kot je entropija sistema, več informacije potrebujemo, da bi ga opisali, če pa je o njem vnaprej že vse znano, je njegova entropija nič. V zvezi z besedili je pojem entropije navadno povezan s pojmom nedoločenosti naslednje, še neprebrane črke besedila. Večja kot je entropija besedila, manj možnosti ima naključni bralec, da bo po n že prebranih črkah uganil črko n+1, ne da bi jo videl. Entropija besedila bi bila seveda največja, če bi bila verjetnost pojavitve vseh črk enaka (1/m, če je m število črk) in če bi bile nepovezane - če bi bila verjetnost pojavitve vsake naslednje črke neodvisna od vseh prejšnjih. Ker pa ni tako, predvsem samoglasniki nastopajo veliko večkrat kot soglasniki in nekateri znakovni n-terčki so tudi zelo pogosti, velika večina od teoretično možnih pa se sploh nikoli ne pojavi, je entropija besedila manjša in besedilo redundantno - lahko ga rekonstruiramo nazaj, tudi če v njem manjka tri četrtine črk, seveda ne naključno izbranih (Pavešić 1997, str. 64). Spodnja meja entropije za besedila v nekem jeziku je zelo težko določljiva, se pa da, s čedalje večjimi obdelanimi vzorci, počasi zniževati oceno za njeno zgornjo mejo.

6.1 Definicije

Po očetu teorije informacije Claudu Eugenu Shannonu (Shannon 1948) je mogoče entropijo nekega sistema X izraziti kot

kjer pomeni m število vseh možnih stanj sistema X, p$$_i pa verjetnost pojavitve i-tega stanja. Vse verjetnosti p$$_i so večje ali enake 0, njihova vsota pa mora biti 1. Če vzamemo za sistem množico vseh znakovnih n-terčkov za dan m in z N označimo število vseh n-terčkov, z m število različnih in če upoštevamo, da je verjetnost pojavitve i-tega n-terčka enaka

kjer je f$$_i frekvenca i-tega n-terčka, lahko izraz (3) poenostavimo (npr. Jakopin 1981) v

ki je bil tudi dejansko uporabljen pri računanju. Enota entropije, če smo jo pisali kot v (3), je en bit (od angl. binary digit) - količina, ki opisuje sistem z dvema možnima stanjema. Entropijo H, ki opisuje množico n-terčkov nekega besedila, imenujemo tudi vezana entropija, normirana vezana entropija pa je entropija na črko besedila, ki jo označimo s

Entropija H$$_n pove, koliko bitov je povprečno treba za najkrajše zakodiranje ene črke besedila, če bi ga kodirali z n-terčki. Na koncu ostane še najzanimivejša entropija F$$_n, to je pogojna entropija n-te črke, če prejšnjih n-1 že poznamo. Po Shannonu lahko hitro izpeljemo, da velja zveza

in privzamemo, da je F$$₁ = H$$₁. V prejšnjih raziskavah angleškega (Brown idr. 1992a) in slovenskega jezika (Kristan idr. 1994) vezane in seveda tudi pogojne entropije za višje n niso bile izračunane; v prvem primeru zaradi zelo velikega vzorca (583 milijonov besed), ki ni dopuščal neposrednega ugotavljanja n-terčkov in njihovih frekvenc, v drugem pa si raziskovalci zaradi premajhnega vzorca (650.000 besed) niso upali iti čez n = 8. Raziskovalci zgornje meje entropije za angleški jezik so si pri ugotavljanju svoje ocene pomagali z modelom, kjer so naslednji trojček v besedilu napovedovali iz prejšnjih dveh. Besedilo so tako aproksimirali z markovsko verigo približno osmega reda - da je vsak naslednji znak odvisen od prejšnjih osmih. Da bi to lahko dosegli, so morali izračunati n-terčke do n = 9.

Entropijo slovenskih leposlovnih besedil bi bilo načelno mogoče izračunati, če bi jih imeli v celoti na razpolago, v elektronski obliki. Ker tega še ni, jo moramo oceniti s pomočjo entropij obeh vzorcev v nalogi, ki skupaj merita (glej razdelek 2.1.3) približno 1% celote. Zmogljivosti računalnikov, predvsem glede pomnilnika, so se v zadnjih dveh letih toliko dvignile, da je postalo možno tako neposredno merjenje entropije obeh vzorcev, kot izvedba modela, ki pri napovedovanju pogostnosti n-terčkov preizkusnega (drugega) vzorca upošteva vse n-terčke učnega (prvega) vzorca, ki so se pojavili vsaj dvakrat. V nadaljevanju je najprej naveden izračun entropij za oba vzorca, potem pa še preizkus z modelom, ki temelji na razširjenem Huffmanovem kodiranju.

6.2 Entropija n-terčkov za oba vzorca

V tabeli 68 so navedene entropije za prvi vzorec, v tabeli 67 pa za drugi vzorec. Ker je prvi precej raznovrsten, drugi pa homogen in kompleten, jih v tem primeru ni bilo smiselno dajati skupaj. Navedene so celotna vezana entropija sistema n-terčkov H za posamezen n, normirana vezana entropija H$$_n (entropija na znak) in pogojna entropija H$$_n n-tega znaka, če je predhodnih n-1 že znanih. Poleg tega so navedeni še: število vseh n-terčkov, ki so se pojavili, število različnih, povprečna frekvenca n-terčkov, število enkratnic (tistih, ki se pojavijo samo enkrat) in število novih enkratnic: tistih n-terčkov s frekvenco 1 za dan n, ki ne izvirajo iz kake krajše enkratnice - take, ki se je

pojavila že za nižji n. Razumljivo je namreč, da če ima recimo neki trojček v besedilu frekvenco 1, pa ni na koncu enote, do koder merimo, bodo vsi višji n-terčki, ki ga imajo na začetku (ki izvirajo iz njega), tudi imeli frekvenco 1. N-terčki so bili tvorjeni iz besedila, očiščenega vseh dodatnih simbolov (oznak) in tujih citatov ter do meja povedi (nobena poved ni bila deljena preko vrstic) zloženega skupaj v 31.000 znakov dolge vrstice, kolikor je znašala zgornja meja urejevalnika. Pri ugotavljanju entropij, v nasprotju s prejšnjimi raziskavami (Gyergyék 1973, Kristan idr. 1994), tudi niso bile več enačene velike in male črke in vsa ločila združena v en znak. Entropije so bile izračunane do n = 62, v tabelah pa so navedene do n = 24, kjer pogojna entropija pri obeh vzorcih pade pod 0,005 bita.

6.2.1 Algoritem

Algoritem, ki je bil uporabljen pri računanju podatkov v tabelah 68 in 67, je skušal kar se najbolj da varčevati s pomnilniškim prostorom in obenem, na koraku n, izkoristiti vso informacijo koraka n-1, da tudi čas računanja ne bi bil pretirano dolg. Računanje rezultatov v tabeli 68 je na sodobnem računalniku (2 x Pentium II 400 MHz, 512 MB pomnilnika, Windows NT) trajalo nekaj manj kot 4 ure. Postopek bi bil izvedljiv že tudi s 96 MB pomnilnika, česar pa avtor seveda ni vedel vnaprej. Prvi poskus, s klasičnim (8-bitnim) pesimističnim algoritmom, da lahko namreč iz enega n-terčka nastane toliko (n+1)-terčkov, kolikor je minimum dveh števil:

• a) števila znakov v naboru
• b) njegove frekvence

in ki je seveda tudi rezerviral toliko prostora zanje, je namreč naletel na premajhen pomnilnik (512 MB) že pri računanju deveterčkov. Da bi bilo lažje nadaljevati, je bilo besedilo najprej prekodirano iz 16-bitnega nabora (tabela 28) v 8-bitnega, v katerem so imeli vsi znaki kode, manjše od 192. Zatem pa sta bili uporabljena dva premisleka:

1. da lahko iz n-terčka s frekvenco 1 nastane (n+1)-terček s frekvenco kvečjemu 1;
2. da je pričakovano število (n+1)-terčkov, ki nastanejo iz n-terčka i s frekvenco f$$_i > 1, mogoče dobro aproksimirati s kvadratnim korenom iz f$$_i, kadar je ta vrednost manjša od števila znakov v naboru;

Pomnilnik je bil nato, po opravljenem koraku n in pred korakon n+1, razdeljen na štiri dele:

1. del, kjer so bile shranjene tiste enkratnice, ki so bile odkrite na enem prejšnjih korakov od 1 do n ("matere" enkratnic s koraka n) in ki so se na koraku n tudi še dejansko pojavile na začetku kakega n-terčka;
2. del, kjer so bili shranjeni n-terčki s pričakovano frekvenco f$$_i,n+1 (na koraku (n+1)) 3 ali manj - zanje je bil rezervirano f$$_i,n+1 enot prostora z dodatnim, še praznim znakom;
3. del, predviden za (n+1)-terčke, katerih pričakovana frekvenca je bila večja kot 3;
4. prostor za (n+1)-terčke, ki bi nastali iz n-terčkov in je bila njihova dejanska frekvenca večja od predvidene (angl. overflow space).

Pomembno pri tem je, da sta bila dela (1) in (2) organizirana kot abecedno urejeni tabeli (abeceda kodov), zgrajeni po načelu podobnih tabel pri zbirkah črkovalnikov - vsak nov niz je imel pred seboj en znak, ki je povedal, koliko znakov v tem nizu je enakih kot v prejšnjem. To število je imelo prišteto 192, da ga je bilo mogoče odkriti. Tako je bilo torej mogoče shranjevati nize do dolžine 62 (znak s kodo 63 oz. 255 je pomenil konec zapisa) in od tod izvira potreba po znižanju kod v naboru na 191 ali manj. S tem so bili seveda shranjeni samo različni konci enkratnic in tabela, ki bi sicer lahko bila zelo velika, ohranjena v zmernih okvirih. Frekvence vseh nizov v tabelah od 1 do 3 do bile pred korakom n+1 postavljene na 0. Med postopkom na koraku n+1 je za bilo za vsak nov niz najprej preverjeno, ali je naslednik kake enkratnice iz dela 1. Če je bil, mu je bila frekvenca povečana na 1 in postopek končan. Če ni bil, je bilo potrebno preveriti, ali je zanj predviden prostor v delu 2 ali v delu 3. Če je bil predviden, je bila frekvenca spet povečana (v delu 2 do 3, v delu 3 brez omejitve) in naloga opravljena. Če je nov niz še vedno ostal, je bil dodan na konec dela 4. Iskanje po delih 1, 2 in 3 je potekalo z bisekcijo. Po pregledu celotnega besedila (ki je bilo medtem tudi v pomnilniku), je bil najprej sortiran del 4, nato pa opravljeno zlivanje delov 2, 3 in 4 (angl. merge) s sprotnim odmetavanjem tistih (pričakovanih) nizov, ki so imeli frekvenco 0. Na koncu je bila iz dela 1 in zlitih 2, 3 in 4 tvorjena izpisna datoteka, ki je bila shranjena na disk (od n = 5 v črkovalnikovem formatu) in odstranjena iz pomnilnika, nato pa še novi deli 1, 2 in 3 za korak n+2.

S to metodo bi bilo mogoče že s sedanjimi računalniki obdelovati tudi za velikostni red večja besedila.

6.2.2 Rezultati

Kot je videti iz tabel 68 in 67, se entropija začne pri 4,459 v prvem oziroma 4,456 v drugem vzorcu. Ugotovitev, da ima večji vzorec večjo entropijo kot manjši (Kristan idr. 1994), seveda vseeno drži - entropija sistema n-terčkov se pri prvem vzorcu dviguje do 23,898 bita, pri drugem vzorcu pa do 21,092 bita. Še bolj zanimivo je opazovati padanje normiranih vezanih entropij (entropij na znak) in pogojnih entropij. Grafično je prikazano na slikah 18 (za prvi vzorec) in 19 (za drugega).

Slika 18: Normirana vezana entropija in pogojna entropija v prvem vzorcu

Slika 19: Normirana vezana entropija in pogojna entropija v drugem vzorcu

Entropija na črko, H$$_n, monotono pada v obeh vzorcih, pri prvem od 4,456 do 0,996 bita na črko, v drugem pa od 4,459 do 0,879. Pogojna entropija F$$_n (spodnji krivulji na obeh slikah) v drugem vzorcu tudi monotono pada do 0, le precej hitreje kot v prvem. Pri prvem vzorcu potek gibanja pogojne entropije ni povsem enakomeren - opaziti je upočasnitev padanja od n = 5 do n = 7, kjer je rahla stopnica, potem pa se krivulja, kot na smučarski skakalnici, spusti v nižino do ničle. Pojavi se vprašanje, kje potegniti črto, do kod vzorca še sledita hipotetičnim vrednostim za celoto vseh slovenskih leposlovnih besedil in od kod naprej ju zaradi njune omejenosti ne moremo več upoštevati. Odgovor na to vprašanje se po mnenju avtorja skriva v zadnjih stolpcih tabel 68 in 67. V tabeli 68 opazimo, da se število novih enkratnic (zadnji stolpec) povečuje do n = 10, do koder hitro raste tudi še število različnih n-terčkov (šesti stolpec); povprečna frekvenca deseterčkov je prav tako še razmeroma blizu 2 (1,68). Pri enajsterčkih vzorcu poide sapa in zmanjka mu življenjske moči - število novih enkratnic znatno pade, povprečna frekvenca se zniža na vrednost, ki je že bližje 1 kot 2 (1,43) in hitrejša pot navzdol je odprta. Gibanje novih enkratnic je upodobljeno na sliki 20.

Slika 20: Število novih enkratnic v prvem vzorcu

Iz vsega naštetega, iz navedenih podatkov besedilnega vzorca v nalogi je mogoče torej sklepati, da zgornje meje entropije ni možno postaviti pod 2,233 bita na znak (vrednosti pri deseterčkih), ki je blizu polovice entropije H$$₁ (2,228 bita na znak), znane ocene za limito entropije H$$_n, ko se n bliža neskončnosti. Ocena za zgornjo mejo entropije v slovenskih leposlovnih besedilih znaša torej 2,233 oziroma

2,2 bita na znak

Pogojna entropija pri deseterčkih znaša 0,740 bita na znak, kar je v mejah, dobljenih pri ocenjevanju pogojne entropije s poskusi za angleški jezik (0,6 - 1,3 bita na znak, Shannon 1951). Ocenjena vrednost, 2,2 bita na znak, je za desetino višja od vrednosti, ki so jo izmerili raziskovalci IBM-ovih laboratorijev na dvestokrat večjem vzorcu (Brown idr. 1992a), 2,0 bita/znak. Osnovna dva razloga sta večja pregibnost slovenskega jezika in pa to, da vzorca vsebinsko nista povsem primerljiva. V ameriškem vzorcu leposlovja praktično ni bilo, le roman Arthurja Conana Doyla Prigode Sherlocka Holmesa, večina gradiva pa je bila poslovna korespondenca (angl. office correspondence) velikih multinacionalnih družb. Pričakovati bi bilo, da je entropija takega gradiva nižja od entropije leposlovnih besedil.

6.3 Ocena entropije z modelom

Ocena zgornje meje entropije, dobljena v prejšnjem razdelku iz entropije n-terčkov prvega vzorca, bi bila seveda prepričljivejša, če bi jo bilo mogoče podpreti še z jezikovnim modelom. V ta namen smatrajmo prvi vzorec za učni vzorec, podatki katerega bodo služili za konstrukcijo modela, s katerim bomo potem besedilo preizkusnega (drugega) vzorca lahko komprimirali, kodirali tako, da bo skupna dolžina kod najkrajša in s tem dobili še eno oceno za entropijo.

Če je teorija informacij pogosto definirana kot proučevanje učinkovitega kodiranja, kar se tiče hitrosti in zanesljivosti prenosa (Ingels 1971), je komprimiranje podatkov veja teorije informacij, ki se ukvarja z minimiziranjem količine podatkov, ki jih je treba prenesti ali shraniti. Težišče reševanja problemov pri komprimiranju podatkov se je v zadnjem desetletju sicer preneslo na metode za učinkovito shranjevanje slik, kakršna sta standard JPEG (npr. Pennebaker in Mitchell 1993, Wallace 1991) in fraktalno komprimiranje (npr. Fisher 1995, Jacquin 1993), vendar je ostalo komprimiranje besedil v sodobnih raziskovalnih prizadevanjih slej ko prej aktualno.

V nadaljevanju je razložen kodirni algoritem, ki je bil nato uporabljen pri konstruiranju modela za komprimiranje besedil.

6.3.1 Huffmanovo kodiranje

Način kodiranja z minimalno redundanco (da se skupno število bitov kod simbolov kar najmanj razlikuje od entropije simbolov), če se število simbolov na izvoru približuje neskončnosti, je Shannon-Fanojevo kodiranje (Shannon in Weaver 1949, Fano 1949), kodiranje z zajamčeno minimalno redundanco tudi že brez zahteve po neskončnem številu simbolov pa je Huffmanovo kodiranje (Huffman 1952, Sayood 1997: tretje poglavje, program v Press 1992: razdelek 20.4). Pri obeh načinih za določitev kod, prirejenih vhodnim simbolom, pri besedilih so to navadno znaki, lahko pa tudi nizi znakov, dobimo kot rezultat binarne kode (kode iz binarnih števk), najprej pa potrebujemo tabelo simbolov z njihovimi pogostnostmi, urejeno po nenaraščajočih pogostnostih. Pri Shanon-Fanojevi metodi na vsakem koraku seznam razdelimo v dve skupini, tako da sta vsoti pogostnosti simbolov v obeh skupinah kar najbolj enaki. Vsem simbolom zgornje skupine potem dodelimo binarno števko 0 kot prvo števko njihovega koda, vsem simbolom spodnje skupine pa 1. Vsako skupino nato po istem načelu razdelimo naprej in njenim simbolom dodelimo dodatno binarno števko. Postopek ponavljamo, dokler v vsaki skupini ne ostane samo po en simbol. V spodnji tabeli so prikazane ustrezne kode za znake povedi Gori_na_gori_gori.

Poved ima 18 znakov, torej bi morali prvi skupini imeti skupno frekvenco kar najbližjo 18/2 ali 9. V prvi zgornji skupini se torej znajdejo znaki _, i in o, ki imajo skupno frekvenco ravno 9, v spodnji pa vsi ostali. Prvi dobijo začetno števko 0, drugi 1. Ponovna delitev skupine _, i in o se ustavi pri i, ker je 9/2 = 4.5 in je 3+3 ravno tako daleč od 4.5 kot 3. _ dobi torej še eno 0, i in o pa 1. Deljenje skupine i in o je trivialno, ker sta podskupini samo dve in imata enako frekvenco - i dobi še eno ničlo, o pa 1. Skupine s simbolom _ ni treba deliti še naprej, ker ima samo en element. Prvo spodnjo skupino r, g, a, G, n in . delimo analogno. Skupno število bitov za kodiranje povedi Gori_na_gori_gori. je tako 55 (3x2 + 3x3 + 3x3 + 3x3 + 2x3 + 1x4 + 1x4 + 1x4 + 1x4) ali 3,06 bita na znak, kar je malenkost slabše od entropije sistema znakov iz tabele 69, ki znaša 3,00 bita na znak (po zvezi (3) iz razdelka 6.1).

1. Razvrstimo n izvornih simbolov padajoče po pogostnostih (normiranih med 0 in 1)
2. Združimo zadnja dva simbola v nov simbol, katerega pogostnost je enaka vsoti obeh in ga uvrstimo na ustrezno mesto v seznam, tako da le-ta obdrži svojo urejenost. Opazovana simbola izločimo iz seznama.
3. Korak 2 ponavljamo tako dolgo (n-1 krat), dokler ne dobimo samo enega simbola (celote) s pogostnostjo 1. Imenujemo ga koren, nastalo strukturo pa Huffmanovo drevo. Izvorni simboli so njegovi listi.
4. Za vsak izvorni simbol sledimo pot od korena do listov, s tem da na vsakem razvejišču zapišemo 0 za prehod na levo in 1 za prehod na desno. Dobljene števke zložimo skupaj in tako dobimo Huffmanovo kodo za vsak izvorni simbol.

V tabeli 70 je upodobljeno Huffmanovo drevo za simbole povedi Pravemu dedcu solze ne tečejo ven, temveč mu tečejo noter. iz drugega vzorca. Poved spada med lipogramske povedi (glej razdelek 5.3.3), saj nima niti ene črke a. Vsebuje 58 znakov, od tega 20 različnih. V tabeli so koraki algoritma ponazorjeni z zaporednimi stolpci. Za vsakim simbolom, izvornim in sestavljenim, je za dvignjeno piko navedena njegova frekvenca. Trikotnik v tabeli je razdeljen na dva dela, da ga je bilo mogoče spraviti na list papirja.

Na prvem koraku sta se v nov simbol ,. s frekvenco 2 združila simbola , in . in se pomaknila 6 mest navzgor, za zadnji simbol s frekvenco 2, za r. Na drugem koraku sta bila to l in P, na tretjem a in c, na četrtem pa je nov simbol, sz,. nastal že iz dveh sestavljenih. Na devetnajstem koraku smo prišli do korena, sestavljenega iz vseh izvornih simbolov in s skupno frekvenco 58. Huffmanovo kodo najpogostejšega simbola e zdaj dobimo tako, da mu sledimo po vseh razvejiščih, kjer še ni bil samostojen. Najprej, pri razcepu simbola _vdo,.szjrtlPacenučm v _vdo,.szjrtlPac in enučm je bil v drugem delu in torej dobi spredaj 1. Pri nadaljnji cepitvi skupine enučm v e in nučm pa je bil v prvem delu, dobil še 0 in je to že tudi vse, ker je postal samostojen. Njegova Huffmanova koda je torej 10.

V tabeli 71 je naveden seznam vseh znakov te povedi s frekvencami, Shannon-Fanojevimi in Huffmanovimi kodami. Shannon-Fanojeve kode hitro prepoznamo po strogem naraščanju vodilnih enojk proti dnu tabele. Skupno število bitov kod za vse znake povedi je 225 pri Shannon-Fanojevem in 224 pri Huffmanovem kodiranju, kar je 3,88 oziroma 3,86 bita na črko. Entropija sistema znakov povedi znaša, spet po izrazu (3) iz razdelka 6.3.1, 222.49 bitov ali 3,84 bita na znak.

Huffmanovo kodiranje besedil na nivoju znakov prinese sicer že znaten prihranek v primerjavi s kodiranjem znakov s fiksno dolžino osmih bitov, ki je zdaj običajno pri shranjevanju in prenašanju (npr. standard ASCII in izpeljanke), skoraj polovico, a vendar manj kot bi bilo možno še z upoštevanjem povezanosti črk v besedilu in upoštevanjem krajevnih posebnosti v besedilu. Klasični Huffmanov algoritem, opisan v tem razdelku, zato navadno označujejo kot statično Huffmanovo kodiranje, ker so kode posameznih simbolov med vsem kodirnim postopkom nespremenjene. Ta način kodiranja tudi zahteva dva prehoda preko izvornih simbolov - prvega za izračun njihovih pogostnosti in drugega za kodiranje v ožjem smislu. Dinamično Huffmanovo kodiranje je postopek, pri katerem se Huffmanovo drevo gradi in spreminja sproti, brez predhodnega ugotavljanja pogostnosti simbolov, z vsakim novim prebranim simbolom glede na njegovo dotedanjo frekvenco (Faller 1973, Gallager 1978, Knuth 1985). Po teh treh raziskovalcih se izpopolnjen postopek, uporabljen v nekaterih komprimirnih programih v okolju UNIX, imenuje tudi algoritem FGK. Kasneje je k zmanjšanju dela pri sprotnem uravnoteževanju Huffmanovega drevesa in k minimiziranju tudi največje dolžine kode za posamezen simbol prispeval še J. Vitter (Vitter 1987).

Dinamično Huffmanovo kodiranje sicer navadno ne prinese prihrankov pri prostoru (Vitter 1987), pač pa, zaradi le enega prehoda preko podatkov namesto dveh pri statičnem, pri hitrosti komprimiranja.

Poleg dinamičnih algoritmov je bilo Huffmanovo kodiranje deležno še raziskav v smeri razširitev (Bshouty in Falk 1992) in novih teoretičnih študij v zadnjem času (Calude in Tomescu 1997). Huffmanovo kodiranje je služilo za osnovo s strani agencije NASA leta 1995 nagrajenemu algoritmu za komprimiranje pri prenosu slik z vesoljskih postaj na zemljo (Rice idr. 1993, Venbrux idr. 1992). Poleg tega je bil ta način kodiranja uporabljen še pri algoritmih, ki niso povezani s komprimiranjem, npr. pri konstruiranju optimalnih iskalnih dreves (Hu in Tucker 1971, Itai 1976) zlivanju seznamov (Brent in Kung 1978) in generiranju optimalnih evaluacijskih dreves pri prevajanju izrazov (Parker 1980).

V tabeli 72 na prejšnji strani so navedene pogostnosti in Huffmanovi kodi za 105 znakov v besedilih obeh vzorcev, ki so dosegli pogostnost vsaj 0,0000005. Najkrajšo kodo, 2 bita, ima presledek, kode samoglasnikov a, e, i in o so dolge po 4 bite, najdaljša pa je koda črke ì, 20 bitov.

6.3.2 Izbira postopka

Poleg Huffmanovega kodiranja in njegovih adaptacij so še drugi kodirni postopki, pri katerih se vsota dolžin kod za izvorne simbole asimptotično približuje entropiji izvornega sistema. Sem sodijo aritmetično kodiranje (Abramson 1963, Rubin 1979, Witten idr. 1987), algoritem LZW (Ziv in Lempel 1977, Welch 1984), algoritem BSTW (Bentley idr. 1986) in algoritem BWT (Burrows-Wheelerjeva transformacija: Burrows in Wheeler 1994, Fenwick 1996). Vsak ima svoje prednosti in pomanjkljivosti. Ker je osnovni namen naloge predvsem iskanje mehanizma, s katerim bi bilo mogoče identificirati izvorne simbole kot tiste nize znakov, katerih pogostnosti se najbolj splača izkoristiti pri konstrukciji modela z minimalno entropijo, je v nadaljnjem kot konkretni algoritem preverjanja še naprej uporabljeno Huffmanovo kodiranje.

Pri načrtovanju konkretnih postopkov, namenjenih posebej komprimiranju besedil, so raziskovalci, kot sicer predvsem za angleški jezik, doslej ubirali različne poti. Predvsem so skušali izpostaviti pogoste elemente v besedilu. B. Hahn (Hahn 1974) je predlagal kodiranje besed v datoteki z besedilom, pri katerem so njihove kode kazalci v slovar besed. Kombiniran postopek, pri katerem bi bil rezultat kodiranja sestavljen iz kazalcev v slovar pogostih besed in pogostih besednih končnic, ostalo pa kodirano na klasičen način, je predlagal R. Tropper (Tropper 1982). Precej pozornosti je bilo posvečeno kodiranju pogostih znakovnih dvojčkov v besedilu (Snyderman in Hunt 1970, Cortesi 1982, Knuth 1985). R. A. Wagner (Wagner 1973) je poskusil najpogostejše besedne skupine (fraze), ki zaslužijo posebno obravnavo, določiti ročno, druga raziskava (Fraenkel idr. 1983) pa je obravnavala strojno identifikacijo pogostih predpon in pripon. Doslej že že večkrat omenjena raziskava (Brown idr. 1992a, Brown idr. 1992b), ki je temeljila na statistiki deveterčkov, dobljeni iz 583 milijonov besed dolgega vzorca, je postregla z doslej najnižjo oceno entropije za angleška besedila, 2,0 bita na znak. Pogostnosti deveterčkov, dobljene iz vzorca, so bile potem uporabljene na 2 milijona besed dolgem preizkusnem vzorcu, znanem Brownovem korpusu z besedili iz leta 1961 (Francis in Kučera 1982). Na kratko bi lahko rekli, da je bila entropija Brownovega korpusa ocenjena z očmi in védenjem nekoga, ki je prebral učni vzorec in si ga zapomnil. Jezik je v smislu svoje funkcije določen kot komunikacijski sistem, ki ekološko odseva lastnosti svojih uporabnikov - človeških bitij (Tobin 1997, str. 145) in je zato sistem, ki mora z najmanj energije posredovati čimveč sporočila. Ta zahteva ima seveda svoj antipod - dodatno zahtevo po zanesljivosti prenosa, ki zahteva redundantnost, da smo sposobni tako ali drugače poškodovano oz. moteno sporočilo še vedno prav prebrati ali razumeti. Kako velik je vzorec, ki ga pozna in se ga spomni tipičen srednje izobražen pripadnik nekega jezikovnega področja, je to nekaj milijonov besed ali manj, ali pa je več, nekaj deset milijonov ali celo nekaj sto milijonov besed kot v primeru vzorca IBM-ovih raziskovalcev, je težko oceniti.

Avtor se je odločil, da bo pri oceni zgornje meje entropije z jezikovnim modelom prvi vzorec, 2.700.000 besed, uporabil kot učni vzorec, drugega, 400.000 besed, pa kot preizkusni. Oba sta seveda veliko manjša od ameriškega zgleda, prvi dvestokrat, drugi pa petkrat. Zato je seveda pričakovati manjšo učinkovitost podatkov učnega vzorca na preizkusnem in posledično šibkejšo (višjo) oceno za zgornjo mejo entropije.

6.3.3 Model z razrezom na enako dolge n-terčke

Najprej je bila uporabljena najpreprostejša možnost, razrez prvega in drugega vzorca na enako dolge n-terčke in določitev ustreznih Huffmanovih kod. Pri tem sta bili besedili obeh vzorcev smatrani za eno samo vrstico in zaporedno razrezani, zadnji n-terček, če je bil prekratek, pa odvržen. V nasprotju z n-terčki v razdelku 6.2 (tabeli 68 in 67), kjer so bili generirani vsi možni, gre tu le za zaporedne n-terčke. Primer je npr. razrez povedi To_je_vse. na peterčke - pri razrezu, ki sledi, dobimo samo 2: To_je in _vse., v razrezu iz razdelka 6.2 pa 6: To_je, o_je_, _je_v, je_vs, e_vse in _vse.. V tabelah 73 in 74 so navedeni: n, število vseh n-terčkov po razrezu, število različnih n-terčkov, skupna dolžina Huffmanovih kod za vse n-terčke (v bitih), dolžina Huffmanovih kod na znak besedila, dolžina najkrajše in najdaljše Huffmanove kode. Tabeli segata od n = 1 do 20, kjer pade dolžina Huffmanovih kod na znak besedila pod 1 bit. Opazimo nižje vrednosti na znak besedila kot v tabelah 68 in 67, kar je razumljivo zaradi manjšega števila n-terčkov; povprečna frekvenca n-terčka pade pri prvem vzorcu pod 2 že pri osmerčkih, pri drugem vzorcu pa pri sedmerčkih. Vidimo tudi, da se z

rastočim n zmanjšuje razlika med najkrajšo in najdaljšo Huffmanovo kodo - v tabeli 73 imajo vsi dvajseterčki razen najpogostejših 1153 dolžino 20 bitov, v tabeli 74 pa vsi razen prvih 22 dolžino 16 bitov. Ob nizkih vrednostih na znak pri višjih n je pri konstrukciji praktičnega komprimirnega mehanizma seveda treba upoštevati še strošek, ki ga potegne za seboj slovar različnih n-terčkov s Huffmanovimi kodami. Tudi če bi bil abecedno urejen in shranjen v črkovalnikovem načinu (kjer je pred vsakim naslednjim n-terčkom najprej shranjen podatek o številu začetnih črk, ki se ujemajo s predhodnikom, potem pa le rep n-terčka, ki se razlikuje od prejšnjega, za njim pa Huff. koda), nikakor ni majhen. Drugače je seveda, če ta strošek vzamemo v zakup, na račun modela - recimo, da je tak slovar že vgrajen v sprejemnik in oddajnik, ki sta specializirana za besedila v slovenskem jeziku. V tem primeru potrebujemo, pred odločitvijo o morebitnem preizkusu modela, dobljenega s podatki o n-terčkih prvega vzorca, na drugem vzorcu, še podatek o pokrivanju, kolikšen delež n-terčkov drugega vzorca se ujema z n-terčki prvega. Ta podatek je razviden iz slike 21.

Slika 21: Pokritje n-terčkov drugega vzorca z n-terčki prvega vzorca

Žal je prekrivanje zelo dobro samo za zelo nizke n. Pri šesterčkih je le 85%, potem pa je padanje še hitrejše in že pri dvanajsterčkih je vrednost pod 10% (8.6%). Ker je število bitov na črko pri peterčkih v prvem vzorcu še precej nad 3, preizkus v tem primeru opustimo.

6.3.4 Model z razrezom na besede

Pri tem se odločimo, da besedilo obeh vzorcev razrežemo na robovih besed - ločilno črto potegnemo pred vsako besedo in za njo. Primer razreza je odlomek iz drugega vzorca - iz romana Pomladni dan:

Tako dobimo po prelomu seznam enot, ki so ali besede ali pa ločilni nizi. Najpogostejša enota je že na prvi pogled najpogostejši ločilni niz, presledek. V tabeli 75 je navedeno število enot in dolžine Huffmanovih kod za oba vzorca:

Vrednostim v zadnjem stolpcu manjka sicer še kar nekaj do želene meje, vendar so obetavne. V tabeli 76 so navedene najpogostejše enote iz besednega razreza za oba vzorca. Do desetega mesta so na vrhu isti nizi; opazimo tudi, da ima samostojni presledek Huffmanovo kodo dolgo le en bit, da pa so le eno ali dve črki dolgi razmeroma slabo kodirani - z vsaj tremi biti na znak.

Poskusimo zdaj uporabiti enote prvega vzorca za kodiranje drugega. Izkaže se, da 20.950 besednih enot nima svojega ustreznika v prvem vzorcu. Med njimi je 9.416 različnih in od tega kar 3.264 (35%) takih z veliko začetnico, ki so predvsem imena. Če med nize prvega vzorca uvedemo še poseben niz, ki ga bomo uporabili za označitev, da sledi neznana besedna enota in mu damo pogostnost 20.950/818.362, ugotovimo, da je dolžina njegove Huffmanove kode 6 bitov. Izkaže se tudi, da bi za Huffmanove kode znanih besednih enot porabili skupaj 5.814.874 bitov, da je v prvemu vzorcu neznanih besednih enotah skupaj 154.870 znakov in pa, da bi za kodiranje dolžin teh 20.950 enot s Huffmanovimi kodami porabili skupaj 70.916 bitov (3,39 bita na dolžino). Če neznane znake kodiramo z navadno Huffmanovo kodo (vsak znak posebej), ki zasede povprečno 4,50 bita, porabimo za kodiranje enot drugega vzorca s kodami enot prvega z omenjenim dopolnilom za neznane enote, skupaj 6.707.685 bitov (5.814.874 + 20.950*6 + 70.196 + 154.870*4,5). Če to delimo s številom znakov v drugem vzorcu, 2.296.775, dobimo

2,92 bita na znak

našo prvo z modelom besed prvega vzorca na drugem vzorcu dobljeno oceno za entropijo. Poglejmo še, kdo so glavni krivci, da ocena ni nižja. Najpogostejših 16 besed (s frekvencami) iz drugega vzorca, ki se v prvem niso nikoli pojavile, je: Majcen (270), Drejc (189), Temnikar (185), Tantadruj (172), Venc (162), Venček (151), Žef (150), Kadetka (125), Tildica (116), Nanca (106), Hotejec (105), Najdù (104), Temnikarica (102), Modrijan (97), Okrogličar (83) in Nančika (73). Skoraj same osebe, ki so tipične za Cirila Kosmača in jih v drugih literarnih delih ne najdemo.

6.3.5 Model z optimalnim razrezom na n-terčke

Glede na vse v prejšnjih razdelkih omenjene in obravnavane pristope ostane na koncu še možnost oblikovanja modela, v katerem bi dali priložnost vsem nizom znakov prvega vzorca, ki dosežejo določeno frekvenco. S tem bi se izognili tako težavam s slabim pokrivanjem (slika 21 v razdelku 6.3.3) enako dolgih n-terčkov: algoritem bi na vsakem koraku uporabil najdaljši možen n-terček kot tudi šibkostim, ki jih prinaša razrez na besede: veliko kratkih besed v vrha frekvenčnega seznama, npr. je, se, bil se z znatno frekvenco pojavlja tudi skupaj. Pot do takega seznama, ki utegne biti zelo obsežen, pa je prav tako znana - seznam vseh n-terčkov s frekvencami je osnovni produkt algoritma za ugotavljanje entropije, opisanega v razdelku 6.2.1. Pojavi se še vprašanje, kako daleč iti, do katere dolžine. Iz slik 22, 23, 24, 25, 26 in 27 na naslednji strani je razvidno, da začne število različnih n-terčkov od n = 20 naprej močno upadati in se je avtor zato odločil postaviti mejo pri 32. V tabeli 77 je navedeno število različnih in vseh n-terčkov z dolžinami od 1 do 32, ki imajo frekvenco vsaj 10, vsaj 5 in vsaj 2.

Kot vidimo, je različnih n-terčkov z dolžinami od 1 do 32, ki imajo frekvenco vsaj 10, slab poldrugi milijon, s frekvenco 5 že skoraj 3,5 milijona, s frekvenco 2 pa že več kot 16 milijonov. Njihove skupne frekvence se gibljejo od 120 milijonov pri minimalni frekvenci 10 do 164 milijonov pri minimalni frekvenci 2. Skratka, jezikovni model za slovenski jezik, ki bi poznal pogoste nize in

Sliki 22 in 23: Število različnih(22) in vseh(23) n-terčkov s frekvenco vsaj 10 po dolžinah

Sliki 24 in 25: Število različnih(24) in vseh(25) n-terčkov s frekvenco vsaj 5 po dolžinah

Sliki 26 in 27: Število različnih(26) in vseh(27) n-terčkov s frekvenco vsaj 2 po dolžinah

njihove frekvence, bi potreboval precej prostora, a še vedno v okvirih zmogljivosti sedanjih računalnikov. Iz slik 22, 24 in 26 razberemo, da se porazdelitve, ko povečujemo število n-terčkov (z nižanjem minimalne frekvence) širijo, vrh pa se pomika od 7 znakov (min. frekv. 10) na 8 (min. frekv. 5) in 9 znakov pri minimalni frekvenci 2. Ker želimo čimveč čimdaljših n-terčkov v modelu, da bo ocena entropije na znak lahko kar najmanjša, pričakujemo, da bo najobsežnejši model tudi najboljši. Porazdelitve na slikah 23, 25 in 27 so nepravilne in monotono padajoče, saj skupne frekvence za manjši n seveda ne morejo biti manjše od tistih pri večjem n - povprečna frekvenca z rastočim n hitro pada. Vidimo tudi, da je celo pri minimalni frekvenci 2 skupna frekvenca n-terčkov od n = 20 naprej praktično zanemarljiva in da torej odločitev o omejitvi na dolžine do 32 ni bila prestroga.

Ostane še konstrukcija Huffmanovih kod za n-terčke vseh treh skupin in preizkus modela na besedilu drugega vzorca. Drevo s 16 milijoni listov in prav toliko razvejišči je bilo še v mejah računalniških virov, dostopnih avtorju. Ko so bile Huffmanove kode za vse n-terčke posameznih variant izračunane, je bilo treba z upoštevanjem n-terčkov in njihovih kod razrezati drugi vzorec tako, da bi bila vsota kod za vse dobljene nize najkrajša. Algoritem razreza je sestavljen iz treh korakov:

1. na tekočem mestu poišči tisti n-terček iz učnega vzorca, ki se bo z besedilom ujemal najdlje in postavi začasno delilno mesto na njegov konec;
2. pomikaj dobljeno delilno mesto za mesto nazaj toliko časa, dokler skupno število bitov na znak dveh nizov - od tekočega mesta do delilnega mesta in najdaljšega niza od delilnega mesta naprej ne bo slabše (večje);
3. pomakni tekoče mesto za delilno mesto in nadaljuj s korakom 1 dokler ne prideš na konec besedila;

Za ilustracijo algoritma je naveden razrez morda najznamenitejše povedi iz drugega vzorca, iz romana Pomladni dan.

V prvi vrstici tabele je naveden razrez, pri katerem so bili uporabljeni vsi n-terčki 1. vzorca z dolžino do 32 znakov, ki so imeli frekvenco vsaj 10, v drugi vrstici vsi s frekvenco vsaj 5, v tretji pa s frekvenco vsaj 2. Prva vrstica ima 12 delilnih mest, druga 11, tretja pa 10. Prva delitev je zajela 81 znakov, druga je prišla 9 znakov dlje, tretja pa še eno mesto naprej, 91 znakov daleč. Zaradi enostavnosti je v nadaljevanju naveden premislek začetka prve delitve.

Pri tem so bili uporabljeni podatki iz tabele 79. Na začetku povedi je bil najdaljši ugotovljeni niz dolg 7 znakov (Tisti_p), katerega Huffmanov kod je dolg 23 bitov. Niz Tisti_po se v prvem vzorcu ni pojavil 10-krat ali več. Začasno delilno mesto je torej postavljeno za sedmim znakom. Najdaljši niz, ki sledi, je omladni z dolžino Huffm. kode tudi 23 bitov. Skupaj 46 bitov za 14 znakov ali 3,29 bita na znak. Algoritem zdaj zahteva preverjanje toliko znakov nazaj, da dobimo slabši rezultat. En znak nazaj dobimo niza Tisti_ in pomladni (niz pomladni_ ni imel frekvence 10 ali več), ki imata skupno dolžino Huffmanovih kod 20+23, se pravi 43 bitov, spet za 14 znakov, ali 3,07 bita na znak. Dva znaka nazaj opazujemo par Tisti in _pomladni (niz _pomladni_ se očitno tudi ni pojavil v naboru), ki imata skupno dolžino Huffm. kod 19+23 = 42 bitov ali 3,00 bita na znak. Še eno mesto nazaj dobimo par Tist in i_pomlad, ki imata skupno dolžino Huffmanovih kod 18+23 = 41 bitov za 12 znakov, kar je 3,42 bita na znak ali slabše kot prej. Prvo delilno mesto torej pade za Tisti, s prirastkom 19 bitov (3,80 bita na znak).

Pri določanju drugega delilnega mesta sta prvi par _pomladni in _dan_je_bil_, ki imata 23 in 22 bitov dolgi Huffmanovi kodi, skupaj torej 45 bitov za 21 znakov ali 2,14 bita na znak. Mesto nazaj dobimo par _pomladn in i_dan_je_bil s skupno dolžino 46 bitov (23+23) za 20 znakov ali 2,30 bita na znak, kar je že slabše. Naslednje delilno mesto je torej za _pomladni. Pri določanju tretjega delilnega mesta imamo najprej niza _dan_je_bil_ in lep,_ s skupno dolžino Huffmanovih kod 22+20 = 42 bitov za 17 znakov ali 2,47 bita na znak. Mesto nazaj je par _dan_je_bil in _lep,_, skupaj 22+22 = 44 bitov ali 2,59 bita na znak, kar je slabše in delilno mesto postavljeno za _dan_je_bil_. Do tja se je torej skupaj nabralo 19+23+22 = 64 bitov za 26 znakov ali 2,46 bita na znak.

Rezultati razreza drugega vzorca za vse tri variante (min. frekvenca 10, 5 in 2) so navedeni v tabeli 80.

Najkrajše dolžine Huffmanovih kod so bile v vseh treh primerih 6 bitov, najdaljše pa, spet v vseh treh primerih, 27 bitov. Ocena za entropijo, dolžina kod na znak besedila, pade od 2,89 bita pri najskromnejšem naboru n-terčkov do 2,72 bita na znak, če upoštevamo vse n-terčke iz prvega vzorca, dolge od 1-32 znakov, ki so se pojavili vsaj dvakrat. Rezultat je opazno večji od ocene iz razdelka 6.2.2, 2,2 bita na znak in je na prvi pogled videti slab. Poskusimo ga osvetliti še z drugega zornega kota. V ta namen razdelimo drugi vzorec na dva, praktično enako velika dela (49.96% : 50.04%) - prvi obsega vsa dela od začetka do vključno scenarija Na svoji zemlji, drugi pa vse ostalo. Če uporabimo prvi del kot učno bazo in generiramo iz njega vse n-terčke (1-32), izračunamo njihove Huffmanove kode in jih potem po v tem razdelku opisanem algoritmu uporabimo za generiranje najkrajših kod za drugi del (1.149.161 znakov), dobimo rezultate iz tabele 81:

V tabeli smo šli še dlje kot pri prejšnji raziskavi, saj smo v zadnji vrstici uporabili prav vse n-terčke, tudi tiste, ki so se pojavili samo enkrat. Iz vrednosti zadnjega stolpca sklepamo, da je entropija Kosmačevega besedila, če druge polovice s prvo ni mogoče napovedati bolje kot do 2,78 bita na znak, res bližje oceni 2,72 bita na znak, dobljeni v tabeli 80, kot pa kaki nižji. Drug premislek, ki kaže na višjo entropijo slovenskega leposlovnega besedila v primerjavi z vzorcem iz ameriške raziskave (Brown idr. 1992a), najdemo v opisu besednjakov IBM-ovega vzorca (Jelinek 1997, tabela 4.2, str. 75). V njem je navedeno, da je bilo za 15.000 novih besed (lem, ne besednih oblik) potrebno obdelati 640.000 besed obsegajoče besedilo. Drugi vzorec pričujočega dela je bil oblikoslovno označen in lematiziran in zato lahko v prejšnjem stavku navedeni številki primerjamo s Kosmačevim besedilom (glej tabelo 82 v naslednjem razdelku). V drugem vzorcu je bilo za 15.140 lem potrebnih le 408.000 besed besedila. Ta podatek spet kaže na višjo entropijo leposlovnega besedila.

Iz vsega navedenega avtor sklepa, da je z modelom, dobljenim iz besedil prvega vzorca in uporabljenim na besedilih drugega vzorca ugotovljena ocena zgornje meje entropije slovenskega leposlovnega besedila manjša od 2,72 oziroma

2,7 bita na znak

Poleg komprimiranja je model z optimalnim razrezom na n-terčke, ker vsebuje veliko zbirko nizov iz slovenskih besedil s pogostnostmi, mogoče uporabiti še za ugotavljanje, ali je neko besedilo slovensko oziroma, kako daleč je od slovenskega jezika. V tabeli 82 so navedeni rezultati uporabe modela na istem besedilu, prevodu Platonove države, v 16 evropskih jezikih (Projekt TELRI: Erjavec, Lawson in Romary 1998). Tabela je urejena padajoče po povprečnem številu bitov na znak, ki jih je pri kodiranju posameznega besedila dosegel model. V vsaki vrstici je najprej navedena zaporedna številka jezika, nato njegovo ime, prevajalec, leto izdaje dela, ki je služilo za prenos v elektronsko obliko (navadno se ujema z letom prevoda), vodjo prenosa v elektronsko obliko (le prvega, kadar jih je bilo več), število besed v delu, število znakov in na koncu še najpomembnejše, povprečno število bitov na znak, ki jih je potreboval model. Pomišljaj pomeni, da posamezen podatek ni bil znan. Besedila, dostopna na TELRI-jevem cedeju je avtor po najboljših močeh poenotil oz. transkribiral - bolgarsko besedilo je bilo že transkribirano v latinico, le šumniki so bili označeni s ch, sh, zh, ruski izvod pa je bil še v cirilici. Besedilom v češkem, slovaškem in poljskem jeziku so bila odvzeta diakritična znamenja (rezultati z njimi vred bi bili povprečno 5.88, 5.37 in 5.34 bita na znak).

Po pričakovanju sta, tudi če upoštevamo rezultate modela, slovenščini najbližja srbski in hrvaški jezik, sledijo pa bolgarski, češki, poljski, ruski in slovaški. Na koncu seznama sta, prav tako ne preveč presenetljivo, oba ugrofinska jezika, le da je finski našemu jeziku po modelu precej bližji kot madžarščina.

6.3.6 Komprimiranje vzorcev z drugimi programi

Za dodatno osvetlitev so navedeni še rezultati komprimiranja besedil obeh vzorcev z najboljšimi programi za komprimiranje datotek, ki jih je mogoče najti na internetu. Zanimanje za tovrstne programe, predvsem za shranjevanje slik, ki delajo brez izgube informacije (angl. lossless compression), se je z razmahom digitalne fotografije v zadnjih dveh letih zelo povečalo.

Avtor se je pri odločanju, katere izmed velike množice programov izbrati, oprl predvsem na rezultate preizkusov, ki sta jih opravila Jeff Gilchrist - internetni naslov strani http://web.act.by.net/~act/act.html, in Aleksander Ratušin - http://www.geocities.com/SiliconValley/5577/artest10.html. Rezultati za prvi in za drugi vzorec so v tabelah 83 in 84 na naslednji strani; v rubriki tip je navedeno, ali je program brezplačen (fw, od angl. freeware) ali ga je treba kupiti po navadno enomesečnem preizkusnem obdobju (sh, od angl. shareware). Programi v obeh tabelah so urejeni naraščajoče po zmogljivosti, ugotovljeni na prvem vzorcu - se pravi po številu bitov, ki jih je za kodiranje znaka obeh datotek (z besedili prvega oz. drugega vzorca) povprečno potreboval ustrezni program. Prvih pet programov, z izjemo programa ESP, je delo renomiranih in uveljavljenih proizvajalcev - PKZIP je dejanski standard za izmenjavo komprimiranih datotek na internetu. Podrobnosti, predvsem o implementaciji in navadno tudi o uporabljenih algoritmih, seveda niso znane; zadnjih pet programov, v največji meri najboljši trije, Boa Constrictor, RKIVE in Ufa, uporabljajo tehniko zaporednega komprimiranja podatkov z različnimi postopki, ki se utegnejo po predhodni oceni najbolje obnesti - npr. najprej LZW, potem aritmetično kodiranje. Časi izvajanja so v sekundah, na običajnem namiznem računalniku tipa PC, stikala pa so bila izbrana za največje možno komprimiranje besedil, kadar je program to izbiro imel, sicer pa na največje možno komprimiranje.

Rezultati sicer niso neposredno primerljivi s postopki iz prejšnjih razdelkov, kjer se modeli opirajo na zelo velike zbirke s podatki, ki so tipični za slovenski jezik, pa vseeno - postopek z optimalnim razrezom na n-terčke je potreboval na prvem vzorcu 255 sekund in kodiral znake s povprečno 2,36 bita na znak, na drugem pa 44 sekund z že omenjenimi 2,72 biti na znak.

Komprimirni časi programov iz obeh tabel gredo pri prvem vzorcu sicer v desetine minut (RKIVE je potreboval celo dobre pol ure), vendar opazimo, da se mehanizmi, razviti predvsem za komprimiranje slik, tudi na besedilih zelo dobro obnesejo. Opazimo tudi, da se, z eno samo izjemo (program Ufa) povprečno število bitov na črko kodiranih datotek z rastjo vzorca povečuje. Pri najboljšem, programu Boa Constrictor, se dvigne z 2,12 bita na črko pri drugem vzorcu na 2,16 bita na črko pri osemkrat večjem prvem vzorcu. Ocena 2,2 bita na črko za zgornjo mejo entropije slovenskih leposlovnih besedil (pribl. stokrat večja celota od obeh vzorcev) dobi s tem nov argument.

6.4 Druge entropije

Ker je bil drugi vzorec, kot že rečeno, oblikoslovno označen, je mogoče podati še nekaj vrednosti za entropije, povezane s tem. Iz tabele 85 na naslednji strani vidimo, da znaša slovnična informacija, ki jo vsebuje povprečna beseda v besedilu, slabih 7 bitov (en dodaten znak) in da je ta informacija z besedno obliko že precej dobro določena - razlika med entropijo leme in označenega para je samo 1,618 bita. Na slikah 28, 29 in 30 so navedene krivulje rasti za besedne oblike, za leme in za oblikoslovne oznake v drugem vzorcu.

Primerjava slik pokaže veliko lepši potek krivulje (končni asimptoti se prilega kot tangenta in ne kot sekanta) pri lemah in seveda še lepši pri oblikoslovnih oznakah.

Slika 28: Krivulja rasti za besedne oblike v drugem vzorcu

Slika 29: Krivulja rasti za leme v drugem vzorcu

Slika 30: Krivulja rasti za oblikoslovne oznake v drugem vzorcu