Huffman Algorithmus speicherung

Jack

Jack

Mitglied
Hallo erstmal,

ich möchte mit Java (zu übungszwecken) eine eigene Klasse schreiben die textdateien mithilfe des Huffman Algorithmus komprimiert und dann in eine Datei abspeichert! Den Algorithmus selber hab ich soweit auch schon begriffen! Ich habe bislang nur keine ahnung wie ich den Huffman Tree in die Datei abspeichere.
 
such mal nach pre-oder bzw. in-order - da hat einer die Rekonstruktion eines Binärbaumes als Problem gehabt. Mit diesen beiden angaben geht es.

Aber es müsste auch besser gehen. Der Code ergibt sich ja einfach aus dem Weg von der Wurzel zum Blatt. Die Werte sind nur in den Blättern gespeichert.
 
vielleicht geht auch die Speicherung in einem Array:

1tes Element: Wurzel
2,3tes Element: Kinder der wurzel

die Kinder eines Knotens an Position n findet man dann an Position 2n und 2n+1 (hier aufpassen, die Nummerierung beginnt mit 1 nicht mit 0 wie beim array).

Damit läßt sich ein vollständiger binärer Baum recht einfach Speichern. Für einen Knoten speicher dann einfach binär 00 für ein Blatt den Wert des Blattes. Den Huffman-Baum muss man natürlich dann künstlich vervollständigen und beim laden wieder kürzen.
 
ja ich bin auch der Meinung dass es mit einem "Array Baum" geht man kann ja einem Array-Element nochmals einen Array unterordnen! Aber in java selber gibt es ja auch, zwar für XML aber man kann das ja auch misbrauchen ein TreeSet mit dem man virtuelle bäume basteln kann.

Ich hab aber mit speicherung nicht die zwischenspeicerung und abbildung des Baumes im Arbeitsspeicher gemeint sondern eher die entgültige Speicherung in der Datei als binärcode!

Ich weis nicht genau wie ich mit bits diesen Baum abbilden soll besser gesagt wie man die binärdatei strukturiert. Klar ist dass die Binärdatei zuerst mal den Baum speichern muss und dann den mithilfe des baumes codierten eigentlichen inhalte. Die frge ist also wei man den Baum im Arbeitsspeicher mithilfe von birnärdaten in eine Datei überträgt!
 
Also - einmal von anfang an.

Du hast einen recht simplen binärbaum - der besteht nur aus Blättern und Knoten. Jeder Knoten/jeds Blatt kennt seinen Vater und weiss ob er linker oder rechter Sohn ist. Jedes Blatt enthält zusätzlich welches Zeichen es repräsentiert. Willst du nun wissen wie ein bestimmtes Zeichen repräsentiert wird, gehtst du vom Blatt zur Wurzel und für jeden Knoten den du betrittst speicherst du woher du kommst - dabei ist es eine 0 wenn du aus einem linken Sohn kommst bzw. eine 1 wenn du aus einem rechten Sohn kommst. Wenn du diese Folge aus 0llen und 1en nun umdrehst, hast du eine Anweisung wie du im Baum von der Wurzel zum Blatt kommst indem du wenn du eine 0 hast nach links, bei einer 1 nach rechts abzweigst. Diese Folge wird nun gespeichert. Dazu musst du sie in 8bit lange Teilstücke aufteilen bzw. aufkumulieren und als einzelen Bytes speichern. Beim laden gehst du umgekehrt vor. Einfach ein Byte laden, die Bits einzeln durchgehen und immer wenn du auf ein Blatt stößt das Zeichen im Blatt ausgeben, wenn das Byte zuende ist einfach ein neues laden.
Nun zum Baum. Da der Binärcode in den Abzweigungen gespeichert ist, reicht es wenn du die Struktur wieder herstellen kannst und brauchst nicht zu speichern wie jedes einzelne Zeichen codiert ist.
Angenommen wir wollen 1 byte große Zeichen Huffman codieren, dann können die Blätter alle Werte zwischen 0 und 255 annehmen. Das Verfahren das ich jetzt hier vorschlage ist nicht besonders effektiv, aber sollte einfach zu verstehen/implementieren sein. Jedem Knoten im Baum wird eine Integerzahl zugewiesen. Alle inneren Knoten bekommen eine Negative zahl, alle Blätter den Wert den sie repräsentieren (0-255). Nun wandelt man den Baum in 2 Zahlenfolgen um, die eine ist die LWR-Order der Knotennummern, die andere die WLR-Order der Knotennummern. Nun kann man das ganze recht einfach speichern:

Ersten 2 Byte: Anzahl der Zahlen in der LWR-Order.
Bytes 3-x1 LWR-Order des Baumes
x1-x2 WLR-Order des Baumes
ab x2+1: Bitstream der Datei

Damit bekommt man zuerst den Baum aus der Datei und kann dann einfach den Bitstream dekodieren.

Definition LWR-Order:
Wie üblich - Rekursiv:
LWR(Knoten x)=LWR(linker Sohn)xLWR(rechter Sohn)

Definition WLR-Order:
WLR(Knoten x)=xWLR(linker Sohn)WLR(rechter Sohn)

ist ein Sohn nicht vorhanden, so liefert die Funktion nichts zurück.

siehe dazu auch:
http://www.tutorials.de/tutorials159110.html

Alle Klarheiten beseitigt?
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück