Huffman-koding

Huffman-koding er en måte å komprimere digital informasjon som ikke medfører tap av informasjon, gjerne brukt i komprimerte bildefiler.

Historie

I 1951 ble David A. Huffman og hans klassekamerater i et kurs om informasjonsteori gitt valget mellom å skrive en semesteroppgave eller å ta avgangseksamen. Oppgaven de kunne velge gikk ut på å finne den mest effektive metoden for å representere tall, bokstaver eller andre symboler ved bruk av binærkode. David Huffman jobbet med oppgaven i flere måneder, og utviklet mange fremgangsmåter, men ingen som han klarte å bevise var den mest effektive.

Det endte med at han ga opp å gjøre oppgaven, og han bestemte seg for heller å begynne å studere til avgangseksamen. Men idet han skulle kaste notatene sine i søpla, kom løsningen til ham. «It was the most singular moment of my life», forteller han. «There was the absolute lightning of sudden realization.» Resultatet var Huffman-kodingen.

Da Huffman gjorde dette, seiret studenten over professoren som hadde jobbet lenge for å finne en lignende kode. Han forteller også at han sannsynligvis aldri ville lagt hans hender på problemet hvis han hadde visst at Robert M. Fano, hans professor, og Claude E. Shannon, skaperen av informasjonsteori, hadde strevd med det i lengre tid.

Hovedteknikk

Hvert symbol, eller piksel i bilde, blir representert med kodeord av ulik lengde, på den måten at de symboler som oppstår oftest har kortest kodeord. Metoden ble utviklet av David A. Huffman, og er basert på Shannon-Fano-algoritmen.

Huffman-algoritmen kan blant annet beskrives slik:

1. Tell opp antall forekomster av hvert symbol
2. Sorter symbolene etter antall forekomster
3. Slå sammen de to symbolene med minst forekomster i en gruppe, og sorter igjen
4. Gjenta punkt 3 til det bare er to grupper igjen
5. Representer denne grupperingen ved hjelp av et binært tre. Hver gren/forgrening blir tildelt 0-bit eller 1-bit
6. Sekvensen av biter fra roten til hver løvnode i treet, gir Huffman-koden.

Regner du informasjonmengde (ved bruk av -ln x/ln2) til alfabetet og runder av til nærmeste bit får du: A=1bit, B=2bit, C=3bit osv

Hvis vi da viser et tenkt eksempel på antall bokstaver som skal sendes:

Antall tegn = A=50 B=23 C=12 D=5 E=5

(1bit x 50) + (2bits x 23) + (3bits x 12) + (4bits x 5) + (5bits x 5) = 162 bits

NB: Man kan ikke bruke informasjonsmengden direkte ettersom man ikke kan sende 3.06 bit i en melding.