So komprimieren sie daten mithilfe der huffman-kodierung

Huffmans Algorithmus wird verwendet, um Daten zu komprimieren oder zu kodieren. Normalerweise wird jedes Zeichen in einer Textdatei als acht Bits (Ziffern, entweder 0 oder 1) gespeichert, die diesem Zeichen mit einer Codierung mit dem Namen ASCII kennzeichnen. Eine Huffman-codierte Datei zerbricht die starre 8-Bit-Struktur, sodass die am häufigsten verwendeten Zeichen in wenigen Bits gespeichert werden (`A` könnte sein "10" oder "1000" anstatt der ASCII, was ist "01100001"). Die am wenigsten gemeinsamen Zeichen dauern oft viel mehr als 8 Bits (`Z` könnte sein "00100011010"), aber weil sie so selten auftreten, erzeugt Huffman-Kodierung insgesamt eine viel kleinere Datei als das Original.

Schritte

Teil 1 von 2:
Codierung
  1. Bildtitel Komprimaten mit Huffman-Kodierung Schritt 1
1. Zählen Sie die Frequenz jedes Zeichens in der zu codierenden Datei. Fügen Sie ein Dummy-Zeichen ein, um das Ende der Datei zu markieren. Dies ist später wichtig. Nennen Sie es jetzt den EOF (Ende der Datei) und markieren Sie es als Häufigkeit von 1.
  • Wenn Sie beispielsweise eine Textdatei-Lesung codieren möchten "ab ABAB," Sie hätten "a" mit Frequenz 3, `B` mit Frequenz 3, `` (Raum) mit Frequenz 2, `C` mit Frequenz 1 und EOF mit Frequenz 1.
  • Bild mit dem Titel Komprimaten mit Huffman-Kodierung Schritt 2
    2. Speichern Sie die Zeichen als Baumknoten und setzen Sie sie in eine Prioritätswarteschlange. Sie bauen einen großen Binärbaum mit jedem Charakter als Blatt, sodass Sie die Zeichen in einem Format speichern sollten, so dass sie Knoten des Baums werden können. Platzieren Sie diese Knoten in eine Prioritätswarteschlange mit der Häufigkeit des jeweiligen Zeichens als Priorität des Knotens.
  • Ein Binärbaum ist ein Datenformat, in dem jedes Datenbild ein Knoten ist, der bis zu einem Elternteil und zwei Kindern auftreten kann. Es wird oft als Verzweigungsbaum gezeichnet, daher der Name.
  • Eine Warteschlange ist eine treffer genannte Datenerhebung, in der das erste, was in die Warteschlange eingeht, auch das erste, was herauskommt (wie das Warten in der Zeile). In einem Priorität Warteschlange, die Daten werden in der Reihenfolge ihrer Priorität gespeichert, so dass das erste, was herauskommt, das dringendste, das Ding mit der kleinsten Priorität, anstatt das erste, was nativ ist.
  • In dem "ab ABAB" Beispiel, Ihre Prioritätswarteschlange würde so aussehen: {`c`: 1, EOF: 1, ``: 2, `A`: 3, `B`: 3}
  • Bildtitel Compress-Daten mit Huffman-Kodierung Schritt 3
    3. Beginnen Sie, Ihren Baum zu bauen. Entfernen (oder Dequeue) die beiden dringendsten Dinge aus der Prioritätswarteschlange. Erstellen Sie einen neuen Baumknoten, um den Elternteil dieser beiden Knoten zu sein, und speichern Sie den ersten Knoten als linkes Kind und das zweite als richtiges Kind. Die Priorität des neuen Knotens sollte die Summe der Prioritäten seines Kindes sein. Dann nehmern Sie diesen neuen Knoten in der Prioritätswarteschlange.
  • Die Prioritätswarteschlange sieht jetzt so aus: {``: 2, Neuer Knoten: 2, `A`: 3, `B`: 3}
  • Bild mit dem Titel Komprimaten mit Huffman-Kodierung Schritt 4
    4. Beenden Sie den Bau Ihres Baums: Wiederholen Sie den obigen Schritt, bis in der Warteschlange nur ein Knoten vorhanden ist. Beachten Sie, dass zusätzlich zu den Knoten, die Sie für die Charaktere und deren Frequenzen erstellt haben, auch deaktivieren, in Bäume verwandeln und übergeordnete Knoten, Knoten, die bereits selbst Bäume sind.
  • Wenn Sie fertig sind, ist der letzte Knoten in der Warteschlange der Wurzel des kodierenden Baums, mit allen anderen Knoten, die davon abzweigen.
  • Die am häufigsten verwendeten Zeichen sind die Blätter, die der Oberseite des Baums am nächsten liegen, während die selten verwendeten Zeichen am Boden des Baums positioniert sind, weiter von der Wurzel entfernt.
  • Bild mit dem Titel Komprimaten mit Huffman-Kodierung Schritt 5
    5. Erstelle ein kodierende Karte. Gehen Sie durch den Baum, um jeden Charakter zu erreichen. Jedes Mal, wenn Sie das linke Kind eines Knotens besuchen, ist das ein "0". Jedes Mal, wenn Sie das rechte Kind eines Knotens besuchen, ist das ein "1". Wenn Sie zu einem Charakter gelangen, lagern Sie den Charakter mit der Reihenfolge von 0s und 1s, dass es dauerte, um dorthin zu gelangen. Diese Reihenfolge ist das, was das Zeichen wie in der komprimierten Datei codiert wird. Speichern Sie die Zeichen und ihre Sequenzen in einer Karte.
  • Beginnen Sie zum Beispiel an der Wurzel. Besuchen Sie das linke Kind des Wurzels und besuchen Sie dann das linke Kind des Knotens. Da der Knoten jetzt keine Kinder hat, haben Sie einen Charakter erreicht. Das ist ` `. Da Sie zweimal gelaufen sind, um hierher zu kommen, ist die Kodierung für `` "00".
  • Für diesen Baum wird die Karte so aussehen: {``:"00", `ein`:"10", `B`:"11", `c`:"010", EOF:"011"}.
  • Bildtitel Komprimaten mit Huffman-Kodierungsschritt 6
    6. Geben Sie in der Ausgabedatei die Kodierkarte als Header ein. Dadurch kann die Datei dekodiert werden.
  • Bildtitel Compress-Daten mithilfe von Huffman-Kodierungsschritt 7
    7. Codiert die Datei. Für jedes Zeichen in der zu codierenden Datei schreiben Sie die binäre Sequenz, die Sie in der Karte gespeichert haben. Sobald Sie mit der Codierung der Datei fertig sind, verleihen Sie den EOF bis zum Ende.
  • Für die Datei "ab ABAB", Die codierte Datei sieht so aus: "1011001011000101011011".
  • Dateien werden als Bytes gespeichert (8 Bit oder 8 binäre Ziffern). Da der Huffman-Codier-Algorithmus das 8-Bit-Format nicht verwendet, haben codierte Dateien häufig keine Längen von mehreren Längen von 8. Die verbleibenden Ziffern werden mit 0s ausgefüllt. In diesem Fall würden am Ende der Datei zwei 0s hinzugefügt, die wie ein anderer Speicherplatz aussieht. Dies könnte ein Problem sein: Wie würde der Decoder wissen, wann das Lesen aufhören soll?? Da wir jedoch einen Charakter mit einem Dateien aufgenommen haben, erscheint der Decoder dazu, und hört dann auf und ignoriert alles andere, was danach hinzugefügt wurde.
    • Teil 2 von 2:
    Dekodierung
    1. Bildtitel Compress-Daten mit Huffman-Kodierungsschritt 8
    1. Lesen Sie in einer Huffman-codierten Datei. Lesen Sie zuerst den Header, der die Kodierkarte sein sollte. Verwenden Sie diese Option, um einen Dekodierbaum auf dieselbe Weise zu erstellen, wie Sie den Baum erstellt haben, den Sie mit der Datei kodieren. Die beiden Bäume sollten identisch sein.
  • Bild mit dem Titel Komprimaten mit Huffman-Kodierungsschritt 9
    2. Lesen Sie in der binären Ziffer zu einer Zeit in der binären Ziffer. Traverse den Baum, wenn Sie lesen. Wenn Sie ein Blatt erreichen (ein Knoten ohne Kinder), sind Sie an einem Charakter angekommen. Schreiben Sie das Zeichen in die decodierte Datei.
  • Aufgrund der Art, wie die Zeichen in der Baumstruktur gespeichert sind, haben die Codes für jedes Zeichen a Präfix-Eigenschaft, Damit kann ein Binärkodieren eines Charakters jemals zu Beginn eines anderen Zeichens eines anderen Zeichens auftreten. Die Kodierung für jedes Zeichen ist total einzigartig. Dies macht das Dekodieren viel einfacher.
  • Bild mit dem Titel Komprimaten mit Huffman-Kodierungsschritt 10
    3. Wiederholen, bis Sie den EOF erreichen. Herzliche Glückwünsche! Sie haben die Datei decodiert.

    • Tipps

    In Verbindung stehende Artikel