Huffmann-Codierung
1. Prinzip
Eingangssymbole mit einer höheren Häufigkeit werden mit einem kurzen Ausgangssymbol versehen.
Seltene Eingangssymbole werden mit einem längeren Ausgangssymbol versehen.
rel. Häufigkeit | Code | Codelänge | |
---|---|---|---|
6/10 | 0 | 1 | |
2/10 | 11 | 2 | |
1/10 | 101 | 3 | |
1/10 | 100 | 3 |
Beispiel
http://www.youtube.com/watch?v=6lUKgFr5-oQ
Adaptive Huffmann-Kodierung
http://www.ziegenbalg.ph-karlsruhe.de/materialien-homepage-jzbg/cc-interaktiv/huffman/codierung.htm
2. Implementierungen
Huffman Encoder/Decoder
http://sourceforge.net/projects/huffman/
Interface
int huffman_encode_memory(const unsigned char *bufin,
uint32_t bufinlen,
unsigned char **pbufout,
uint32_t *pbufoutlen);
int huffman_decode_memory(const unsigned char *bufin,
uint32_t bufinlen,
unsigned char **bufout,
uint32_t *pbufoutlen);
uint32_t bufinlen,
unsigned char **pbufout,
uint32_t *pbufoutlen);
int huffman_decode_memory(const unsigned char *bufin,
uint32_t bufinlen,
unsigned char **bufout,
uint32_t *pbufoutlen);
3. Häufigkeitsanalyse
clear
clc
s = [];
for k=1:100
s = [s 0xA0 0x01 randi(2).'-1 0xE0];
s = [s 0xA0 0x02 randi(2).'-1 0x00 randi(256).'-1 randi(256).'-1 randi(256).'-1 0xE0];
end
a = unique(s).'; % Alphabet
for k=1:length(a)
c(k) = sum(s==a(k));
end
p = c/sum(c);
ps=sort(p);
tres=min(ps(end-10:end));
sel = p>tres;
dec2hex(a(sel))
p(sel).'
clc
s = [];
for k=1:100
s = [s 0xA0 0x01 randi(2).'-1 0xE0];
s = [s 0xA0 0x02 randi(2).'-1 0x00 randi(256).'-1 randi(256).'-1 randi(256).'-1 0xE0];
end
a = unique(s).'; % Alphabet
for k=1:length(a)
c(k) = sum(s==a(k));
end
p = c/sum(c);
ps=sort(p);
tres=min(ps(end-10:end));
sel = p>tres;
dec2hex(a(sel))
p(sel).'
Siehe auch