verständnisproblem huffman codierung
-
hallo
1. angenommen, in der quellnachricht kommen symbole von 0 bis 255 vor, die alle eine zum wert negativ-proportionale auftrittswahrscheinlichkeit haben (0 sehr oft z.b.). stimmt es, dass dann das symbol 255 in der quellnachricht 8 bits hatte und in der huffman-codierten nachricht 256 bits?
2. angenommen wir haben eine datei, in welcher die auftrittswahrscheinlichkeiten der symbole mehr oder weniger gleichverteilt sind. stimmt es, dass dann die huffman-codierte ausgabe wesentlich länger ist als die eingabe?
gruss
-
asfdlol schrieb:
1. angenommen, in der quellnachricht kommen symbole von 0 bis 255 vor, die alle eine zum wert negativ-proportionale auftrittswahrscheinlichkeit haben
Was ist "negativ-proportional"? Und zu was ist die Wahrscheinlichkeit "negativ-proportional"? Meinst du P(i) für i=0..255 ist proportional zu 2^(-i)?
asfdlol schrieb:
(0 sehr oft z.b.). stimmt es, dass dann das symbol 255 in der quellnachricht 8 bits hatte und in der huffman-codierten nachricht 256 bits?
Im schlimmsten Fall wären das 255 Bits. Kommt aber echt drauf an, wie die Wahrscheinlichkeitsverteilung aussieht und wie Deine Implementierung des Huffman-algorithmus ein "Unentschieden" auflöst; denn manchmal gibt es ja auch drei oder mehr Wurzeln mit derselben minimalen Wahrscheinlichkeit. In den Fällen könnte man die zwei Wurzeln zu einem neuen Baum bauen, die zu den flachsten Bäumen gehört haben. Wenn du die maximale Länge der Codeworte beschränken willst, gibt es aber auch einen schönen Algorithmus dafür.
asfdlol schrieb:
2. angenommen wir haben eine datei, in welcher die auftrittswahrscheinlichkeiten der symbole mehr oder weniger gleichverteilt sind. stimmt es, dass dann die huffman-codierte ausgabe wesentlich länger ist als die eingabe?
Wenn die Symbole mehr oder weniger gleichverteil sind, ist der Gewinn der Huffmankodierung klein oder sogar 0. Es lohnt sich dann nicht wirklich. Ob die Ausgabe "wesentlich länger" wird, hängt dann davon ab, wieviel Overhead der Code-Baum gegenüber den Nutzdaten in der Ausgabedatei macht. Du könntest es aber so machen, wie die meisten Kompressionsformate: Sie speichern ein Flag oder eine kurze Kennung, die sagt, welcher Algorithmus verwendet wurde. Und wenn sich alles nicht lohnt, dann verwendet man einfach den "Kompressionsalgorithmus", der nichts macht und die daten 1:1 speichert.
-
asfdlol schrieb:
hallo
1. angenommen, in der quellnachricht kommen symbole von 0 bis 255 vor, die alle eine zum wert negativ-proportionale auftrittswahrscheinlichkeit haben (0 sehr oft z.b.). stimmt es, dass dann das symbol 255 in der quellnachricht 8 bits hatte und in der huffman-codierten nachricht 256 bits?
2. angenommen wir haben eine datei, in welcher die auftrittswahrscheinlichkeiten der symbole mehr oder weniger gleichverteilt sind. stimmt es, dass dann die huffman-codierte ausgabe wesentlich länger ist als die eingabe?
gruss
- Kommt aufs "negativ-proportional" an. Es muss schon arg negativ sein.
1b)
p(0)=1/2 //Zeichenlänge 1
p(1)=1/4 //Zeichenlänge 2
p(2)=1/8 //Zeichenlänge 3
...
p(255)=0.5^256 //Zeichenlänge 256
Da stimmt's offensichtlich.1a)
0 kommt 256-mal vor
1 kommt 255-mal vor
2 kommt 254-mal vor
...
255 kommt 1-mal vor
Gesamtttextlänge=32896
Hmm, würde schätzen, daß der Baum nicht so einseitig wird und die 255 eher so 16 oder 17 bits kriegt.Nö, wäre mir neu.
-
volkard schrieb:
1b)
p(0)=1/2 //Zeichenlänge 1
p(1)=1/4 //Zeichenlänge 2
p(2)=1/8 //Zeichenlänge 3
...
p(255)=0.5^256 //Zeichenlänge 256
Da stimmt's offensichtlich.Nicht ganz. Der Baum wäre unvollständig. Huffman führt zu einem "vollständingen Baum" in dem Sinne, dass ein Knoten entweder ein Blatt oder ein innerer Knoten mit zwei Kindern ist. Die Anzahl der längsten Codeworte ist bei Huffman also immer gerade. In diesem Fall hättest du zwei Codeworte mit einer Länge von jeweils 255 Bits.
Beispiel für ein kleineres Alphabet:
* / \ <- 1. Bit 0 * / \ <- 2. Bit 1 * / \ <- 3. Bit 2 3
-
-
mit negativ-proportional meinte ich reziprok-proportional. danke für den link, da hab ich offenbar noch einiges zu lernen...
also 255 bits wenn man das nicht speziell optimiert und wenn die auftrittswahrscheinlichkeit der zeichen wirklich so strikt ist wie in meinem hypothetischen beispiel. -
oh ja wie dumm von mir, bei einer gleichverteilung ist der baum natürlich nicht einseitig...
-
-
asfdlol schrieb:
also 255 bits wenn man das nicht speziell optimiert
Da gibt es nichts zu optimieren, 255 ist gut, das Zeichen tritt ja nur alle 2^256 Zeichen mal auf. Das ist *sehr* selten. Bei einer Millarde Zeichen pro Sekunde kannste ca alle 10^64 Jahre mal eins erwarten.