Huffman-Codierung

Angenommen, du hast einen Text mit den Zeichen A, B, C und D, die mit den Häufigkeiten 5, 9, 12 und 13 auftreten. Der erste Schritt wäre das Zusammenführen der Symbole A und B, da sie die niedrigsten Frequenzen haben. Dies erzeugt eine neue Einheit mit der kombinierten Frequenz von 14. Der Prozess wird fortgesetzt, bis nur noch eine Einheit übrig bleibt, die den gesamten Text repräsentiert.

Im Beispiel der Zeichen A, B, C und D, würde der Baum wie folgt aussehen:

     50
    /  \
 20   30
/  \ /  \
A B C   D
5 15  12 18 

Angenommen, du hast einen Text mit den Zeichen A, B, C und D, die mit den Häufigkeiten 5, 9, 12 und 13 auftreten. Mit der Huffman-Codierung würden die Symbole folgendermaßen kodiert:

A -> 110
B -> 111
C -> 0
D -> 10

Durch folgenden Java-Code lässt sich ein Huffman-Baum erstellen:

 
PriorityQueue queue = initializeQueue(data);
HuffNode root = null;

while (queue.size() > 1) {
  HuffNode x = queue.peek();
  queue.poll();
  
  HuffNode y = queue.peek();
  queue.poll();
  
  HuffNode tree_node = new HuffNode();
  tree_node.data = x.data + y.data;
  tree_node.left = x;
  tree_node.right = y;
  
  root = tree_node;
  
  queue.add(tree_node);
}

Das Codieren der Zeichen mit Huffman-Codierung in Python könnte beispielsweise durch folgenden Code erreicht werden:

 
import heapq
from collections import defaultdict

def encode(frequency):
  heap = [[weight, [symbol, ""]] for symbol, weight in frequency.items()]
  heapq.heapify(heap)
  
  while len(heap) > 1:
    lo = heapq.heappop(heap)
    hi = heapq.heappop(heap)
    
    for pair in lo[1:]:
      pair[1] = '0' + pair[1]
    for pair in hi[1:]:
      pair[1] = '1' + pair[1]
      
    heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
  return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

Wenn wir das Beispiel der Zeichen A (5), B (9), C (12) und D (13) betrachten, entsteht der Huffman-Baum folgendermaßen:

     39
    /  \
  14   25
 / \  / \
A  B C   D
5 9 12 13

Hier der entsprechende Code in Python:

import heapq
from collections import defaultdict

def encode(frequency):
  heap = [[weight, [symbol, ""]] for symbol, weight in frequency.items()]
  heapq.heapify(heap)

  while len(heap) > 1:
    lo = heapq.heappop(heap)
    hi = heapq.heappop(heap)

    for pair in lo[1:]:
      pair[1] = '0' + pair[1]
    for pair in hi[1:]:
      pair[1] = '1' + pair[1]
      
    heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
  return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

Nehmen wir zum Beispiel an, dass ein Zeichen mit der Häufigkeit 5 den Code '110' und ein Zeichen mit der Häufigkeit 9 den Code '111' hat. Dann ist die Länge des gesamten codierten Textes gleich \(5 \cdot 3 + 9 \cdot 3 = 42\). Würde man den kürzeren Code dem häufiger vorkommenden Zeichen zuweisen, wäre die gesamte Länge des codierten Textes nur \(5 \cdot 3 + 9 \cdot 2 = 33\), was wesentlich effizienter wäre.