6.4 Huffman-koding

Huffman-koding som grådig algoritme — bygg treet via prioritetskø, og les av kodelengder fra en frekvenstabell (håndkjøring).

45 min

4 oppgaver

Huffman-koding

Din fremgang i kapitlet

0 / 4 oppgaver

Kapitlets plass i kurset

Bygger på

4.4Heap og prioritetskø

Brukes videre i

6.5DRILL — Korteste-vei-matrisen og MST-modellering

Huffman-koding dukker opp i 4 til 5 av 7 sett (rundt 64 %), og den kommer
nesten alltid i én form:

- Sjanger E — håndkjøring, altså at du utfører algoritmen steg for steg og
oppgir sluttilstanden. Du får en frekvenstabell og skal oppgi kodelengden per
symbol, eller det totale antallet bits for en tekst.

Du blir svært sjelden bedt om å skrive Huffman i pseudokode. Du blir bedt om å
bygge treet på papir og lese av tallene — og det er en mekanisk ferdighet du
kan trene deg feilfri på i løpet av en halvtime.

Prioritet: kjenne (nivå 3 av tre — «må sitte» er nivå 1, «kunne» er nivå 2).
Det betyr ikke at temaet er uviktig, men at det gir få poeng per side lest. Til
gjengjeld er de poengene svært lette å ta: én korrekt håndkjøring er typisk 2
poeng, og det er ingen skjønn i vurderingen.

Slik er kapitlet lagt opp (45 min): tre løkker med teori, gjennomkjørt
eksempel og oppgaver.

Forkunnskaper

- kap. 4.4 — min-heapen som prioritetskø. Huffman bygger
treet ved å ta ut de to minste elementene gjentatte ganger, og det er nøyaktig
RemoveMin to ganger.
- kap. 6.3 — begrepet grådig algoritme. Huffman er den
tredje grådige algoritmen i denne delen, etter Prim og Kruskal.
- kap. 4.1 — binære trær, og hva det vil si at en node er et
blad.

Notasjons- og pseudokodeliste

Løkke 1 — hvorfor korte koder til vanlige tegn (ca. 12 min)

Tenk deg at du skal sende en lang tekst over en treg linje, og at du selv får
bestemme hvordan hvert tegn skal kodes som bits.

Den enkle løsningen er å gi alle tegn like lange koder. Har du seks forskjellige
tegn, holder det med 3 bits hver ( $2^3 = 8 \ge 6$ ), og en tekst på 50 tegn koster
150 bits.

Men tegnene er ikke like vanlige. I en norsk tekst er E langt hyppigere enn K.
Gir du E en kode på 1 bit og K en på 5, betaler du mer for de sjeldne tegnene
og mindre for de vanlige — og siden de vanlige forekommer oftest, går regnestykket
i din favør.

Det er hele ideen i Huffman-koding. Og det er også der den vanligste feilen ligger:
kort kode til hyppig symbol, ikke omvendt.

Prefikskode

En koding der ingen kodeord er begynnelsen på et annet kodeord. Det er egenskapen som gjør at en bitstreng kan leses entydig uten skilletegn: når du har lest et gyldig kodeord, vet du at det er ferdig. Har E koden 0 og R koden 01, er koden ikke en prefikskode — og bitstrengen 01 kunne betydd både «R» og «E fulgt av noe som begynner på 1». Et binærtre der alle symbolene ligger i bladene, gir automatisk en prefikskode: ingen vei til et blad er begynnelsen på en annen vei til et blad.

Huffman-tre

Et binærtre der hvert symbol ligger i et blad, og kodeordet leses av veien fra rota: venstre gren er 0, høyre gren er 1 . Treet bygges grådig nedenfra: slå gjentatte ganger sammen de to minste frekvensene til én ny node. Resultatet er en optimal prefikskode — ingen annen prefikskode gir færre bits totalt.

📜Pseudokode-kontrakt: `Huffman`

Antagelser om representasjon. Frekvenstabellen er en liste av par
(symbol, frekvens) med

n

oppføringer. Prioritetskøen PQ er en min-heap
ordnet på frekvens, med RemoveMin og Insert i

O(\log n)

— se
kap. 4.4. En trenode har feltene v.frekvens, v.venstre
og v.hoyre; et blad har i tillegg v.symbol.

Prebetingelse: $n \ge 2$ og alle frekvenser er positive.
Postbetingelse: returverdien er rota i et binærtre der hvert symbol er et blad,
og kodene lest av treet danner en optimal prefikskode.

Procedure Huffman(frekvenser)
  Input:  liste med n par (symbol, frekvens), alle frekvenser > 0
  Output: rota i et Huffman-tre
  PQ = tom min-heap ordnet paa frekvens
  for hvert par (s, f) i frekvenser:
      PQ.Insert(nytt blad med symbol s og frekvens f)
  while PQ inneholder mer enn én node:
      a = PQ.RemoveMin()
      b = PQ.RemoveMin()
      ny = ny node med frekvens a.frekvens + b.frekvens
      ny.venstre = a
      ny.hoyre = b
      PQ.Insert(ny)
  return PQ.RemoveMin()

Grunnideen i én setning: de to sjeldneste symbolene må ligge dypest i treet,
så de kan trygt slås sammen først — og etterpå er det samme problem med ett symbol
mindre.

Kjøretid: $O(n \log n)$ . Tell operasjonene: $n$ Insert i starten à
$O(\log n)$ gir $O(n \log n)$ . while-løkka kjøres $n - 1$ ganger (hver runde
reduserer køens størrelse med én, fra $n$ til 1), og hver runde gjør to
RemoveMin og én Insert, altså $O(\log n)$ . Summen er $O(n \log n)$ .

Å lese av kodene koster en traversering av treet, $O(n)$ , og endrer ikke
orden.

✏️Eksempel 1: Bygg Huffman-treet og les av kodelengdene

Et tekstutdrag på 50 tegn bruker bare seks bokstaver, med disse frekvensene:
$E$ 20, $R$ 12, $S$ 8, $T$ 5, $V$ 3, $K$ 2.

Bygg Huffman-treet, oppgi kodelengden til hvert symbol, og finn hvor mange bits
teksten trenger til sammen.

Steg 1 — sett alle symbolene i prioritetskøen som blad, ordnet på frekvens.

Køen vises som heap-array med indeks fra 0. Etikettene på de sammenslåtte
nodene, som KV og KTV, viser hvilke symboler som ligger under noden — de er
bare navn, ikke en del av algoritmen. Ved lik frekvens tas den alfabetisk minste
etiketten først, slik at sporingen kan gjenskapes nøyaktig.

Steg 2 — slå sammen de to minste, gjentatte ganger:

Steg	To minste tatt ut	Ny node lagt inn	Kø etter (heap-array)
1	(2, K) og (3, V)	(5, KV)	`(5, KV), (5, T), (12, R), (20, E), (8, S)`
2	(5, KV) og (5, T)	(10, KTV)	`(8, S), (10, KTV), (12, R), (20, E)`
3	(8, S) og (10, KTV)	(18, KSTV)	`(12, R), (20, E), (18, KSTV)`
4	(12, R) og (18, KSTV)	(30, KRSTV)	`(20, E), (30, KRSTV)`
5	(20, E) og (30, KRSTV)	(50, EKRSTV)	`(50, EKRSTV)`

Fem sammenslåinger for seks symboler. Kontrollregning:

n - 1 = 6 - 1 = 5

.
Stemmer.
Steg 3 — les av kodene ved å gå ned fra rota: venstre er 0, høyre er 1.
I hver sammenslåing over er den først uttatte noden venstre barn.

Symbol	Frekvens	Kodeord	Kodelengde	Bits (frekvens × lengde)
`E`	20	`0`	1	20
`K`	2	`11100`	5	10
`R`	12	`10`	2	24
`S`	8	`110`	3	24
`T`	5	`1111`	4	20
`V`	3	`11101`	5	15
Sum	50	113

Sluttilstand — dette er svaret du leverer:

E: 1 bit    R: 2 bits   S: 3 bits
T: 4 bits   V: 5 bits   K: 5 bits
Totalt: 113 bits

Sammenligningen som viser poenget. Med fast kodelengde trengs 3 bits per tegn

(seks symboler krever minst 3, siden $2^2 = 4 < 6$ ), altså
$50 \cdot 3 = 150$ bits. Huffman bruker 113. Det er en besparelse på 37 bits,

eller nesten 25 %.
Se på rekkefølgen på kodelengdene: 1, 2, 3, 4, 5, 5 — de følger frekvensene
nøyaktig omvendt. Det er ikke tilfeldig, det er hele algoritmen. Får du en tabell
der et sjeldent symbol har kortere kode enn et hyppig, har du gjort en feil.
Fellenote. Fella her er å bytte om: kort kode til det sjeldneste symbolet.
Kontrollen tar fem sekunder — sorter symbolene etter frekvens og sjekk at
kodelengdene går motsatt vei.

📝Oppgave 1

(Innstegsoppgave, sjanger E — håndkjøring, altså at du utfører algoritmen steg for
steg og oppgir sluttilstanden.) Bruk kodetabellen fra eksempel 1.

a) Hvor mange bits trengs for å kode strengen RESE?
b) Bitstrengen 100110 skal dekodes. Hvilken tekst er det?
c) Hvorfor trenger du ingen skilletegn mellom kodeordene?

Løkke 2 — håndkjøringen, steg for steg (ca. 15 min)

Dette er den delen som gir poeng på eksamen, så den er verdt å gjøre mekanisk.
Oppskriften er fire steg, og den er den samme hver gang.

📜Håndkjøringsoppskriften for Huffman

1. Skriv opp alle frekvensene sortert stigende. Da ser du med én gang hvilke
to som skal slås sammen først.
2. Slå sammen de to minste. Summen blir en ny node, og den settes inn på riktig
plass i den sorterte lista. Gjenta til det er én node igjen.
3. Tell sammenslåingene: det skal være nøyaktig

n - 1

av dem.
4. Les av kodelengden per symbol som antall sammenslåinger symbolet var med i,
altså dybden i treet.

Snarveien for punkt 4: du trenger ofte ikke tegne treet i det hele tatt.
Kodelengden til et symbol er antallet ganger frekvensen dets inngikk i en
sammenslåing. Fulgte $K$ med i sammenslåing 1, 2, 3, 4 og 5, er kodelengden 5.

Totalt antall bits:

$\sum_{s} f(s) \cdot \ell(s)$

Merk at dette tallet er entydig selv når treet ikke er det. Er to frekvenser like,
kan sammenslåingene gjøres i forskjellig rekkefølge, og du kan få forskjellige
kodeord — men den totale bitkostnaden er alltid den samme, og det er den sensor
regner på.

✏️Eksempel 2: Håndkjøring uten å tegne treet

Fem symboler har frekvensene $L$ 12, $O$ 9, $S$ 4, $T$ 3, $U$ 2. Oppgi
kodelengden til hvert symbol og totalt antall bits, uten å tegne treet.

Sortert stigende: 2 (

U

), 3 (

T

), 4 (

S

), 9 (

O

), 12 (

L

Steg	To minste tatt ut	Ny node lagt inn	Kø etter (heap-array)
1	(2, U) og (3, T)	(5, TU)	`(4, S), (5, TU), (9, O), (12, L)`
2	(4, S) og (5, TU)	(9, STU)	`(9, O), (12, L), (9, STU)`
3	(9, O) og (9, STU)	(18, OSTU)	`(12, L), (18, OSTU)`
4	(12, L) og (18, OSTU)	(30, LOSTU)	`(30, LOSTU)`

Kodelengdene, lest som antall sammenslåinger hvert symbol var med i:
-

U

var med i sammenslåing 1, 2, 3 og 4: lengde 4.
-

T

var med i 1, 2, 3 og 4: lengde 4.
-

S

var med i 2, 3 og 4: lengde 3.
-

O

var med i 3 og 4: lengde 2.

- $L$ var med i 4: lengde 1.

Symbol	Frekvens	Kodeord	Kodelengde	Bits (frekvens × lengde)
`L`	12	`0`	1	12
`O`	9	`10`	2	18
`S`	4	`110`	3	12
`T`	3	`1111`	4	12
`U`	2	`1110`	4	8
Sum	30	62

Sluttilstand — dette er svaret du leverer:

L: 1 bit    O: 2 bits   S: 3 bits   T: 4 bits   U: 4 bits
Totalt: 62 bits

Kontrollregningene, begge verdt å gjøre:
1. Antall sammenslåinger: 4, og

n - 1 = 5 - 1 = 4

. Stemmer.

2. Kodelengdene mot frekvensene: frekvensene stiger $2, 3, 4, 9, 12$ , og
lengdene synker $4, 4, 3, 2, 1$ . Motsatt vei hele veien, som de skal.
Sammenligning med fast kodelengde: fem symboler krever 3 bits hver, altså
$30 \cdot 3 = 90$ bits mot Huffmans 62.
Merk hvorfor snarveien virker. Hver gang en node inngår i en sammenslåing,
kommer den ett nivå lenger ned fra rota, og hvert nivå er ett bit. Å telle
sammenslåinger er derfor nøyaktig det samme som å telle dybde i treet — og det er
mye raskere å gjøre riktig under tidspress.

📝Oppgave 2

Sjanger E

Fem symboler har frekvensene $A$ 15, $B$ 7, $C$ 6, $D$ 6, $E$ 5.

a) Kjør Huffmans algoritme og oppgi hvilke noder som slås sammen i hvert steg.
b) Oppgi kodelengden til hvert symbol.
c) Hvor mange bits trengs totalt, og hvor mye sparer du mot fast
kodelengde?

Typiske feil

- Å gi kortest kode til det sjeldneste symbolet. Dette er den klassiske
ombyttingen, og den ødelegger hele svaret. Kontrollen: sorter symbolene etter
frekvens og sjekk at kodelengdene går motsatt vei.
- Å slå sammen andre enn de to minste. Algoritmen er grådig og har ingen
unntak: alltid de to laveste frekvensene i køen, også når den ene er en node du
nettopp laget.
- Å blande kodelengde og kodeord. Spør oppgaven om kodelengden, er svaret et
tall (4). Spør den om kodeordet, er svaret en bitstreng (1110). Les
oppgaveteksten nøye — det er sensors mest gjentatte råd.
- Å regne totalbits feil. Formelen er $\sum_s f(s) \cdot \ell(s)$ — frekvens
ganger lengde, summert. Ikke summen av kodelengdene alene, og ikke summen av
frekvensene.
- Å tro at treet er entydig. Er to frekvenser like, finnes flere gyldige
Huffman-trær. Kodeordene kan variere; totalen kan ikke. Oppgir du en gyldig
tabell med riktig total, er svaret riktig selv om det ikke ser ut som fasiten.
- Å glemme kontrollen $n - 1$ . Med $n$ symboler skal det være nøyaktig $n - 1$
sammenslåinger. Har du flere eller færre, har du mistet eller duplisert en node
underveis.

Og den gjennomgående: å oppgi kjøretiden $O(n)$ . Huffman er $O(n \log n)$ —
logaritmefaktoren kommer fra prioritetskøen, og uten den kunne du ikke funnet de
to minste billig.

Løkke 3 — hvorfor grådighet virker her (ca. 10 min)

Huffman er den tredje grådige algoritmen i Del 6. Prim tar alltid den letteste
kanten ut av treet; Kruskal tar alltid den letteste kanten som ikke lager sykel;
Huffman slår alltid sammen de to minste frekvensene.

Alle tre har det til felles at det lokale valget aldri må gjøres om. Det er ikke
selvsagt — for de fleste optimeringsproblemer er grådighet feil. At det virker
her, er et resultat du skal kjenne til, ikke bevise.

📜Huffman gir en optimal prefikskode

Bør kjenne til. Ingen prefikskode gir færre bits totalt enn den Huffmans algoritme
finner.

Intuisjonen bak, i to setninger. De to sjeldneste symbolene må ligge dypest i
et optimalt tre — ellers kunne du byttet et sjeldent symbol med et hyppigere som
lå dypere, og spart bits. Og siden de er dypest, kan de like gjerne være søsken,
for da er treet over dem det samme problemet med ett symbol færre.

Det du skal kunne på eksamen er påstanden og at algoritmen er grådig — ikke
beviset. Selve beviset er ikke IN2010-pensum.

Merk grensen for hva «optimal» betyr: optimal blant prefikskoder med ett fast
kodeord per symbol. Andre komprimeringsmetoder kan gjøre det bedre ved å utnytte
mønstre over flere tegn — men det er utenfor pensum, og utenfor det Huffman lover.

✏️Eksempel 3: Eksamensnivå — seks statuskoder fra en sensor

En sensor sender en av seks statuskoder hvert minutt. Over en time ble kodene talt
opp slik: $N$ 25, $I$ 14, $G$ 9, $H$ 6, $J$ 4, $Y$ 2.

a) Bygg Huffman-treet og oppgi kodelengden per statuskode.
b) Hvor mange bits trengs for hele timen?
c) Hvor mye spares mot en fast koding, og hva ville skjedd hvis alle seks
kodene forekom like ofte?

a) Sortert stigende: 2 (

Y

), 4 (

J

), 6 (

H

), 9 (

G

), 14 (

I

), 25 (

N

).
Sum: 60 — én kode per minutt i en time. Stemmer.

Steg	To minste tatt ut	Ny node lagt inn	Kø etter (heap-array)
1	(2, Y) og (4, J)	(6, JY)	`(6, H), (6, JY), (14, I), (25, N), (9, G)`
2	(6, H) og (6, JY)	(12, HJY)	`(9, G), (12, HJY), (14, I), (25, N)`
3	(9, G) og (12, HJY)	(21, GHJY)	`(14, I), (25, N), (21, GHJY)`
4	(14, I) og (21, GHJY)	(35, GHIJY)	`(25, N), (35, GHIJY)`
5	(25, N) og (35, GHIJY)	(60, GHIJNY)	`(60, GHIJNY)`

Fem sammenslåinger, og

n - 1 = 6 - 1 = 5

. Stemmer.

Symbol	Frekvens	Kodeord	Kodelengde	Bits (frekvens × lengde)
`G`	9	`110`	3	27
`H`	6	`1110`	4	24
`I`	14	`10`	2	28
`J`	4	`11111`	5	20
`N`	25	`0`	1	25
`Y`	2	`11110`	5	10
Sum	60	134

Kodelengder: $N$ 1, $I$ 2, $G$ 3, $H$ 4, $J$ 5, $Y$ 5.
b) 134 bits for hele timen.
c) Fast koding trenger 3 bits per melding (seks koder krever minst 3, siden

2^2 = 4 < 6

), altså

60 \cdot 3 = 180

bits. Huffman bruker

134, en besparelse på 46 bits,

eller rundt 26 %.
Hadde alle seks kodene forekommet like ofte — 10 hver — ville Huffman gitt
kodelengder på 2, 2, 3, 3, 3, 3 (treet den bygger på seks like frekvenser), og
totalt $10 \cdot (2 + 2 + 3 + 3 + 3 + 3) = 160$ bits mot fast kodings 180. En liten
gevinst, men langt mindre enn de 46 bitene her.
Momentet, og det som gir det siste poenget: Huffman tjener på skjevhet.
Jo skjevere frekvensfordelingen er, jo mer sparer du. Er alle symbolene like
vanlige, er det nesten ingenting å hente — og det er verdt å si i en besvarelse,
fordi det viser at du forstår hva algoritmen faktisk utnytter.

Kjøretid: $O(n \log n)$ , der $n = 6$ er antall forskjellige statuskoder — ikke

antall meldinger. Å blande de to er en fast forveksling: alfabetets størrelse er

det som styrer kostnaden ved å bygge treet.

📝Oppgave 3

Sjanger C

Marker sant eller usant, og begrunn hvert svar med én setning.

a) I et Huffman-tre har det hyppigste symbolet alltid den korteste koden.
b) Huffman-treet er entydig bestemt av frekvenstabellen.
c) Huffmans kjøretid er $O(n \log n)$ , der $n$ er antall forskjellige symboler.
d) En Huffman-kode er alltid en prefikskode.
e) Huffman lønner seg mest når alle symbolene forekommer like ofte.

📝Oppgave 4

Sjanger E, krevende

En melding består av sju symboler med frekvensene 1, 1, 2,
3, 5, 8, 13.

a) Hvor mange sammenslåinger gjør algoritmen?
b) Bygg treet og oppgi kodelengden til hvert symbol.
c) Hva er totalt antall bits, og hva blir gevinsten mot fast kodelengde?
d) Hva er spesielt med denne frekvensfordelingen, og hva gjør den med treets
form?

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Huffmans algoritme

O(n \log n)

Kodelengde per symbol

Dybden til symbolets blad i Huffman-treet, altså antall bits i kodeordet. Snarveien i håndkjøring: kodelengden er antall sammenslåinger symbolet var med i. Du trenger ikke tegne treet for å svare på eksamen.

Totalt antall bits

\sum_{s} f(s) \cdot \ell(s)

Antall sammenslåinger

n

Huffman-treet er ikke alltid entydig

Er to frekvenser like, kan sammenslåingene gjøres i forskjellig rekkefølge, og kodeordene kan bli forskjellige. Kodelengdene og den totale bitkostnaden er derimot alltid de samme. Leverer du en gyldig tabell med riktig total, er svaret riktig selv om det ikke ligner fasiten.

Når lønner Huffman seg?

Når frekvensfordelingen er skjev . Jo mer noen symboler dominerer, jo mer sparer du mot en fast koding. Er alle symbolene like vanlige, blir kodelengdene nesten like, og gevinsten er liten. Det er ofte det siste delpoenget i en oppgave: å si hva algoritmen faktisk utnytter.

Fast kodelengde som referanse

n

Grådig algoritme i Del 6

Prim, Kruskal og Huffman er alle grådige: de tar det beste lokale valget i hvert steg og angrer aldri. For alle tre er grådighet beviselig optimalt. Det er ikke selvsagt — for de fleste optimeringsproblemer er grådighet feil — og at det virker her, er et resultat du skal kjenne, ikke bevise.

Huffmans høyde i verste tilfelle

n

Dekoding av en Huffman-kode

O(\text{antall bits})

Prefikskode

En koding der ingen kodeord er begynnelsen på et annet. Det gjør bitstrengen entydig lesbar uten skilletegn. Et binærtre med alle symbolene i bladene gir automatisk en prefikskode. Ligger et symbol i en intern node, brytes egenskapen, og koden blir tvetydig.

Hva

n

er i Huffmans kjøretid

n

Repetisjon — kapitlet på ett kort

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.