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.
Huffmankoding - mest effektiv
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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
http://www.maths.abdn.ac.uk/~igc/tch/mx ... ode59.html
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.jeg skulle gjerne hatt et bevis for at den faktisk lager det kortest mulige koden for en tegnstreng.
Cube - mathematical prethoughts | @MatematikkFakta
Med forbehold om tullete feil. (både her og ellers)
Med forbehold om tullete feil. (både her og ellers)
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.
[tex]L(C,X) = \sum_{i}p_{i}l_{i} \geq H(X) = \sum_{i}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)[/tex]
1. Definer de ubetingede sannsynlighetene
[tex]q_{i}= \frac{2^{-l_{i}}}{z}[/tex], der [tex]z = \sum_{i_{b}}2^{-l_{i_{b}}}[/tex], slik at
[tex]l_{i} = log_{2}\left(\frac{1}{q_{i}}\right)-log_{2}(z)[/tex]
2. Bruk så Gibbs ulikhet som sier
[tex]\sum_{i}p_{i}log_{2}\left(\frac{1}{q_{i}}\right) \geq \sum_{i}{}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)[/tex] med likhet hvis [tex]p_{i} = q_{i}[/tex]
3. Bruk så Kraftulikheten som sier at for enhver unik dekodbar kode [tex]C(X)[/tex] over det binære alfabetet [tex]\left{0,1\right}[/tex] må lengden på kodeordet tilfredsstille
[tex]\sum_{i=1}^{|A_{X}|}2^{-l_{i}} \leq 1[/tex], der [tex]|A_{X}|[/tex] er lengden på symbolalfabetet.
Dette gir at [tex]z \leq 1[/tex]
Da kan en utlede:
[tex]L(C,X) = \sum_{i}p_{i}l_{i} = \sum_{i}p_{i}log_{2}\left(\frac{1}{q_{i}}\right)-log_{2}(z) \geq \sum_{i}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)-log_{2}(z) \geq H(X)[/tex]
Slik at en komprimerer ned til entropien hvis, og bare hvis, Kraftulikheten er oppfylt. Det vil si at [tex]z=1[/tex], noe som gir [tex]q_{i} = 2^{-l_{i}}[/tex], som er en potens av 2.
Huffmanalgoritmen gir optimal koding hvis alle symbolene fra kilden har en sannsynlighet som er en potens av 2.
[tex]L(C,X) = \sum_{i}p_{i}l_{i} \geq H(X) = \sum_{i}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)[/tex]
1. Definer de ubetingede sannsynlighetene
[tex]q_{i}= \frac{2^{-l_{i}}}{z}[/tex], der [tex]z = \sum_{i_{b}}2^{-l_{i_{b}}}[/tex], slik at
[tex]l_{i} = log_{2}\left(\frac{1}{q_{i}}\right)-log_{2}(z)[/tex]
2. Bruk så Gibbs ulikhet som sier
[tex]\sum_{i}p_{i}log_{2}\left(\frac{1}{q_{i}}\right) \geq \sum_{i}{}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)[/tex] med likhet hvis [tex]p_{i} = q_{i}[/tex]
3. Bruk så Kraftulikheten som sier at for enhver unik dekodbar kode [tex]C(X)[/tex] over det binære alfabetet [tex]\left{0,1\right}[/tex] må lengden på kodeordet tilfredsstille
[tex]\sum_{i=1}^{|A_{X}|}2^{-l_{i}} \leq 1[/tex], der [tex]|A_{X}|[/tex] er lengden på symbolalfabetet.
Dette gir at [tex]z \leq 1[/tex]
Da kan en utlede:
[tex]L(C,X) = \sum_{i}p_{i}l_{i} = \sum_{i}p_{i}log_{2}\left(\frac{1}{q_{i}}\right)-log_{2}(z) \geq \sum_{i}p_{i}log_{2}\left(\frac{1}{p_{i}}\right)-log_{2}(z) \geq H(X)[/tex]
Slik at en komprimerer ned til entropien hvis, og bare hvis, Kraftulikheten er oppfylt. Det vil si at [tex]z=1[/tex], noe som gir [tex]q_{i} = 2^{-l_{i}}[/tex], som er en potens av 2.