Huffman Kompression

Michael E.

Tatsächlich. Ich zitier mich mal selbst aus nem anderen Thread:

Ups. Nenns Sonntagsunkonzentriertheit :p

rapso

beispiel für 4bit

root
                   /\
                  /\ 1
                 /\ 2
                /\ 4
               /\ 8
              /\ 16
             /\ 32
            /\ 64
           /\ 128
          /\ 256
         /\ 512
        /\ 1024
       /\ 2048
      /\ 4096
     /\ 8192
32768  16384

wie du sehen kannst, kommt für 4bit als worstcase (für das octed das 32768 mal vorkommt) 15bit als codelenge raus.

wenn ihr den baum schöner gezeichnet haben wollt, zeichnet selber

rapso->greets();

Michael E.

rapso: Wieso nicht so?

root
          /    \
         0      1
        / \    / \
       0   1  0   1
           usw.

Es werden doch immer die beiden kleinsten Wahrscheinlichkeiten in einem Knoten vereint.

rapso

Michael E. schrieb:

rapso: Wieso nicht so?

weil

Michael E. schrieb:

Es werden doch immer die beiden kleinsten Wahrscheinlichkeiten in einem Knoten vereint.

nimm dir einfach mal die werte aus meinem beispiel und bau daraus einen baum auf, bin 'gespannt' wie er aussehen wird.

rapso->greets();
btw. hier nochmal die werte:

1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768

Michael E.

Hmm, du hast Recht

Ich bin, ohne es zu merken, von gleich großen Wahrscheinlichkeiten ausgegangen.

Michael E.

Ankerkung: Ist dein Baum nicht falsch herum aufgebaut?

rapso

aber wie man an dem beispiel wunderbar sehen kann, muss man sich weder die codes noch die häfigkeit der einzelnen zeichen speichern um den baum erstellen zu können, es reich der exponent.

also von
1<<a, das a abspeichern.
so kann man den baum erstellen bzw rekonstruieren und natürlich kann a nicht größer werden als die 'eingangscodes' zum speicher einer table für 8bit werde würden also 256 bytes reichen

rapso->greets();

Michael E.

rapso schrieb:

aber wie man an dem beispiel wunderbar sehen kann, muss man sich weder die codes noch die häfigkeit der einzelnen zeichen speichern um den baum erstellen zu können, es reich der exponent.

also von
1<<a, das a abspeichern.

Ich kann dir nicht ganz folgen. Ist wohl nicht mein Tag heute
Was machst du mit Zahlen, die nicht Potenzen von 2 sind?

rapso

hab ich auch ein wenig unklar ausgedrückt.

du erstellst aus den bäumen die potenzen
wenn also für das byte 243 der bitcode 12bit hat, dann speichert man sich 12 anstatt dem bitcode oder der häufigkeit des vorkommens.

das braucht dann natürlich beim packen mehr phasen
-erst erstellt man den hufftree
-anhand der bitcodes erstellt man nun die zu speichernden shift-werte
-anhand der (1<<shiftwert) erstellt man einen neuen tree der genau so ausschaut wie beim entpacken aber anders als der erste tree.

ich kann c++ besser als deutsch fällt mir gerade auf.

rapso->greets();

Michael E.

Schreib das ganze doch mal bitte in Pseudo-C++ :p Ich bin immer noch nicht ganz schlau draus geworden. Deine Vorgehensweise würde doch IMHO scheitern, wenn zwei oder mehr Buchstaben die selbe Bitcodelänge hat...