Huffmankodning

Innehåll- 1. Mer teknisk beskrivning

Huffmankodningär en ickeförstörande kompressionsalgoritm baserad på statistisk analys av tecknena i datan som ska komprimeras. När sannolikheten för tecknena är kända skapas ett så kallat huffmanträd där vanligt förekommande tecken hamnar nära trädets rot och ovanliga tecken hamnar långt ut i trädet. Koden för ett visst tecken blir sedan "vägbeskrivningen" från trädets rot till lövet för tecknet i fråga, vänster ger en nolla och höger ger en etta. Huffmankodningen skapades av David A. Huffman.

1. Mer teknisk beskrivning

Exempel: Vi vill komprimera strängen "AAABBAC".

1. Skapa en frekvenstabell för tecknenaA: 4B: 2C: 1

2. Skapa en nod för varje tecken tillsammans med dess sannolikhet

|A:4| |B:2| |C:1|

3. Slå ihop noder

• välj de två noder som har lägst sannolikhet.
• skapa en ny nod med summan av de två nodernas sannolikheter och med de två noderna som barn.
• upprepa tills det bara finns en toppnod

B och C har lägst sannolikhet|:3| |A:4| / |B:2||C:1|

Bara två toppnoder kvar, slå ihop dom |:7|/ |:3||A:4| / |B:2||C:1|

4. Skapa bitsträngarna för varje tecken genom att traversera trädetEn nolla för vänster och en etta för högerA: 1B: 00C: 01

5. Skriv ut bitsträngen för varje tecken i datan som ska komprimeras

AAABBAC 1 1 1 00 00 1 01 Vi fick alltså totalt 10 bitar

Vi fick en kompression på ungefär 1,42 bits per byte, eller 82 procent. Detta förutsatt att vi använder åtta bitar för att representera ett tecken.

Redigera?

Artikeln skriven 2009-01-17 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Tre amigos
Ivar Jacobson
Rational Quantify
Stendhals syndrom
Ullervad
Hällevadsholm
Gördelmaskar
Iglar
Arhynchobdellida