«Regn, seinare regnbyer.» Kor mykje informasjon er det i meldinga frå Vêrvarslinga på Vestlandet? Inga. Dei seier det same kvar gong.

Eg, den vesle guten, sit åleine saman med radioen den regntunge sumaren. Dei vaksne søv middag. Eg kosar meg med kodekryssord. Ved å telja bokstavar og sjå på endingar av ord har eg alt fått dei mest vanlege bokstavane – E, R og T – på plass. Så er det å sjå etter kombinasjonar av to bokstaver. Er dei like, er det som regel konsonantar. Etter det er det litt prøving og feiling, så er det heile på plass. Eg har drive med frekvensanalyse utan å vite det. Slik analyse har kode­knekkarar halde på med i uminnelege tider.

Eg veit ikkje om Alfred Vail var spesielt glad i å lesa aviser, men det var det han gjorde då han saman med Samuel Morse utvikla morsekoden. Han talde førekomstar av einskilde bokstavar. Bokstaven e, som dukka opp oftast, blei til ein prikk. Sjeldne bokstaver, som q, blei til tre strekar og ein prikk. På den måten klarte dei å komprimera meldingane som blei sende med telegrafen deira. Børsmenn som bruka telegrafen, syntest han var dyr. Dei laga difor kodar på toppen av morsekoden for å komprimera endå meir. Dei utnytta det at språk inneheld meir informasjon enn strengt tatt nødvendig – språk har redundans. Prisen dei måtte betala dersom ein feiltolka ein strek eller prikk, var at heile meldinga blei uforståeleg.

Hundre år etter Vail og Morse var det ein liten gut på bondelandet i USA som laga sin eigen vesle telegraf. Han blei fascinert av prikkane og strekane og korleis dei var fordelte.

Som 21-åring skreiv han den mest banebrytande hovudoppgåva i historia. Han såg samanhengen mellom matematisk logikk og elektriske krinsar som hadde gått alle dei andre hus forbi.

Claude Shannon blei far til den moderne digitale teknologien. Med ein slik prestasjon opna alle dører seg. Shannon fekk jobb på Bell Labs. I arbeidstida var han kodeknekkar, og på fritida utvikla han informasjonsteori. Det tok han ti år.

Me skal no sjå på første delen av arbeidet hans, som omhandla komprimering. Ved eit seinare høve skal me kosa oss med kommunikasjonsbiten.

Shannon byrja med å omsetja prikkane og strekane i morsekoden til binære kodar sette saman av 0 og 1 – såkalla bit. E, som er * i morsekoden, vart til 1, og Q, som er - - * -, vart til 0010. Så spurde han seg sjølv om det var mogleg å finna ei nedre grense for komprimering som dei ulike kodane kunne målast mot. Eit mål for gjennomsnittleg informasjonsmengd i ein lang morsemelding er:

Her er p sannsyn for ein bokstav og l lengda i morsekode for same bokstaven. Ein treng altså i morsekoden i gjennomsnitt 4,8 bit for å koda ein bokstav. Med dette som utgangspunkt kom Shannon opp med følgande formel for nedre grense for komprimering:

Shannon kalla denne grensa entropien H. Entropien er eigentleg eit mål på uvissa om det neste som kjem. Shannon tok 2-logaritmen av det omvende sannsynet, slik at bokstavar som dukka opp, sjeldan fekk den lengste binære koden. Det er fascinerande å sjå at Vail og Morse var berre 15 prosent unna ei optimal komprimering på bokstavnivå.

Shannon gjekk vidare og såg på frekvensen av ord. Han tok dei 8727 mest vanlege engelske orda og rekna ut entropien:

? tyder sum. Med ei gjennomsnittleg ordlengde på ein stad mellom 4 og 5 blir entropien 2,3 bit per bokstav. Entropien, uvissa om kva som kjem, er sjølvsagt mindre på ordnivå enn på bokstavnivå.

Shannon fann den nedre grensa, men fortalde ikkje korleis ein kunne nå han. Det tok ikkje lang tid frå han publiserte resultata sine, til den optimale løysinga kom. Nærare enn Huffman-koden kjem ein ikkje til grensa. I figur 1 ser du eit eksempel med fem meldingar, m1 til m5, og forskjellig sannsyn p(mk). Som vist til høgre i figuren grupperer ein dei to med lågast sannsyn til kvar tid, og ein endar opp med binære meldingar av ulik lengde som har minst mogleg entropi. Meldingane med minst sannsyn, m4 og m5, blir koda med tre binære siffer, 000 og 001, mens dei andre blir koda med to siffer: m1 01, m2 10 og m3 11.

Figur 1. Huffman-koding

Huffman-koden er vel og bra dersom ein på førehand kjenner sannsynfordelinga på meldingane. Det gjer ein som regel ikkje. Når du lagar zipfiler av tekst du skriv, veit ikkje programvara som skal koda, noko som helst om korleis du brukar språket. Då blir ein såkalla LZW (Lempel-Ziv-Welch)-algoritme, som kodar undervegs, nytta. La oss sjå på eit overkommeleg døme gitt i figur 2.

Figur 2. Radbrekking av Shakespeare med LZW

I utgangspunktet har ein 26 bokstavar. Dei får kode #1 til #26. Så lager ein kodane #27, #28 og så vidare for samansette bokstavar etter som ein møter på dei i teksta. Når ein møter bokstavkombinasjonane igjen, understreka, blir dei bytte ut med tilhøyrande kode. Ein ser òg at første gongen ein møter to bokstavar ein alt har kode for, så startar ein å laga kode for tre bokstaver, og etter kvart har ein kodar for lange sekvensar av vanlege bokstavkombinasjonar, og teksta blir komprimert.

Det kan visast matematisk at LZW nærmar seg grensa H, som Shannon fann, for lange sekvensar av bokstavar. Når ein ønsker å dekoda fila, er det berre å køyra same sekvens. Ein finn kodar for samansette bokstavar og puttar dei inn der det er kodar for dei i den komprimerte fila.

Gode greier, men kan ein vera sikker på at alle filer vert komprimerte? Nei. Tenk at du har ei mengd forskjellige filer av same lengde. Filene består av 0 og 1. Du kan sjå på ei fil som eit stort binært tal. Dersom talet på filer du har, er større enn det største talet ei fil kan representera, må nokre av filene bli større enn den originale. Viss ikkje vil nokre forskjellige filer bli komprimerte til den same fila, og då er ikkje algoritmen eintydig. Trøysta får vera at det ikkje lenger er nokon som kan fatta seg kort og konsist.

Per Thorvaldsen

per.eilif.thorvaldsen@hvl.no