JavaScript is disabled in your web browser or browser is too old to support JavaScript. Today almost all web pages contain JavaScript, a scripting programming language that runs on visitor's web browser. It makes web pages functional for specific purposes and if disabled for some reason, the content or the functionality of the web page can be limited or unavailable.

Takk for at du vil dele artikkelen

Den du deler artikkelen med, kan lese og eventuelt lytte til heile artikkelen.
Det gjer vi for at fleire skal oppdage DAG OG TID.

Namnet ditt vert synleg for alle du deler artikkelen med.

TeknologiFeature

Datakomprimering

Kvar veke les vi inn utvalde artiklar, som abonnentane våre kan lytte til.
Lytt til artikkelen
Claude Shannon blei far til den moderne digitale teknologien.

Claude Shannon blei far til den moderne digitale teknologien.

Claude Shannon blei far til den moderne digitale teknologien.

Claude Shannon blei far til den moderne digitale teknologien.

5920
20210319
5920
20210319

«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

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

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

Digital tilgang til DAG OG TID – heilt utan binding

Prøv ein månad for kr 49.
Deretter kr 199 per månad. Stopp når du vil.


Eller kjøp eit anna abonnement

«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

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

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

Claude Shannon byrja med å omsetja prikkane og strekane i morsekoden til binære kodar sette saman
av 0 og 1 – såkalla bit.

Emneknaggar

Fleire artiklar

Etter valet i 2016 blei det vanleg å seie at Trump vann fordi folk hadde oversett kjenslene til den kvite arbeiderklassa. Er biletet eit anna i denne omgangen?

Etter valet i 2016 blei det vanleg å seie at Trump vann fordi folk hadde oversett kjenslene til den kvite arbeiderklassa. Er biletet eit anna i denne omgangen?

Foto: Dustin Chambers / Reuters / NTB

UtanriksSamfunn

Overkorrigeringa

NEW YORK: Mark Lilla fekk enorm merksemd for sin diagnose av presidentvalet i USA i 2016. Eg oppsøker han for å få oppdaterte psykologiseringar av den amerikanske folkesjela anno 2024.

Ida Lødemel Tvedt
Etter valet i 2016 blei det vanleg å seie at Trump vann fordi folk hadde oversett kjenslene til den kvite arbeiderklassa. Er biletet eit anna i denne omgangen?

Etter valet i 2016 blei det vanleg å seie at Trump vann fordi folk hadde oversett kjenslene til den kvite arbeiderklassa. Er biletet eit anna i denne omgangen?

Foto: Dustin Chambers / Reuters / NTB

UtanriksSamfunn

Overkorrigeringa

NEW YORK: Mark Lilla fekk enorm merksemd for sin diagnose av presidentvalet i USA i 2016. Eg oppsøker han for å få oppdaterte psykologiseringar av den amerikanske folkesjela anno 2024.

Ida Lødemel Tvedt
Med jamne mellomrom legg Riksrevisjonen, her representert ved riksrevisor Karl Eirik Schjøtt-Pedersen, fram undersøkingar med nokså hard kritikk av korleis vedteken politikk vert gjennomført av forvaltinga.

Med jamne mellomrom legg Riksrevisjonen, her representert ved riksrevisor Karl Eirik Schjøtt-Pedersen, fram undersøkingar med nokså hard kritikk av korleis vedteken politikk vert gjennomført av forvaltinga.

Foto: Ole Berg-Rusten / NTB

Samfunn
Eva Aalberg Undheim

Eit spørsmål om kontroll

I rapport etter rapport kritiserer Riksrevisjonen statlege institusjonar for feil og manglar. Men kva kjem det eigentleg ut av kritikken?

Odd Nordstoga slo gjennom som soloartist i 2004. No har han skrive sjølvbiografi.

Odd Nordstoga slo gjennom som soloartist i 2004. No har han skrive sjølvbiografi.

Foto: Samlaget

BokMeldingar
ArildBye

Ein av oss

Odd Nordstoga skriv tankefullt om livet, ut frå rolla som folkekjær artist.

Stian Jenssen (t.v.) var alt på plass i Nato då Jens Stoltenberg tok til i jobben som generalsekretær i 2014. Dei neste ti åra skulle dei arbeide tett i lag. Her er dei fotograferte i Kongressen i Washington i januar i år.

Stian Jenssen (t.v.) var alt på plass i Nato då Jens Stoltenberg tok til i jobben som generalsekretær i 2014. Dei neste ti åra skulle dei arbeide tett i lag. Her er dei fotograferte i Kongressen i Washington i januar i år.

Foto: Mandel Ngan / AFP / NTB

IntervjuSamfunn
Christiane Jordheim Larsen

Nato-toppen som sa det han tenkte

Stian Jenssen fekk kritikk då han som stabssjef i Nato skisserte ei fredsløysing der Ukraina gjev opp territorium i byte mot Nato-medlemskap. – På eit tidspunkt må ein ta innover seg situasjonen på bakken, seier han.

Feature

Greske byggjeklossar

Eg dreg til Kreta og lærer om skilnaden på tyske og britiske turistar.

May Linn Clement
Feature

Greske byggjeklossar

Eg dreg til Kreta og lærer om skilnaden på tyske og britiske turistar.

May Linn Clement

les DAG OG TID.
Vil du òg prøve?

Her kan du prøve vekeavisa DAG OG TID gratis i tre veker.
Prøveperioden stoppar av seg sjølv.

Komplett

Papiravisa
Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Digital

Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Komplett

Papiravisa
Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Digital

Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis