Auch als Huffman-Codierung bekannt, ein Algorithmus zur verlustfreien Komprimierung von Dateien basierend auf der Häufigkeit des Auftretens eines Symbols in der zu komprimierenden Datei. Der Huffman-Algorithmus basiert auf statistischer Codierung, was bedeutet, dass die Wahrscheinlichkeit eines Symbols einen direkten Einfluss auf die Länge seiner Darstellung hat. Je wahrscheinlicher das Auftreten eines Symbols ist, desto kürzer ist seine Bitgrößendarstellung. In jeder Datei werden bestimmte Zeichen häufiger verwendet als andere. Bei Verwendung der binären Darstellung hängt die Anzahl der zur Darstellung jedes Zeichens erforderlichen Bits von der Anzahl der Zeichen ab, die dargestellt werden müssen. Mit einem Bit können wir zwei Zeichen darstellen, dh 0 steht für das erste Zeichen und 1 für das zweite Zeichen. Mit zwei Bits können wir vier Zeichen darstellen und so weiter.
Im Gegensatz zu ASCII-Code, bei dem es sich um einen Code mit fester Länge und sieben Bits pro Zeichen handelt, handelt es sich bei der Huffman-Komprimierung um ein Codierungssystem mit variabler Länge, das kleinere Codes für häufiger verwendete Zeichen und größere Codes für weniger häufig verwendete Zeichen zuweist, um die Größe von zu verringern Dateien werden komprimiert und übertragen.
Zum Beispiel in einer Datei mit den folgenden Daten:
XXXXXXYYYYZZ
Die Frequenz von "X" ist 6, die Frequenz von "Y" ist 4 und die Frequenz von "Z" ist 2. Wenn jedes Zeichen mit einem Code fester Länge von zwei Bits dargestellt wird, ist die Anzahl der Bits erforderlich Speichern Sie diese Datei wäre 24, dh (2 x 6) + (2x 4) + (2x 2) = 24.
Wenn die obigen Daten unter Verwendung der Huffman-Komprimierung komprimiert würden, würden die häufiger auftretenden Zahlen durch kleinere Bits dargestellt, wie z.
X durch den Code 0 (1 Bit)
Y durch den Code 10 (2 Bits)
Z durch den Code 11 (2 Bits)
daher wird die Größe der Datei 18, dh (1 × 6) + (2 × 4) + (2 × 2) = 18.
Im obigen Beispiel werden häufiger vorkommenden Zeichen kleinere Codes zugewiesen, was zu einer geringeren Anzahl von Bits in der endgültigen komprimierten Datei führt.
Die Huffman-Komprimierung wurde nach ihrem Entdecker David Huffman benannt.