Huffmann-Kompression

Hallo,
ich habe mir heute mal die Huffmann-Kompression angesehen.
Die Kompression habe ich bereits verstanden, aber wie wird die Zeichenkette wieder dekomprimiert?
Zum einen weiß ich nicht, wie man an den Baum kommen soll, und zum anderen verstehe ich nicht, wie man dann die 0-1-Kette durchgehen soll (einfach von vorne nach hinten?).
Vielleicht mag mir ja jemand was erklären

CStoll

Den Baum mußt du natürlich gesondert speichern, damit du ihn wieder zurückgewinnen kannst. Im Wikipedia-Artikel zum Thema wird sogar ein Beispiel angegeben, wie man das machen kann.
Zum Dekodieren baust du dir den Baum wieder auf und folgst dann bitweise den Ästen. Wenn du bei der Wurzel ankommst, gibst du den entsprechenden Buchstaben aus und kehrst zur Wurzel zurück.

pos=wurzel
while !eof()
  if getbit()==0
    pos=pos.left
  else
    pos=pos.right
  if istblatt(pos)
    print pos.wert
    pos=wurzel

icarus2

Den Baum musst du selber konstruieren. Die Konstruktion ist in Prinzip ganz eifach. Hier... findest du den Algorithmus für die Erstellung eines Huffman-Baums.

Sagen wir du hast 010100...
Du beginnst dann immer bei der Wurzel. Wenn du eine 0 hast, gehtst du nach links, bei einer 1 nach rechts, bis du bei einem Blatt ankommst, indem ein Buchstabe gespeichert ist. Wenn du den Buchstaben gefunden hast machst du weiter, indem du wieder bei der Wurzel beginnst und weiter den zu decodierenden String durchläufst.

hustbaer

CStoll schrieb:

...

Genau.

Und wenn man fertig ist, muss man auf der Wurzel stehen, sonst sind die Input-Daten fehlerhaft:

pos=wurzel
while !eof()
  if getbit()==0
    pos=pos.left
  else
    pos=pos.right
  if istblatt(pos)
    print pos.wert
    pos=wurzel

if pos!=wurzel
  FEHLEEER()

Ok, das Dekodieren hab ich verstanden, danke

Nur noch nicht das erzeugen des Baums aus einer Datei. Angenommen ich benutze die von Wikipedia genannte Methode, wie kriege ich aus "\x01A\x00\x04BCDE" dann den Baum?

icarus2

Du zählst die absoluten Vorkomnisse eines einzelnen Zeichens in dem String. Für jedes Zeichen, das in dem String vorkommt machst du dann einen Knoten und merkst dir die absolute Häufigkeit.
Mit diesem Wissen kannst du dann den Baum konstruieren.

CStoll

Wurst mit Ketchup schrieb:

Ok, das Dekodieren hab ich verstanden, danke

Nur noch nicht das erzeugen des Baums aus einer Datei. Angenommen ich benutze die von Wikipedia genannte Methode, wie kriege ich aus "\x01A\x00\x04BCDE" dann den Baum?

Du hast die Verteilung der Knoten auf die einzelnen Baum-Ebenen, den Rest mußt du mit inneren Knoten auffüllen:

0

1  A

2

3    B   C   D   E

-->

0     _*_
   0_-   -_1
1  A      _*_
       0_-   -_1
2      *       *
     0/ \1   0/ \1
3    B   C   D   E

(die Entscheidung, wo du 0 und 1 an die Äste schreibst, ist einfach eine Definitionsfrage und ändert nichts an der Kompressionsrate)

Ich glaube, auch das hab ich jetzt verstanden,
Danke für die Hilfe.