[Base64.sh]

sv v
en fr de es pt it nl ru ja ko zh tw ar hi pl tr sv da no

koda | avkoda | komprimera

> huffman | optimala | koder <

// Huffman-kodning – optimalt prefixfritt komprimeringsalgoritm

0 tecken
0 tecken

>> funktioner

[OPTIMAL]

Optimala koder

Ger den kortast möjliga genomsnittliga kodelängden för de givna frekvenserna.

[PREFIX-FREE]

Prefixfri

Ingen kod är prefix till en annan, vilket ger entydig avkodning.

[ADAPTIVE]

Frekvensbaserad

Vanliga tecken får automatiskt kortare koder.

>> teknisk info

Hur fungerar Huffman-kodning?

Huffman-kodning bygger ett binärt träd nerifrån och upp. Utifrån teckenfrekvenser kombineras upprepade gånger de två noder med lägst frekvens till en föräldranod, tills endast roten återstår. Vänstra grenar representerar '0' och högra '1'. Tecken som förekommer oftare får kortare koder, vilket ger optimal komprimering för den aktuella frekvensfördelningen.

Exempel på Huffman-kodning

Text: "AABBBCCCC"

Frequencies:
A: 2
B: 3
C: 4

Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)

Tree:
     Root(9)
    /      \
   C(4)    AB(5)
          /     \
        A(2)    B(3)

Codes:
C: 0
A: 10
B: 11

Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000

Varför använda Huffman-kodning?

  • Nästan optimal komprimeringsgrad
  • Enkelt att implementera
  • Grund för ZIP/JPEG-komprimering
  • Ingen dataförlust
  • Bevisad effektivitet i praktiken

>> vanliga frågor

Vad är Huffman-kodning?

Huffman-kodning är en optimal, prefixfri komprimeringsalgoritm som utvecklades av David A. Huffman 1952. Den tilldelar tecken koder med variabel längd baserat på hur ofta de förekommer; vanligare tecken får kortare koder, vilket minimerar den genomsnittliga kodelängden.

Varför kallas den prefixfri?

Ett kodesystem är prefixfritt när inget kodord är prefix till ett annat. Om till exempel 'A' har koden '01' får inget annat tecken ha en kod som börjar med '01'. Det gör att bitströmmen kan avkodas entydigt utan extra avskiljare.

Hur effektiv är Huffman-kodning?

Huffman-kodning uppnår optimal komprimering för en given frekvensfördelning och ligger oftast inom 1 bit från den teoretiska entropigränsen. För engelsk text ger den ofta 60–70 % komprimering, särskilt när teckenfrekvenserna skiljer sig mycket åt.

Var används Huffman-kodning?

Huffman-kodning används i JPEG-bildkomprimering, ZIP-filkomprimering (tillsammans med LZ77 i DEFLATE), MP3-ljud och många andra format. Den kombineras ofta med andra algoritmer – JPEG använder exempelvis Huffman efter DCT och kvantisering, medan ZIP använder det efter LZ77.