Welche Datenstruktur wird bei der Huffman-Codierung verwendet?

Die bei der Huffman-Codierung verwendete Datenstruktur ist eine „Baumstruktur“. Mit der Unterstützung des Huffman-Algorithmus wird ein optimaler Binärbaum erstellt, und wir nennen diesen Baumtyp Huffman-Baum. Genauer gesagt handelt es sich bei der Huffman-Codierung um eine Codierungsform, die auf Huffman-Bäumen basiert.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Die bei der Huffman-Codierung verwendete Datenstruktur ist eine „Baumstruktur“.

Huffman-Codierung, auch als Huffman-Codierung bekannt, ist eine Codierungsmethode. Die Huffman-Codierung ist eine Art der Codierung mit variabler Länge (VLC). Huffman schlug 1952 eine Codierungsmethode vor. Diese Methode basiert vollständig auf der Wahrscheinlichkeit des Auftretens von Zeichen, um ein Codewort mit der kürzesten durchschnittlichen Länge verschiedener Präfixe zu konstruieren. Sie wird manchmal als beste Codierung bezeichnet und im Allgemeinen als Huffman-Codierung bezeichnet Hough-Kodierung).

Huffman-Codierung nutzt die Baumstruktur der Datenstruktur, um mit Unterstützung des Huffman-Algorithmus einen optimalen Binärbaum zu erstellen. Wir nennen diesen Baumtyp Huffman-Baum. Genauer gesagt handelt es sich bei der Huffman-Codierung um eine auf Huffman-Bäumen basierende Codierungsform mit einem sehr breiten Anwendungsspektrum.

Huffman-Baum

Konstruieren Sie bei gegebenen N Gewichten als N Blattknoten einen Binärbaum. Wenn die gewichtete Pfadlänge des Baums das Minimum erreicht, wird ein solcher Binärbaum als optimaler Binärbaum bezeichnet, der auch als Huffman-Baum bezeichnet wird Baum. Der Huffman-Baum ist der Baum mit der kürzesten gewichteten Pfadlänge, und Knoten mit größeren Gewichten liegen näher an der Wurzel.

Die sogenannte gewichtete Pfadlänge eines Baums ist das Gewicht aller Blattknoten im Baum multipliziert mit der Pfadlänge zum Wurzelknoten (wenn der Wurzelknoten Level 0 ist, die Pfadlänge vom Blattknoten zur Wurzel). (Knoten ist die Anzahl der Schichten von Blattknoten). Die Pfadlänge des Baums ist die Summe der Pfadlängen von der Baumwurzel zu jedem Knoten, aufgezeichnet als WPL = (W1*L1+W2*L2+W3*L3+...+Wn*Ln), N Gewichte Wi ( i=1,2,...n) bildet einen Binärbaum mit N Blattknoten, und die Pfadlänge des entsprechenden Blattknotens beträgt Li (i=1,2,...n). Es kann bewiesen werden, dass die WPL des Huffman-Baums die kleinste ist.

Weitere verwandte Artikel finden Sie auf der Chinesischen PHP-Website! !

Das obige ist der detaillierte Inhalt vonWelche Datenstruktur wird bei der Huffman-Codierung verwendet?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!