Rechnernetze
|
Huffmann-KodierungDie einfache Huffmann-Kodierung stellt eine algorithmische Umsetzung der informationstheoretischen Regel dar, möglichst gleichwahrscheinliche Teilmengen der zu kodierenden Werte zu verwenden, um eine (sub-) optimale Kodierung zu erhalten. Sie erzeugt einen binären Baum, dessen Blätter den Zeichen entsprechen, und der zu jedem Knoten zwei Nachfolger (0, 1) besitzt. Eine Kodierung verwendet jeweils ein entsprechendes Anfangsstück. 1. Initialisierung: Alle Zeichen werden Knoten zugeordnet und nach ihrer Häufigkeit in einer Liste sortiert. 2. Solange die Liste der Knoten noch mehr als ein Element enthält:
Im obigen Beispiel werden 87 Bits zu Kodierung benutzt, während eine Kodierung mit jeweils 3 Bits 121 Bits benötigen würde. Die idelle Entropie ist 2.19, währen die wahre Entropie in diesem Beispiel 87/39 = 2,23 ist, also nahe an der wahren Entropie liegt. |