Redigerer Huffman-koding (avsnitt)

==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:
# Tell opp antall forekomster av hvert symbol
# Sorter symbolene etter antall forekomster
# Slå sammen de to symbolene med minst forekomster i en gruppe, og sorter igjen
# Gjenta punkt 3 til det bare er to grupper igjen
# Representer denne grupperingen ved hjelp av et binært tre. Hver gren/forgrening blir tildelt 0-bit eller 1-bit
# 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.




<!--

Dette eksempelet er ikke ferdig utarbeidet, derfor skjuler jeg den. Den trenger en illustrasjon av selve treet som viser en representasjon av hvilke biter 


Eksempel:

La oss gi teksten "Wikipedia – Den frie encyklopedi" en representasjon ved hjelp av Huffman-koding.

1. Telle opp forekomster

{| class="wikitable"
|-
! W
! i
! k
! p
! e
! d
! D
! n
! f
! r
! c
! y
! l
! o
|-
| 1
| 5
| 2
| 2
| 5
| 1
| 1
| 2
| 1
| 1
| 1
| 1
| 1
| 1
|}

2. Sorter symbolene

{| class="wikitable"
|-
! i
! e
! k
! p
! n
! W
! d
! D
! f
! r
! c
! y
! l
! o
|-
| 5
| 5
| 2
| 2
| 2
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
|}


 -->
{{Autoritetsdata}}

[[Kategori:Datakompresjonsalgoritmer]]