Tehtävä:
Shannonin alaraja

Lyhyt MathCheck-ohje (uuteen välilehteen)

Tarkastellaan suomen­kielisen tekstin esittämistä tieto­koneessa. Tekstissä voi esiintyä pieniä ja isoja kirjaimia, väli­lyöntejä sekä joitakin välimerkkejä. Jos erilaisia merkkejä on `n`, yksin­kertaisinta on esittää kukin merkki `|~log_2 n~|` bitillä. Tämä ei kuitenkaan ole muistin käytön kannalta tehokasta, koska toiset merkit ovat paljon harvinai­sempia kuin toiset. Esimerkiksi q on harvinainen ja e yleinen suomen­kielisissä teksteissä. Tehokkaampaan esitys­tapaan päästään käyttämällä yleisille merkeille vähemmän bittejä kuin harvinaisille. Tässä tehtävässä tutkitaan, kuinka tämä kannattaa tehdä ja miten vähällä määrällä bittejä voidaan selvitä.

Annamme ensin symbolit jatkossa tarvittaville käsitteille ja tutustumme niihin esimerkin avulla. Merkitsemme erilaisten merkkien määrää `n`:llä ja annamme niille indeksit `1, ..., n`. Jos merkit ovat

1234
nkas

niin indeksiä 1 vastaava merkki on n ja indeksiä 2 vastaava merkki on .
tai

Merkitsemme koko tekstin merkkien määrää `m`:llä ja eri merkkien esiintymis­kertojen määriä symboleilla `m_1, ..., m_n`. Jos tekstinä on ananaskana (se on eräs ruoka­laji), niin indeksiä 1 vastaava merkki eli n esiintyy siinä kolmesti. Tämä selittää alla valmiiksi annetun vastauksen. Vastaa muihin kohtiin samalla periaatteella.
`m_1=`,
`m_2 =`,
`m_3 =` ja
`m_4 =`.
tai

Merkintä `sum_(i=1)^n m_i` tarkoittaa `m_1 + m_2 + ... + m_n`. Pätee `m = sum_(i=1)^n m_i`. Ananaskana-esimerkissä `n=` ja `m =`.
tai

Merkitsemme eri merkeille annettujen bitti­kuvioiden pituuksia `l_1, ..., l_n`. Jos annamme ananas­kanan merkeille bitti­kuviot seuraavasti,

1234
nkas
000101011

niin
`l_1 =`,
`l_2 =`,
`l_3 =` ja
`l_4 =`.
tai

Koko tekstin esittämiseen kuluu `sum_(i=1)^n m_i l_i` eli `m_1 l_1 + ... + m_n l_n` bittiä. Ananaskana-esimerkissä
`m_1 l_1 =`,
`m_2 l_2 =`,
`m_3 l_3 =` ja
`m_4 l_4 =`.
tai

Näillä valinnoilla sanan ”ananaskana” esittämiseen kului bittiä. Käyttämällä kullekin merkille `|~log_2 n~| = 2` bittiä olisi kulunut bittiä, joten eri­pituisten bitti­kuvioiden käyttö kannattaa tässä esi­merkissä.
tai

Merkin esiintymis­tiheys on sen esiintymis­kertojen määrä jaettuna tekstin merkkien kokonais­määrällä eli `m_i/m`. Merkitsemme sitä symbolilla `p_i`, siis `p_i = m_i/m`. Ananas­kana-esimerkissä `p_1 = 3/10` ja `p_2=`.
tai

Keskimäärin merkkiä kohti kuluu `1/m sum_(i=1)^n m_i l_i``=``sum_(i=1)^n p_i l_i` bittiä. Tämän luvun haluaisimme saada mahdollisimman pieneksi. Ananas­kana-esimerkissä merkkiä kohti kuluu keski­määrin bittiä (ilmaise desimaali­lukuna).
tai

Tekstiä lukevan ohjelman on tiedettävä käytetyt bitti­kuviot. Yksi mahdollisuus on kertoa ne ennen tekstiä. Se lisää kaikkiaan tarvittavien bittien määrää niin paljon, että hyöty menetetään, jos teksti on lyhyt. Pitkien tekstien tapauksessa menetelmä on silti kannattava. Voidaan myös tehdä niin, että merkkien esiintymis­tiheyksiä ei lasketa siitä tekstistä joka halutaan esittää, vaan lukuina `p_i` käytetään täällä julkaistuja merkkien esiintymis­tiheyksiä suomen­kielessä.

Tavoitteemme on siis valita esitys­tapa siten, että `sum_(i=1)^n p_i l_i` on mahdollisimman pieni, kun luvut `p_i` on annettu. Mitä pienempiä bitti­kuvioiden pituudet eli luvut `l_i` ovat, sitä pienempi tästä summasta tulee. On selvää, että emme saa kaikista luvuista `l_i` miten pieniä tahansa, koska 1-bittisiä bitti­kuviota on vain kaksi eri­laista (0 ja 1), mikä ei riitä, jos `n > 2`. Toisaalta aina voimme saada yhden `l_i`:n ykköseksi valitsemalla yhden merkin bitti­kuvioksi 0 ja kaikille muille merkeille 1-alkuisen bitti­kuvion. On siis olemassa jokin ehto, joka pakottaa valitsemaan osalle luvuista `l_i` suuria arvoja. Seuraavaksi selvitämme tarkasti, mikä tämä ehto on.


Kun eri merkit käyttävät eri määrän bittejä, ongelmaksi tulee, miten tiedetään missä edellisen merkin bitti­kuvio loppuu ja seuraavan alkaa. Tämä on sama kysymys kuin koostuuko yhdys­sana ”kaivosaukko” osista ”kaivo” ja ”saukko” vai ”kaivos” ja ”aukko”. Yksin­kertaisin ja eniten käytetty ratkaisu on sopia, että minkään merkin bitti­kuvio ei saa olla toisen merkin bitti­kuvion aito alku­osa. (Bitti­jonon aito alku­osa on alku­osa, joka on lyhyempi kuin bitti­jono itse.) Jos siis jollekin merkille on annettu bitti­kuvioksi 0100, bitti­kuvioita 01000, 01001, 010000 jne. ei voi antaa millekään merkille.

Tätä ehtoa noudattava esitys­tapa toteuttaa Kraftin epä­yhtälön. Olkoot käytössä olevien bitti­kuvioiden pituudet `l_1, ..., l_n`. Silloin `sum_(i=1)^n 2^(-l_i) <= 1`. Kraftin epäyhtälöä kutsutaan Kraftin epä­yhtälöksi, koska Kraft esitti sen gradussaan vuonna 1949 ja kertoi, että Raymond Redheffer oli keksinyt sen.

Kokeillaan! Laske ym. summa, kun bittikuviot ovat anneutut. Alimmassa tapauksessa ei noudateta aidon alku­osan ehtoa.

{ 0, 10, 11 } tai
{ 00, 010, 10, 11 } tai
{ 00, 010, 1, 011 } tai
{ 00, 01, 1, 10 } tai

Todistamme Kraftin epä­yhtälön induktiolla. Pohja­tapauksessa joukossa on vain yksi bitti­jono, nimittäin tyhjä bitti­jono `varepsilon`. Siis `n=1` ja `l_1 =`. Silloin koko summa on `2^(-l_1) =`.
tai

Induktio­askeleessa oletamme, että Kraftin epä­yhtälö pätee jokaiselle ehtoa noudattavalle joukolle bitti­jonoja, joiden pituus on enintään `n`. Tavoitteena on todistaa, että se pätee myös jokaiselle ehtoa noudattavalle joukolle `B` bitti­jonoja, joiden pituus on enintään .
tai

Jos `B` sisältää tyhjän bitti­jonon, niin muuta siinä ei voi ollakaan, koska tyhjä bitti­jono on jokaisen muun bitti­jonon aito alku­osa, ja ehto kieltää joukon alkiota olemasta toisen alkion aito alku­osa. Olemme jo todistaneet Kraftin epä­yhtälön tässä tilanteessa. Se oli induktion pohja­tapaus.

Muussa tapauksessa `B` koostuu bitti­jonoista muotoa `0 beta` tai `1 beta`, missä `beta` on bitti­jono, jonka pituus on enintään `n`. Olkoon `B_0` niiden `beta` joukko, joille `0 beta in B`, ja olkoon `B_1` niiden `beta` joukko, joille `1 beta in B`. Jos `0 alpha in B` ja `0 beta in B`, niin `alpha` ei voi olla `beta`:n aito alku­osa, koska muutoin `0 alpha` olisi `0 beta`:n aito alku­osa, vastoin oletusta että `B` noudattaa ehtoa. Näin ollen `B_0` noudattaa ehtoa. Induktio-oletuksen vuoksi se noudattaa myös Kraftin epä­yhtälöä. Emme merkitse summaan mitä arvoja `i` saa vaan joukon nimen `B_0`, koska joukon nimi on tässä tilanteessa selkeämpi kuin indeksit. Siis `sum_(B_0) 2^(-l_i) <= 1`. Sama päättely pätee myös `B_1`:lle, joten `sum_(B_1) 2^(-l_i) <=1`.

Koska `B`:n alkiot saadaan lisäämällä `B_0`:n alkioiden eteen `0` ja `B_1`:n alkioiden eteen `1`, pätee

`sum_B 2^(-l_i) = sum_(B_0) 2^(-(l_i+1)) + sum_(B_1) 2^(-(l_i+1))`

Potenssi-, yhteen- ja kertolaskun sääntöjen nojalla
`sum_(B_0) 2^(-(l_i+1)) =``* sum_(B_0) 2^(-l_i)`, joten induktio-oletuksella saadaan `sum_(B_0) 2^(-(l_i+1)) <=`.
tai

Sama pätee `B_1`:lle, joten kaikkiaan
`sum_B 2^(-l_i) <=``+``=`.
tai

Induktio­askel ja samalla Kraftin epä­yhtälön todistus on valmis.


Luku `sum_(i=1)^n p_i l_i` saadaan mahdollisimman pieneksi Huffmanin koodilla. Se muodostetaan seuraavasti. Jos eri merkkejä on vain kaksi, toiselle niistä annetaan bitti­kuvioksi 0 ja toiselle 1. Muussa tapauksessa valitaan kaksi eri merkkiä, joille `p_i` on mahdollisimman pieni. Olkoot niiden indeksit `j` ja `k`. Sitten rakennetaan Huffmanin koodi muunnetulle merkistölle, jossa valittujen kahden merkin sijalla on yksi merkki, jonka esiintymis­tiheys on `p_j + p_k`. Olkoon `beta` se bitti­kuvio, jonka yhdistetty merkki saa tässä esitys­tavassa. Merkeille `j` ja `k` annetaan esitys­tavoiksi `beta 0` ja `beta 1`.

Ananaskana-esimerkissä harvinaisimmat merkit ovat k ja s, joten ne yhdistetään merkiksi ks ja etsitään Huffmanin koodi merkistölle {n, a, ks}. Sen harvinaisimmat merkit ovat ks ja n, joten ne yhdistetään ja etsitään Huffmanin koodi merkistölle {ksn, a}. Nyt valitaan ksn:n bitti­kuvioksi 0 ja a:n bitti­kuvioksi 1. (Aivan yhtä hyvin olisi voitu valita toisin­päin.) Koska ksn tehtiin yhdistämällä ks ja n, lisätään sen bitti­kuvion eli 0:n perään 0, jolloin saadaan n:n bitti­kuvio 00, ja 1, jolloin saadaan ks:n bitti­kuvio 01. Viimeisessä vaiheessa ks:n bitti­kuviosta tehdään k:n bitti­kuvio 010 ja s:n bitti­kuvio 011.

On ilmeistä, että Huffmanin koodi toteuttaa aidon alku­osan ehdon. Sen todistaminen, että Huffmanin koodi minimoi luvun `sum_(i=1)^n p_i l_i` ei ole vaikeaa, mutta jätämme sen tekemättä, koska siitä ei saa MathCheck-kysymyksiä. Sen sijaan arvaamme, missä yhteydessä Huffman keksi koodinsa vuonna 1951.
Päiväkodissa äitienpäiväkorttia tehdessään.
Lukiossa tylsän matematiikan tunnin aikana.
Vastatessaan yliopiston pääsykoe­kysymykseen.
Kirjoittaessaan projekti­raporttia, jolla saattoi korvata tentin.
tai

Nyt tarkastelemme erikois­tapausta, jossa lukujen `p_i` ja `l_i` välinen riippuvuus on poikkeuksellisen helppo. Kun käsitellään vain kahta merkkiä (joista kumpikin saattaa olla yhdistelmä useasta alkuperäisestä merkistä), kummallakin sattuu olemaan sama esiintymis­tiheys `t`. Koska esiintymis­tiheyksien summa on 1, pätee `t=`. Toinen merkki saa bitti­kuviokseen 0 ja toinen 1, joten bitti­kuvion pituus on .
tai

Oletamme myös, että kun jaetaan merkki kahdeksi, kummallakin sattuu olemaan sama esiintymis­tiheys. Jos merkin bitti­kuvion pituus on `j`, niin siitä syntyvien kahden merkin bitti­kuvioiden pituus on . Jos `j=1`, niin alkuperäisen merkin esiintymis­tiheys on se mikä edellä pääteltiin, ja kummankin syntyvän merkin esiintymis­tiheys on . Jos `j=2`, niin kummankin syntyvän merkin esiintymis­tiheys on . Jos merkin bitti­kuvion pituus on `j`, niin merkin esiintymis­tiheys on .
tai

Erikois­tapauksessamme laskimme `p_i`:n tiedosta, että `l_i = j`. Jos ratkaisemme siitä `l_i`:n `p_i`:n funktiona, saamme `l_i = -log_2 p_i`. Keskimäärin käytetylle bittien määrälle merkkiä kohti saamme lausekkeen `sum_(i=1)^n p_i l_i``=``-sum_(i=1)^n p_i log_2 p_i`. Yleisessä tapauksessa ei voi aina olla `l_i = -log_2 p_i`, koska `l_i` on luonnollinen luku mutta `-log_2 p_i` ei välttämättä ole luonnollinen luku. Voidaan kuitenkin todistaa, että yleisessä tapauksessa `sum_(i=1)^n p_i l_i``>=``-sum_(i=1)^n p_i log_2 p_i`. Tämä on Claude Shannonin vuonna 1948 todistama ala­raja sille, kuinka tiiviisti tietoa voidaan pakata, jos oletetaan, että merkkien esiintyminen on toisistaan riippumatonta. (Oletus ei aina päde: esimerkiksi suomen­kielessä seuraava merkki on hyvin harvoin t, jos kaksi edellistä ovat olleet t. Shannonin teoria on kuitenkin erin­omainen alku tiedon pakkaamisen tutkimiselle.)

Lopuksi johdamme, mitä Shannonin ala­rajaksi tulee, jos oletamme, että jokainen merkki esiintyy yhtä usein. Koska MathCheckissä ei ole kaksi­kantaista logaritmia, kirjoita sen sijaan esim. (ln x)/(ln 2). Koska merkkejä on `n`, saamme `p_i =`, `log_2 p_i =` ja `-sum_(i=0)^n p_i log_2 p_i =`. Toivottavasti muistat nähneesi jotain saman­näköistä aikaisemmin jossain yhteydessä!
tai