Der Algorithmus von Huffman wird verwendet, um Daten zu komprimieren oder zu codieren. Normalerweise wird jedes Zeichen in einer Textdatei als acht Bits (Ziffern, entweder 0 oder 1) gespeichert, die diesem Zeichen unter Verwendung einer Codierung namens ASCII zugeordnet werden. Eine Huffman-codierte Datei bricht die starre 8-Bit-Struktur auf, sodass die am häufigsten verwendeten Zeichen in nur wenigen Bits gespeichert werden ('a' könnte "10" oder "1000" sein, anstatt ASCII, also "01100001".). Die am wenigsten verbreiteten Zeichen benötigen dann oft viel mehr als 8 Bit ('z' könnte "00100011010" sein), aber weil sie so selten vorkommen, erzeugt die Huffman-Kodierung insgesamt eine viel kleinere Datei als das Original.
Schritte
Teil 1 von 2: Kodierung
Schritt 1. Zählen Sie die Häufigkeit jedes zu codierenden Zeichens in der Datei
Fügen Sie ein Dummy-Zeichen hinzu, um das Ende der Datei zu markieren – dies wird später wichtig sein. Nennen Sie es vorerst EOF (Ende der Datei) und markieren Sie es mit einer Häufigkeit von 1.
Wenn Sie beispielsweise eine Textdatei mit der Aufschrift "ab ab cab " codieren möchten, haben Sie 'a' mit Häufigkeit 3, 'b' mit Häufigkeit 3, '' (Leerzeichen) mit Häufigkeit 2, 'c' mit Häufigkeit 1, und EOF mit Frequenz 1
Schritt 2. Speichern Sie Zeichen als Baumknoten und stellen Sie sie in eine Prioritätswarteschlange
Sie werden einen großen Binärbaum mit jedem Zeichen als Blatt erstellen, daher sollten Sie die Zeichen in einem Format speichern, damit sie zu Knoten des Baums werden können. Platzieren Sie diese Knoten in einer Prioritätswarteschlange mit der Häufigkeit jedes Zeichens als Priorität seines Knotens.
- Ein binärer Baum ist ein Datenformat, bei dem jedes Datenelement ein Knoten ist, der bis zu ein Elternteil und zwei Kinder haben kann. Es wird oft als verzweigter Baum gezeichnet, daher der Name.
- Eine Warteschlange ist eine treffend benannte Datensammlung, bei der das erste, was in die Warteschlange geht, auch als erstes herauskommt (wie das Warten in der Schlange). In einer Prioritätswarteschlange werden die Daten in der Reihenfolge ihrer Priorität gespeichert, so dass als Erstes die dringendste Sache herauskommt, die Sache mit der niedrigsten Priorität, und nicht die erste, die in die Warteschlange eingereiht wird.
- Im Beispiel "ab ab cab" würde Ihre Prioritätswarteschlange so aussehen: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Schritt 3. Beginnen Sie mit dem Aufbau Ihres Baumes
Entfernen (oder entfernen) Sie die beiden dringendsten Dinge aus der Prioritätswarteschlange. Erstellen Sie einen neuen Baumknoten, der diesen beiden Knoten übergeordnet ist, und speichern Sie den ersten Knoten als seinen linken und den zweiten als seinen rechten untergeordneten Knoten. Die Priorität des neuen Knotens sollte die Summe der Prioritäten seines untergeordneten Knotens sein. Stellen Sie diesen neuen Knoten dann in die Prioritätswarteschlange ein.
Die Prioritätswarteschlange sieht jetzt so aus: {' ':2, new node:2, 'a':3, 'b':3}
Schritt 4. Beenden Sie den Aufbau Ihres Baums:
Wiederholen Sie den obigen Schritt, bis sich nur noch ein Knoten in der Warteschlange befindet. Beachten Sie, dass Sie zusätzlich zu den Knoten, die Sie für die Zeichen und deren Häufigkeiten erstellt haben, auch die Warteschlange entfernen, sich in Bäume verwandeln und Elternknoten wieder einreihen, Knoten, die selbst bereits Bäume sind.
- Wenn Sie fertig sind, ist der letzte Knoten in der Warteschlange die Wurzel des Codierungsbaums, von dem alle anderen Knoten abzweigen.
- Die am häufigsten verwendeten Zeichen sind die Blätter, die der Baumspitze am nächsten sind, während die selten verwendeten Zeichen am unteren Rand des Baums, weiter von der Wurzel entfernt, positioniert werden.
Schritt 5. Erstellen Sie eine Codierungszuordnung. Gehen Sie durch den Baum, um jedes Zeichen zu erreichen. Jedes Mal, wenn Sie das linke Kind eines Knotens besuchen, ist dies eine '0'. Jedes Mal, wenn Sie das rechte Kind eines Knotens besuchen, ist das eine '1'. Wenn Sie zu einem Zeichen gelangen, speichern Sie das Zeichen mit der Folge von 0s und 1s, die es brauchte, um dorthin zu gelangen. Mit dieser Sequenz wird das Zeichen in der komprimierten Datei codiert. Speichern Sie die Zeichen und ihre Sequenzen in einer Karte.
- Beginnen Sie beispielsweise mit der Wurzel. Besuchen Sie das linke untergeordnete Element der Wurzel und dann das linke untergeordnete Element dieses Knotens. Da der Knoten, an dem Sie sich gerade befinden, keine Kinder hat, haben Sie einen Charakter erreicht. Das ist ' '. Da Sie zweimal nach links gegangen sind, um hierher zu gelangen, ist die Codierung für ' ' "00".
- Für diesen Baum sieht die Karte so aus: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Schritt 6. Fügen Sie die Codierungszuordnung als Header in die Ausgabedatei ein
Dadurch kann die Datei entschlüsselt werden.
Schritt 7. Codieren Sie die Datei
Schreiben Sie für jedes zu codierende Zeichen in der Datei die Binärsequenz, die Sie in der Karte gespeichert haben. Wenn Sie mit dem Kodieren der Datei fertig sind, stellen Sie sicher, dass Sie das EOF am Ende hinzufügen.
- Für die Datei "ab ab cab" sieht die codierte Datei so aus: "1011001011000101011011".
- Dateien werden als Bytes (8 Bit oder 8 Binärziffern) gespeichert. Da der Huffman-Kodierungsalgorithmus nicht das 8-Bit-Format verwendet, haben kodierte Dateien oft keine Längen, die ein Vielfaches von 8 sind. Die restlichen Ziffern werden mit Nullen aufgefüllt. In diesem Fall würden am Ende der Datei zwei Nullen hinzugefügt, was wie ein weiteres Leerzeichen aussieht. Dies könnte ein Problem sein: Woher weiß der Decoder, wann er mit dem Lesen aufhören muss? Da wir jedoch ein Zeichen für das Ende der Datei eingefügt haben, wird der Decoder zu diesem Punkt gelangen und dann anhalten, wobei er alles andere ignoriert, was danach hinzugefügt wurde.
Teil 2 von 2: Dekodierung
Schritt 1. Lesen Sie eine Huffman-codierte Datei ein
Lesen Sie zuerst den Header, der die Codierungszuordnung sein sollte. Verwenden Sie dies, um einen Decodierungsbaum auf die gleiche Weise zu erstellen, wie Sie den Baum erstellt haben, mit dem Sie die Datei codiert haben. Die beiden Bäume sollten identisch sein.
Schritt 2. Lesen Sie die binäre Ziffer nach der anderen ein
Durchqueren Sie den Baum beim Lesen: Wenn Sie eine '0' einlesen, gehen Sie zum linken Kind des Knotens, an dem Sie sich befinden, und wenn Sie eine '1' einlesen, gehen Sie zum rechten Kind. Wenn Sie ein Blatt erreichen (ein Knoten ohne Kinder), sind Sie bei einem Charakter angekommen. Schreiben Sie das Zeichen in die dekodierte Datei.
Aufgrund der Art und Weise, wie die Zeichen im Baum gespeichert werden, haben die Codes für jedes Zeichen eine Präfixeigenschaft, sodass die binäre Codierung eines Zeichens niemals am Anfang der Codierung eines anderen Zeichens auftreten kann. Die Codierung für jedes Zeichen ist völlig einzigartig. Dies erleichtert die Dekodierung erheblich
Schritt 3. Wiederholen Sie den Vorgang, bis Sie den EOF erreichen
Herzliche Glückwünsche! Sie haben die Datei entschlüsselt.
