Huffman Kompression

Spacelord

FrEAkout schrieb:

255Bit??

Das kann ich mir nicht vorstellen..

Also nach meinem Verständnis wäre doch der worst case bei huffman wen alle Zeichen des ascii zeichensatzes (0-255) 1 mal in der datei vorkommen. Ich kann mir vorstellen das die Längen der Codewörter lang werden aber nicht 255bit lang..

Naja im worst Case entartet doch der Baum zu ner Liste mit einer "Tiefe" von 255(bei 8Bit).Das letzte Zeichen,dass ja in diesem Fall jedes sein kann,würde also durch eine 255 Bit lange Folge dargestellt.

MfG Spacelord

Michael E.

log_2(Anzahl der Zeichen)

[EDIT] Tschuldigung, hab grad Huffman mit Shannon-Fano verwechselt, weil ich beide erst mit dem Link kennen gelernt hab.

rapso

Spacelord schrieb:

FrEAkout schrieb:

255Bit??

Das kann ich mir nicht vorstellen..

Also nach meinem Verständnis wäre doch der worst case bei huffman wen alle Zeichen des ascii zeichensatzes (0-255) 1 mal in der datei vorkommen. Ich kann mir vorstellen das die Längen der Codewörter lang werden aber nicht 255bit lang..

Naja im worst Case entartet doch der Baum zu ner Liste mit einer "Tiefe" von 255(bei 8Bit).Das letzte Zeichen,dass ja in diesem Fall jedes sein kann,würde also durch eine 255 Bit lange Folge dargestellt.

MfG Spacelord

worst-case tritt auf wenn:

for( a = 0 to 255 )
  counterliste[a]=1<<a;

natürlich müßte in dem fall die zu packende datei extrem gross sein, nämlich (1<<256) bytes.

rapso->greets();

Aber dieser worst case kann beim ascii zeichensatz doch gar nicht auftreten weil der baum keine tiefe von 255 bekommt bei 255 zeichen.. da sich die zeichen ja auf links und rechts verteilen!

also ist das mit dem log gar nicht so falsch... wenn nicht sogar richtig

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...