Huffman-encoding - header & EOF
Derzeit arbeite ich an der Umsetzung eines Programms basiert auf der huffman-Algorithmus in Java, und ich bin in der Phase, wo ich brauche, um die Ausgabe der codierten Inhalt in eine Datei. Ich bin ein bisschen verwirrt darüber, wie zu implementieren, die header und eof benötigt für die Decodierung. Für meinen header im moment habe ich alle eindeutigen Werte auftreten, die aus der Eingabedatei und Ihre Häufigkeit, aber auf einige Artikel, die ich gesehen habe Menschen tun es mit 0 oder 1 repräsentiert den Knoten, und dann die Frequenz (die ich bin ein bisschen verwirrt, da Sie nicht sagen, was das symbol ist).
Auch, für die EOF-wie ich es verstehe, die ich verschlüsseln, wie die Symbole, so wird es gelesen und decodiert, aber ich bin mir nicht sicher welchen Wert ich verwenden können, für Sie, die definitiv nicht kommen? Ich weiß, es muss ein Gewicht von 1 war aber unsicher, wie Sie sicherstellen, dass Sie nicht tatsächlich in der Datei.
- Welche Artikel? Könnten Sie ein paar links?
- Die wichtigsten beiden, die ich suchte, waren michael.dipperstein.com/huffman und cs.duke.edu/csed/poop/huff/info zu denken, nachdem die header kann ich sehen, warum Sie es tun nun, ich denke (konstruieren einen Baum mit dem Kopf, dann bekommen Sie Frequenzen, die durch Lesen der Inhalte der Datei? Im moment hat mir die Symbole und Frequenzen im header ist falsch) Es ist nur die pseudo-eof-code bin ich verwirrt, wie ich bin mir nicht sicher, was zu verwenden, wie es für nicht möglich, den code könnte ein symbol schon in den Baum?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich habe einmal für eine Aufgabe und das ist der Ansatz, den wir verwendet.
Kodierung der header wurde getan, indem man mit 0 und 1 zu Kodieren die Struktur des Baumes (anstatt der Frequenzen). Eine "0" gekennzeichnet Umzug auf dem Baum, wird eine "1" gekennzeichnet waren wir an einem Blattknoten. Dies führte in eine Art pre-order-Traversierung des Baumes Kodierung, die es eindeutig.
Beispielsweise eine Struktur wie (((a b) c) d e)) würde codiert werden als "0001
a1b1c01d1e", wo a,b,c,d,e sind der ASCII-Formen.Hier ist der Baum in einer grafischen form:
Für die EOF-nutzten wir die letzten 3 bits in der Datei, um anzugeben, wie viele die letzten zwei bytes benötigt, um gelesen werden. Einmal Lesen wir das Letzte byte (also wir arbeiteten auf dem vorletzten byte) checkten wir die letzten 3 bits: Sie codiert, wie viele weitere bits zu Lesen, minus 6. So
110101xxxxxxx000gemeint "Lesen110101(6 bits) und verwerfen alles andere".1101011xxxxxx001gemeint "Lesen1101011(7 bits) und verwerfen Sie den rest", etc.Doing es auf diese Weise gemeint, dass wir nicht haben einen besonderen Wert für die EOF und wir konnten noch Lesen die Datei ein byte zu einer Zeit (obwohl wir eigentlich benötigt, um zu Lesen ein byte Voraus, wo wir gearbeitet haben).
(Für die EOF-ich habe nicht Ihre Artikel Lesen, so dass ich weiß nicht, ob unsere Idee funktioniert mit deinem Ansatz.)
Huffman-Kodierung gibt an, wie erstellen Sie den Huffman-Baum aus eine Folge von Zeichen, und dann, wie zu codieren, dass in einer Folge von bits.
Es ist nicht angegeben, wie sollte man das codieren der Baum-oder wie genau herauszufinden, wie viele bits zu Lesen. Die exakte Anzahl von bits ist ein problem, weil Sie sparen können nur ganze bytes in einer Datei. Und so müssen Sie einige Weg, um genau herauszufinden, an dem etwas zu Ende.
Kodierung für die Baum, es gibt mehrere Optionen. Einer von Ihnen ist-Aufnahme wird die Anzahl für jedes Zeichen, und lassen Sie den decoder rekonstruieren Sie den Baum aus, der. Eine andere option ist die direkte Kodierung der Baum irgendwie, zum Beispiel mit dem 0-1 Ansatz Räude (und ich nehme die Artikel, die Sie erwähnt) beschreibt.
Dann gibt es adaptive Huffman-Codierung, die nicht erfordern den Baum, aber ist komplizierter.
Für die Entscheidung, Wann zu beenden, könnten Sie schreiben, dass die Gesamtzahl der Zeichen in der Datei, und verwenden, wenn Sie entscheiden, zu stoppen. Oder Sie können diese Anzahl für Sie kostenlos, wenn Sie codiert den Baum mit Charakter zählt.
Andere option ist die Verwendung einer EOF-Zeichen. Dies ist ein Zeichen, das in Ihrer Huffman-Baum, aber nicht codieren jeder normalen Wert. Sie könnten es sich vorstellen, als 257th Wert, vorausgesetzt, Sie sind Codierung Byte. (Sie könnte Verwendung einigen normalen Wert, wie das null-byte, für die EOF-token, aber das würde erfordern, dass Sie absolut sicher sein, es wird nicht vorhanden sein, in der Eingabe-Datei.)