Huffmankodning
Från Rilpedia
Huffmankodning är en datakomprimeringsalgoritm uppfunnen 1952 av doktoranden David A. Huffman.
I Huffmankodning byts sekvenser av symboler av fix längd entydigt ut mot andra sekvenser av tecken, koder, av olika längd, beroende på symbolens relativa frekvens.
Relativ frekvens kan ses som sannolikheten att en viss symbol ska sändas. Ofta förekommande symboler ges kortare koder än sällan förekommande, så att den totala kodsekvensen blir så kort som möjligt. Det finns två metoder för att uppskatta den relativa frekvensen för symbolerna:
- Symbolernas relativa frekvenser är kända på förhand. Antingen har detta gjorts genom att analysera hela filen som ska kodas, eller så har använder man kunskap man har om källan. T ex kan man kanske anta att bokstaven "e" ska vara ungefär lika vanlig i alla tidningsartiklar på ett visst språk. Metoden kallas statisk huffmankodning.
- Symbolernas sannolikhet uppskattas samtidigt som filen kodas. Kodningstabellen förändras under kodningens gång. Detta kallas adaptiv huffmankodning.
En algoritm för att finna en binär (statisk) Huffmankodning är den följande:
- Ta de två minst frekventa tecknen och tilldela dem en nolla respektive en etta.
- Slå samman de två tecknen och deras frekvenser.
- Börja om från 1 om det finns fler än ett tecken kvar.
Varje huffmankod kan representeras som ett huffmanträd, där symbolerna är lövnoder. Koden är sekvensen av ettor och nollor räknad från den sista tilldelningen.
Exempel
Givet följande tecken och deras respektive frekvenser:
| Tecken | A | B | C |
|---|---|---|---|
| Frekvens | 1 / 2 | 1 / 3 | 1 / 6 |
De två minst frekventa tecknen är B och C. Tilldela B koden 0 och C koden 1. Slå ihop deras frekvenser, B+C: 1 / 3 + 1 / 6 = 1 / 2.
| Tecken | A | B+C |
|---|---|---|
| Frekvens | 1 / 2 | 1 / 2 |
De två minst frekventa tecknen är A och B+C. Tilldela A koden 0 och B+C koden 1 (vilket blir det första tecknet i koderna för B och C).
Koderna blir:
| Tecken | A | B | C |
|---|---|---|---|
| Kod | 0 | 10 | 11 |
Den genomsnittliga kodlängden är
- 1 * 1 / 2 + 2 * 1 / 3 + 2 * 1 / 6 = 1,5
Användningsområden
Huffmankodning är vanlig vid komprimering av data. Populära filformat som ZIP, JPEG och MP3 använder Huffmankodning som en del av komprimeringsprocessen.
