Nazaj: Statistični opis      Naprej: Sklep      Kazalo    Začetek    Konec

Doktorska disertacija P. Jakopina, str. 89 - 114

6. poglavje

Entropija

6.1  Definicije
6.2  Entropija n-terčkov za oba vzorca
     6.2.1  Algoritem
     6.2.2  Rezultati
6.3  Ocena entropije z modelom
     6.3.1  Huffmanovo kodiranje
     6.3.2  Izbira postopka
     6.3.2  Model z razrezom na enako dolge n-terčke
     6.3.4  Model z razrezom na besede
     6.3.5  Model z optimalnim razrezom na n-terčke
     6.3.6  Komprimiranje vzorcev z drugimi programi
6.4  Druge entropije

Č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, pi pa verjetnost pojavitve i-tega stanja. Vse verjetnosti pi 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 fi 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 Hn 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 Fn, 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 F1 = H1. 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 Hn (entropija na znak) in pogojna entropija Hn 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

Tabela 67: Entropije znakovnih n-terčkov v drugem vzorcu

                Vseh   Različnih   Povprečna       Novih
n   H    Hn    Fn    n-terčkov   n-terčkov   frekvenca   Enkratnic   enkratnic
 
1    4,459   4,459   4,459   2.296.775    101   22.740,35    2    2
2    7,963   3,982   3,504   2.296.700    1.841    1.247,53    324    322
3   10,911   3,637   2,948   2.296.625    13.121    175,03    2.712    2.388
4   13,315   3,329   2,404   2.296.550    62.078    36,99    16.815    14.103
5   15,283   3,057   1,968   2.296.475    196.532    11,68    74.095    57.287
6   16,887   2,815   1,604   2.296.400    449.426    5,11    228.307   154.222
7   18,123   2,589   1,236   2.296.325    773.038    2,97    485.939   257.654
8   19,030   2,379   0,907   2.296.250   1.091.856    2,10    784.557   298.645
9   19,677   2,186   0,647   2.296.175   1.371.101    1,67   1.074.334   289.811
10   20,130   2,013   0,453   2.296.100   1.600.442    1,43   1.332.741   258.450
11   20,440   1,858   0,310   2.296.025   1.779.061    1,29   1.548.459   215.769
12   20,649   1,721   0,209   2.295.950   1.912.514    1,20   1.719.968   171.564
13   20,788   1,599   0,139   2.295.875   2.009.353    1,14   1.850.505   130.597
14   20,882   1,492   0,094   2.295.800   2.079.296    1,10   1.948.967    98.525
15   20,946   1,396   0,064   2.295.725   2.129.397    1,08   2.022.425    73.525
16   20,989   1,312   0,043   2.295.650   2.165.325    1,06   2.076.840    54.483
17   21,019   1,236   0,030   2.295.575   2.191.073    1,05   2.117.018    40.250
18   21,041   1,169   0,022   2.295.500   2.209.902    1,04   2.146.991    30.046
19   21,056   1,108   0,015   2.295.425   2.223.711    1,03   2.169.345    22.428
20   21,068   1,053   0,012   2.295.350   2.233.987    1,03   2.186.180    16.909
21   21,076   1,004   0,008   2.295.275   2.241.786    1,02   2.199.090    12.984
22   21,083   0,958   0,007   2.295.200   2.247.697    1,02   2.208.987    9.971
23   21,088   0,917   0,005   2.295.125   2.252.252    1,02   2.216.714    7.801
24   21,092   0,879   0,004   2.295.050   2.255.838    1,02   2.222.841    6.201

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.

Tabela 68: Entropije znakovnih n-terčkov v prvem vzorcu
                   Vseh   Različnih   Povprečna       Novih
n   H      Hn    Fn    n-terčkov   n-terčkov   frekvenca   Enkratnic   enkratnic
 
1    4,456   4,456   4,456   15.802.362    133   118.814,75    10    10
2    7,994   3,997   3,538   15.801.851    3.683    4.290,48    571    561
3   11,020   3,673   3,026   15.801.340    30.023    526,31    7.270    6.699
4   13,565   3,391   2,545   15.800.829    149.094    105,98    45.446    38.179
5   15,739   3,148   2,174   15.800.318    528.051    29,92    195.247    149.811
6   17,643   2,941   1,904   15.799.807    1.441.169    10,96    655.505    460.288
7   19,272   2,753   1,629   15.799.296    3.066.203    5,15    1.716.853   1.061.411
8   20,587   2,573   1,315   15.798.785    5.177.804    3,05    3.416.698   1.699.956
9   21,594   2,399   1,007   15.798.274    7.375.385    2,14    5.462.046   2.045.508
10   22,334   2,233   0,740   15.797.763    9.385.084    1,68    7.533.769   2.071.930
11   22,861   2,078   0,527   15.797.252   11.078.807    1,43    9.424.877   1.891.364
12   23,221   1,935   0,360   15.796.741   12.420.307    1,27   11.030.525   1.605.966
13   23,460   1,805   0,239   15.796.230   13.422.587    1,18   12.307.935   1.277.779
14   23,615   1,687   0,155   15.795.719   14.139.003    1,12   13.270.707    963.177
15   23,715   1,581   0,100   15.795.208   14.638.044    1,08   13.972.904    702.621
16   23,779   1,486   0,064   15.794.697   14.980.642    1,05   14.474.510    502.046
17   23,821   1,401   0,042   15.794.186   15.213.792    1,04   14.827.769    353.712
18   23,848   1,325   0,027   15.793.675   15.372.308    1,03   15.075.733    248.432
19   23,866   1,256   0,018   15.793.164   15.479.668    1,02   15.248.294    173.043
20   23,878   1,194   0,012   15.792.653   15.553.149    1,02   15.368.825    121.018
21   23,886   1,137   0,008   15.792.142   15.604.148    1,01   15.453.885    85.550
22   23,891   1,086   0,005   15.791.631   15.640.078    1,01   15.514.768    61.376
23   23,895   1,039   0,004   15.791.120   15.665.784    1,01   15.559.113    44.840
24   23,898   0,996   0,003   15.790.609   15.684.179    1,01   15.591.459    32.847

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:

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 fi > 1, mogoče dobro aproksimirati s kvadratnim korenom iz fi, 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 fi,n+1 (na koraku (n+1)) 3 ali manj - zanje je bil rezervirano fi,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, Hn, 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 Fn (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 H1 (2,228 bita na znak), znane ocene za limito entropije Hn, 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.

Tabela 69: Znaki povedi Gori_na_gori_gori. s frekvencami in Shannon-Fanojevimi kodami

_3   00
i3   010
o3   011
r3   100
g2   101
a1   1100
G1   1101
n1   1110
.1   1111

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).


Algoritem Huffmanovega kodiranja lahko na kratko opišemo s štirimi koraki:
  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.

Tabela 70: Primer Huffmanovega drevesa z znaki povedi iz drugega vzorca

e 12   e 12   e 12   e 12   e 12   e 12    e 12    e 12    e 12    e 12    e 12    e 12    e 12    e 12    e 12    ,.szjrtlPac 16   _vdo 18    enučm 24    _vdo,.szjrtlPac 34   _vdo,.szjrtlPacenučm 58
_ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    _ 9    nučm 12    e 12    ,.szjrtlPac 16   _vdo 18    enučm 24
o 4    o 4    o 4    o 4    o 4    o 4    o 4    o 4    vd 5    nu 6    nu 6    ,.szjr 8   ,.szjr 8   vdo 9    _ 9    nučm 12    e 12    ,.szjrtlPac 16
t 4    t 4    t 4    t 4    t 4    t 4    t 4    t 4    o 4    vd 5    čm 6    nu 6    tlPac 8    ,.szjr 8   vdo 9    _ 9    nučm 12
č 3    č 3    č 3    č 3    č 3    lPac 4   lPac 4   lPac 4   t 4    o 4    vd 5    čm 6    nu 6    tlPac 8    ,.szjr 8   vdo 9
m 3    m 3    m 3    m 3    m 3    č 3    ,.sz 4   ,.sz 4   lPac 4   t 4    o 4    vd 5    čm 6    nu 6    tlPac 8
n 3    n 3    n 3    n 3    n 3    m 3    č 3    jr 4    ,.sz 4   lPac 4   t 4    o 4    vd 5    čm 6
u 3    u 3    u 3    u 3    u 3    n 3    m 3    č 3    jr 4    ,.sz 4   lPac 4   t 4    o 4
v 3    v 3    v 3    v 3    v 3    u 3    n 3    m 3    č 3    jr 4    ,.sz 4   lPac 4
d 2    d 2    d 2    d 2    d 2    v 3    u 3    n 3    m 3    č 3    jr 4
j 2    j 2    j 2    j 2    j 2    d 2    v 3    u 3    n 3    m 3
r 2    r 2    r 2    r 2    r 2    j 2    d 2    v 3    u 3
a 1    ,. 2   ,. 2   ,. 2   ,. 2   r 2    j 2    d 2
c 1    a 1    sz 2   sz 2   sz 2   ,. 2    r 2
l 1    c 1    a 1    lP 2   lP 2   sz 2
P 1    l 1    c 1    a 1    ac 2
s 1    P 1    l 1    c 1
z 1    s 1    P 1
, 1    z 1
. 1 

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.

Tabela 71: Znaki iz tabele 70 s frekvencami, Shannon-Fanojevimi in Huffmanovimi kodami

e12   00    10
_ 9   010    000
o 4   0110    0011
t 4   0111    0110
č 3   1000    1110
m 3   1001    1111
n 3   1010    1100
u 3   10110    1101
v 3   10111    00100
d 2   11000    00101
j 2   11001    01010
r 2   11010    01011
a 1   11011    011110
c 1   11100    011111
l 1   111010   011100
P 1   111011   011101
s 1   111100   010010
z 1   111101   010011
, 1   111110   010000
. 1   111111   010001

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).

Tabela 72: Huffmanov kod za črke, števke in ločila slovenskih leposlovnih besedil

A   0,000928550   1001010100   o   0,069218303   0101   
B   0,000807521   1001011010   ó   0,000037784   000011110100100   
C   0,000184813   100101111111   ò   0,000000649   00001010100011100110   
Č   0,000346868   10111111011   ô   0,000006216   10010100000111101   
D   0,000659466   00001010010   p   0,024119859   10110   
E   0,000211732   100101010111   q   0,000015297   1001010000001011   
F   0,000193245   100101111101   r   0,038129672   00111   
G   0,000433410   10010101010   s   0,037610100   01000   
H   0,000273084   000011110101   š   0,007468506   1000001   
I   0,000826711   1001010110   t   0,031742312   01111   
J   0,000599303   00001010101   u   0,014322898   100001   
K   0,001491528   101111000   ú   0,000006865   10010100000111100   
L   0,000532762   00001111100   ù   0,000006216   000010101000111000   
M   0,001159038   0000111100   v   0,027802165   10001   
N   0,001457798   101111001   w   0,000036487   000011110100101   
O   0,000799846   1001011011   x   0,000033946   100101000000100   
P   0,001884829   100101001   y   0,000172704   101111110101   
Q   0,000017297   0000101010001111   z   0,015412152   011101   
R   0,000482924   10010100010   ž   0,004836480   00001110   
S   0,001338932   0000101000   0   0,000141515   1001010000000   
Š   0,000211516   100101111100   1   0,000349030   10111111001   
T   0,001623692   100101100   2   0,000232975   100101000110   
U   0,000157137   0000101010010   3   0,000164650   0000101010000   
V   0,001209525   0000101011   4   0,000124326   1001010000010   
W   0,000062109   10010100000011   5   0,000106866   1001010101100   
X   0,000029244   100101000001101   6   0,000095460   1001011111100   
Y   0,000012108   1001010000011111   7   0,000084812   00001010100010   
Z   0,000795197   1001011110   8   0,000106433   1001010101101   
Ž   0,000145893   0000111101000   9   0,000109461   1001010001111   
a   0,079735811   0010       0,187343573   11   
á   0,000067460   00001111010011   !   0,001592124   100101110   
à   0,000008324   10010100000010101   '   0,000048649   10010111111010   
â   0,000007243   10010100000111001   (   0,000087731   1011111101001   
b   0,014135058   100100   )   0,000087839   1011111101000   
c   0,004918697   00001011   *   0,000502113   10010100001   
č   0,011080487   0000100   ,   0,016751138   011100   
ć   0,000004649   0000101010001110010   -   0,001385527   101111111   
d   0,025467980   10100   -   0,000146488   0000101010011   
e   0,082316215   0001   .   0,009900151   0000110   
é   0,000113244   1001010001110   /   0,000014162   1001010000011101   
è   0,000029784   100101000001100   :   0,000811576   1001010111   
ê   0,000007784   10010100000111000   ;   0,000529843   00001111101   
f   0,000653844   00001010011   ?   0,001022929   0000111111   
g   0,012188660   101110   Q   0,000546600   00001111011   
h   0,007800023   1000000   k   0,002906677   10111101   
i   0,068865705   0110   j   0,002906677   10111110   
í   0,000038000   000010101000110   Ş   0,000181786   101111110000   
ì   0,000000486   00001010100011100111   Ť   0,000181786   101111110001   
j   0,035433430   01001   Ś   0,000008595   00001010100011101   
k   0,027060212   10011   š   0,000008595   10010100000010100   
l   0,040057475   00110   §   0,000021892   100101111110110   
m   0,024314618   10101   ş   0,000021892   100101111110111   
n   0,047316249   00000   

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

Tabela 73: Dolžine Huffmanovih kod pri razrezu prvega vzorca na n-terčke

n    vseh    različnih   skupno   bitov    najkrajša    najdaljša
   n-terčkov   n-terčkov   bitov    na črko   Huff. koda   Huff. koda
   
1   15.802.872    133   71.160.133   4.5030    3   24
2    7.901.436    3.280   63.368.664   4.0099    5   23
3    5.267.624    22.677   58.191.686   3.6823    7   22
4    3.950.718    96.318   53.621.781   3.3932    7   22
5    3.160.574    280.525   49.537.784   3.1347    9   22
6    2.633.812    589.240   45.756.764   2.8955   10   21
7    2.257.553    919.393   41.992.115   2.6572   10   21
8    1.975.359    1.156.054   38.323.126   2.4251   11   21
9    1.755.874    1.275.809   34.938.247   2.2109   11   21
10    1.580.287    1.310.359   31.859.619   2.0161   13   21
11    1.436.624    1.289.850   29.104.778   1.8417   14   20
12    1.316.906    1.238.465   26.673.762   1.6879   15   21
13    1.215.605    1.173.826   24.544.717   1.5532   15   21
14    1.128.776    1.106.523   22.684.277   1.4355   16   21
15    1.053.524    1.041.361   21.053.062   1.3322   17   20
16    987.679    980.920   19.677.795   1.2452   16   19
17    929.580    925.682   18.464.196   1.1684   16   20
18    877.937    875.628   17.383.179   1.1000   16   20
19    831.730    830.217   16.414.586   1.0387   17   19
20    790.143    789.239   15.542.545   0.9835   17   20

Tabela 74: Dolžine Huffmanovih kod pri razrezu drugega vzorca na n-terčke

n    vseh    različnih   skupno   bitov    najkrajša    najdaljša
   n-terčkov   n-terčkov   bitov    na črko   Huff. koda   Huff. koda
   
1   2.296.849    101   10.345.994   4.5044    2   21
2   1.148.424    1.611    9.177.023   3.9955    5   20
3    765.456    10.292    8.366.728   3.6427    6   20
4    574.212    41.174    7.626.828   3.3206    7   19
5    459.369    98.603    6.919.121   3.0124    9   19
6    382.808   159.760    6.242.933   2.7180    9   19
7    328.121   197.771    5.586.563   2.4323    9   19
8    287.106   213.629    4.991.709   2.1733   11   18
9    255.205   214.456    4.473.365   1.9476   11   18
10    229.684   207.291    4.043.712   1.7606   11   18
11    208.804   196.467    3.674.764   1.5999   12   18
12    191.404   184.618    3.358.406   1.4622   13   18
13    176.680   172.688    3.085.576   1.3434   13   18
14    164.060   161.665    2.849.628   1.2407   14   18
15    153.123   151.710    2.644.098   1.1512   14   17
16    143.553   142.613    2.463.311   1.0725   15   17
17    135.108   134.468    2.303.519   1.0029   14   18
18    127.602   127.126    2.164.754   0.9425   14   17
19    120.886   120.204    2.043.466   0.8897   14   17
20    114.842   114.594    1.935.556   0.8427   14   16

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:

... |priči|_|izginila|._>>|Kaj|_|le|_|rogovilim|_|s|_|to|_|angleščino|!<<_|sem|_|se|_|ozmerjal|._>>| Tennysona|_|recitiraš|,<<_|me|_|je|_|zaničljivo|_|opomnila|_|pamet|._>>|Saj|_|vem|,<<_|sem|_| zamrmral| ...

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:

Tabela 75: Število enot in dolžine Huffmanovih kod pri razrezu na besede

    vseh    besednih   različnih   skupaj   bitov
   znakov    enot     enot     bitov   na znak
       
Prvi vzorec   15.802.362   5.446.180   176.792   41.323.662   2.62
Drugi vzorec   2.296.775    818.362    40.747    5.905.093   2.57

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.

Tabela 76: Najpogosteše besedne enote, njihove frekvence in Huffmanove kode

     prvi vzorec        drugi vzorec
 
enotafrekvenca   Huffmanova   enotafrekvenca   Huffmanova
          koda         koda
 
_2.214.919   1    _329.333   1
,_258.876   00010    ,_33.989   00100
je150.558   01110    je25.768   01011
._119.505   001000    ._20.586   000001
in87.126   010100    in16.555   001010
se69.576   0000001    se13.306   010101
v51.034   0011010    v7.168   0100011
da43.590   0101010    da5.159   00000011
na34.025   00000110    na4.674   00010001
so32.915   00001010    so4.242   00011100
ne24.867   00111001    pa4.224   00011101
pa24.114   01000001    ._k3.941   00111011
ki23.238   01000110    bi3.219   01100001
bi21.862   01001111    ne3.178   01100100
za19.092   01101001    ga3.035   01101111
z18.912   01101100    z3.017   01110000
sem18.300   01111011    ki2.993   01110010
ni18.048   01111101    sem2.793   01111011
._k17.766   000000000    po2.771   01111101
ga15.524   000111011    ni2.532   000011000

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.

Tabela 77: Število n-terčkov (n=1-32) prvega vzorca za minimalne frekvence

minimalna   različnih    vseh
frekvenca   n-terčkov   n-terčkov
10    1.454.567   120.517.900
5    3.427.898   133.038.634
2   16.401.724   164.019.971

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.

Tabela 78: Primer entropijsko najugodnejšega razreza povedi iz drugega vzorca

10.Tisti|_pomladni|_dan_je_bil_|lep,_|svetel_|in_zve|neč,_|kakor_iz_|čistega|_srebr|a_uli|t._Re|
5.Tisti|_pomladni|_dan_je_bil|_lep,_|svetel_in_|zveneč|,_kakor_iz_|čistega|_srebra_|ulit|._Res_je,_da_|
2.Tisti|_pomladni_dan|_je_bil_lep,_|svetel_in_|zveneč|,_kakor_|iz_čistega_sr|ebra|_ulit|._Res_je,_da_s|

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.

Tabela 79: N-terčki prvega vzorca s frekvenco vsaj 10, z dolžinami Huffmanovih kod

T 12         o 7    p 8    _ 5    i 7
Ti 15        om 11    po 10    _p 9    i_ 9
Tis 18       oml 18    pom 14    _po 10    i_p 12
Tist 18      omla 19    poml 19    _pom 14    i_po 13
Tisti 19     omlad 19    pomla 19    _poml 19    i_pom 17
Tisti_ 20    omladn 22    pomlad 19    _pomla 19    i_poml 23
Tisti_p 23   omladni 23   pomladn 23    _pomlad 20    i_pomla 23
                 pomladni 23   _pomladn 23    i_pomlad 23
                     _pomladni 23   

_ 5               i 7    n 7    l 8    _ 5    l 8
_d 10             i_ 9    ni 10    le 11    _l 12    l_ 10
_da 11            i_d 13    ni_ 12    lep 14    _le 13    l_l 17
_dan 15           i_da 16    ni_d 16    lep, 20    _lep 15    l_le 18
_dan_ 16          i_dan 17    ni_da 18    lep,_ 20   _lep,_ 22   l_lep 20
_dan_j 20         i_dan_ 18    ni_dan 20
_dan_je 20        i_dan_j 21    ni_dan_ 21
_dan_je_ 20       i_dan_je 21    
_dan_je_b 22      i_dan_je_ 21    
_dan_je_bi 22     i_dan_je_b 23    
_dan_je_bil 22    i_dan_je_bi 23    
_dan_je_bil_ 22   i_dan_je_bil 23   

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.

Tabela 80: Rezultati optimalnega razreza drugega vzorca z n-terčki prvega

minimalna   znakov   nizov po    povprečna    skupaj   bitov na
frekvenca        razrezu   dolžina nizov   bitov     znak
10   2.296.775   331.153   6.94   6.647.122   2,89
5   2.296.775   305.344   7.52   6.469.638   2,82
2   2.296.775   273.301   8.40   6.245.660   2,72

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:

Tabela 81: Rezultati optimalnega razreza druge polovice 2. vzorca z n-terčki prve polovice

minimalna   različnih    vseh    bitov na
frekvenca   n-terčkov   n-terčkov    znak
10    104.040    6.607.609   3,08
5    252.415    7.548.271   2,96
2   1.119.263    9.640.829   2,81
1   2.375.354   11.041.782   2,78

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).

Tabela 82: Preizkus modela na besedilu Platonove Države v 16 jezikih

    jezik prevodleto   prenos v el. oblikobesed   znakov   b/z
       
 slovenski  Jože Košar 1976   Primož Jakopin 92.741   565.604   2,37
1. srbohrvaški A. Vilhar, B. Pavlović1983   Duško Vitas 107.506   613.082   3,77
2. hrvaški  Damir Salopek 1976   Marko Tadić 92.870   532.497   3,84
3. bolgarski   - -    Patrice Bonhomme 112.676   678.131   3,96
4. češki  Radislav Hošek 1993   František Čermák 110.466   636.201   4,10
5. poljski  Wladyslaw Witwicki 1991    - 107.559   645.532   4,32
6. ruski   - -     - 99.503   649.102   4,46
7. slovaški  Július Španár 1990   Alexandra Jarošová 99.661   622.463   4,46
8. latvijski  Gustavs Lukstinš 1982   Andrejs Spektors 45.238   290.508   4,74
9. litvanski  Jonas Dumčius 1981    - 85.144   584.318   4,94
10. angleški  Paul Shorey -     - 129.331   692.058   5,40
11. francoski   - 1993    - 142.624   817.658   5,67
12. nemški  Karl Vretska 1982   Joachim Hohwieler 104.876   641.333   5,69
13. romunski  Andrei Cornea 1986   Dan Tufis 131.064   658.804   5,76
14. finski  Marja Itkonen-Kaila -    Anna Mauranen 75.800   582.522   6,11
15. madžarski  Szabó Miklós 1984   Tamás Váradi 105.538   728.501   6,47

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.

Tabela 83: Komprimiranje prvega vzorca s tujimi komprimirnimi programi

ime        verzija   dobavitelj   državaleto   tipdolžina    stikalačas iz.  bitov
programa                programa    v sek. /znak
     
ARJ  2.60  ARJ Software  US1997   sh203.199   -m1 -jm 84   3,27
ESP  1.92  GyikSoft  HU1996   fw 12.644    - 60   3,22
PKZIP  2.04g  PKWARE  US1993   sh 42.166   -ex 74   3,20
RAR  2.50b3  RarSoft  FI1999   sh105.224   -m5 138   3,09
JAR  1.02  ARJ Software  US1997   sh343.030   -m4 195   3,00
UHARC  0.2  Uwe Harklotz  GE1997   sh 99.444   -m3 751   2,73
Arhangel 1.38  Jurij Ljapko  UA1999   sh 76.416    - 188   2,52
Ufa  0.04b1  Igor Pavlov  RU1998   sh133.632   -m5 -mu32 703   2,24
RKIVE  1.92b1  Malcolm Taylor NZ1998   sh120.740   -mt3 2.148   2,23
Boa  0.58b  Ian Sutton  CA1998   sh105.984   -m15 756   2,16


Tabela 84: Komprimiranje drugega vzorca s tujimi komprimirnimi programi

ime        verzija   dobavitelj   državaleto   tipdolžina    stikalačas iz.  bitov
programa                programa    v sek. /znak
     
ARJ  2.60  ARJ Software  US1997   sh203.199   -m1 -jm 13   3,19
ESP  1.92  GyikSoft  HU1996   fw 12.644    - 9   3,14
PKZIP  2.04g  PKWARE  US1993   sh 42.166   -ex 10   3,12
RAR  2.50b3  RarSoft  FI1999   sh105.224   -m5 19   3,01
JAR  1.02  ARJ Software  US1997   sh343.030   -m4 31   2,89
UHARC  0.2  Uwe Harklotz  GE1997   sh 99.444   -m3 84   2,63
Arhangel 1.38  Jurij Ljapko  UA1999   sh 76.416    - 28   2,48
Ufa  0.04b1  Igor Pavlov  RU1998   sh133.632   -m5 -mu32 105   2,25
RKIVE  1.92b1  Malcolm Taylor NZ1998   sh120.740   -mt3 270   2,10
Boa  0.58b  Ian Sutton  CA1998   sh105.984   -m15 100   2,12

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.

Tabela 85: Entropije besednih oblik in lem iz drugega vzorca

                                                     n    entropija
                                                         na enoto
     
različnih parov (besedna oblika,oblikoslovna oznaka)  44.858  11,201
različnih lem (osnovnih besednih oblik)               15.140   9,582
različnih oblikoslovnih oznak                          1.498   6,607

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




Naslov strani: http://www.jakopin.net/primoz/disertacija/entropija.html        Datum: 26. junij 1999. Zadnja sprememba: 10. september 2013.        

Naprej: Sklep      Nazaj: Statistični opis      Kazalo    Začetek    Konec