Huffman-koding

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

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.

Ukategorisert: Denne artikkelen bør kategoriseres i en egnet kategori.