Huffmankoding - mest effektiv

[EScII]

Jeg holder på med et prosjekt om Huffmanalgoritmen og jeg skulle gjerne hatt et bevis for at den faktisk lager det kortest mulige koden for en tegnstreng.

Takker for alle svar.

[FredrikM]

Jeg har ikke lest dette, men den er resultatet etter et raskt søk på Google.

http://www.maths.abdn.ac.uk/~igc/tch/mx ... ode59.html

jeg skulle gjerne hatt et bevis for at den faktisk lager det kortest mulige koden for en tegnstreng.

Dette er ikke nødvendigvis tilfellet. Huffman-koding er optimal om vi baserer kodingen vår på et binært tre. Det fins flere andre komprimeringsmetoder som i noen tilfeller kan komprimere bedre enn Huffmann-koding.

[EScII]

Men så lenge hvert tegn skal ha hver sin kode, blir vel kodingen optimal ved bruk av Huffmanalgoritmen?

[EScII]

Mulig jeg tenker feil.

[drgz]

Vet ikke om det er dette du er på utkikk etter, men jeg gir det et forsøk, så får du heller si i fra hvis det er noe annet.

Huffmanalgoritmen gir optimal koding hvis alle symbolene fra kilden har en sannsynlighet som er en potens av 2.

$L(C,X)=\sum _i{p}_i{l}_i\ge H(X)=\sum _i{p}_{i}lo{g}_2\left(\frac{1}{p_i}\right)$

1. Definer de ubetingede sannsynlighetene
$q_i=\frac{2^{-l_i}}{z}$, der $z=\sum _{i_b}{2}^{-l_{i_b}}$, slik at
$l_i=lo{g}_2\left(\frac{1}{q_i}\right)-lo{g}_2(z)$

2. Bruk så Gibbs ulikhet som sier
$\sum _i{p}_{i}lo{g}_2\left(\frac{1}{q_i}\right)\ge \sum _i{p}_{i}lo{g}_2\left(\frac{1}{p_i}\right)$ med likhet hvis $p_i=q_i$

3. Bruk så Kraftulikheten som sier at for enhver unik dekodbar kode $C(X)$ over det binære alfabetet $\text{Missing or unrecognized delimiter for left}$ må lengden på kodeordet tilfredsstille

$\sum _{i=1}^{|A_X|}{2}^{-l_i}\le 1$, der $|A_X|$ er lengden på symbolalfabetet.

Dette gir at $z\le 1$

Da kan en utlede:

$L(C,X)=\sum _i{p}_i{l}_i=\sum _i{p}_{i}lo{g}_2\left(\frac{1}{q_i}\right)-lo{g}_2(z)\ge \sum _i{p}_{i}lo{g}_2\left(\frac{1}{p_i}\right)-lo{g}_2(z)\ge H(X)$

Slik at en komprimerer ned til entropien hvis, og bare hvis, Kraftulikheten er oppfylt. Det vil si at $z=1$, noe som gir $q_i=2^{-l_i}$, som er en potens av 2.