{"id":189442,"date":"2026-02-19T20:11:20","date_gmt":"2026-02-19T19:11:20","guid":{"rendered":"https:\/\/liora.io\/de\/?p=189442"},"modified":"2026-02-19T20:11:20","modified_gmt":"2026-02-19T19:11:20","slug":"huffman-codierung-so-gehts","status":"publish","type":"post","link":"https:\/\/liora.io\/de\/huffman-codierung-so-gehts","title":{"rendered":"Huffman Codierung: So geht’s!"},"content":{"rendered":"

Die Huffman Kodierung ist ein Algorithmus zur Datenkomprimierung. Die Idee dahinter ist, den Eingabezeichen Codes mit variabler L\u00e4nge zuzuweisen. Die L\u00e4nge der zugewiesenen Codes basiert auf der H\u00e4ufigkeit, mit der die Zeichen in der urspr\u00fcnglichen Sequenz vorkommen.<\/strong><\/p>\n\n\n\n

Die Huffman Codierung<\/strong> ist ein Algorithmus zur verlustfreien Datenkomprimierung. Dieser Algorithmus wurde 1952 von David Albert Huffman erfunden.<\/p>\n\n\n\n

Die Huffman-Kodierung ist im Allgemeinen wichtig, um Daten zu komprimieren, in denen es Zeichen gibt, die h\u00e4ufig vorkommen. Der Faktor H\u00e4ufigkeit wird hierbei aufgrund des Konzepts der Informationsentropie ber\u00fccksichtigt, denn je h\u00e4ufiger ein Zeichen auftritt, desto h\u00f6her ist die Entropie dieses Zeichens.<\/p>\n\n\n\n

Wie funktioniert die Huffman-Codierung?<\/h2>\n\n\n\n

Das Prinzip der Huffman Codierung beruht auf dem Aufbau einer Baumstruktur mit Knoten<\/a>. Dieser Algorithmus basiert auf der Idee,<\/a> dass die beste Art und Weise, eine Information zu kodieren, darin besteht, die optimale L\u00e4nge zu finden, um jedes Zeichen in der urspr\u00fcnglichen Sequenz darzustellen.<\/p>\n\n\n\n

Die optimale L\u00e4nge des Codes f\u00fcr ein Zeichen wird durch die Anzahl der Zweige bestimmt, die man von der Spitze des Huffman Baums<\/strong> aus durchlaufen muss, um zu diesem Zeichen zu gelangen, das immer ein Blatt des Huffman-Baums ist.<\/p>\n\n\n\n

Die Idee hinter dem Huffman-Baum ist es, die L\u00e4nge der Symbole, die man zur Verschl\u00fcsselung einer Nachricht verwendet, zu minimieren, und das bedeutet, die Gr\u00f6\u00dfe des Huffman-Baums zu minimieren. Man k\u00f6nnte sich jedoch fragen, wie der Huffman-Baum aufgebaut ist.<\/p>\n\n\n\n

\n
Tout savoir du codage de Huffman<\/a><\/div>\n<\/div>\n\n\n\n

Was ist das Prinzip der Huffman Codierung?<\/h3>\n\n\n\n

Was die Konstruktion des Baumes betrifft, so werden jedes Mal die beiden Knoten mit dem geringsten Gewicht miteinander verbunden, um einen neuen „Vater“-Knoten zu erhalten, dessen Gewicht der Summe der Gewichte seiner S\u00f6hne entspricht.<\/p>\n\n\n\n

Dieser Vorgang wird so lange wiederholt, bis nur noch ein einziger Knoten \u00fcbrig bleibt: die Wurzel des Huffman-Baums<\/strong>, deren Gewicht der Summe der Gewichte aller urspr\u00fcnglichen Blattknoten entspricht. Dann wird z. B. jeder Abzweigung, die nach links f\u00fchrt, der Code 0 und jeder Abzweigung, die nach rechts f\u00fchrt, der Code 1 zugeordnet.<\/p>\n\n\n\n

Um den bin\u00e4ren Code jedes Zeichens zu erhalten, durchl\u00e4uft man den Baum von der Spitze bis zu den Bl\u00e4ttern und nimmt jedes Mal das Zeichen 0 oder 1 von den Zweigen, die man durchl\u00e4uft, je nachdem, ob man von rechts oder von links kommt.<\/p>\n\n\n\n

Die einzelnen Schritte beim Bau des Huffman Tree<\/h4>\n\n\n\n
    \n
  1. Erstelle Blattknoten<\/strong> aus jedem Zeichen der zu verschl\u00fcsselnden Nachricht, wobei jedes Zeichen nur einmal mit den verschiedenen H\u00e4ufigkeiten des Auftretens der Zeichen ber\u00fccksichtigt wird, die nach Priorit\u00e4t geordnet werden sollen, wobei die Zeichen mit den niedrigsten H\u00e4ufigkeiten Vorrang haben.<\/li>\n\n\n\n
  2. Extrahiere die beiden Knoten<\/strong> mit der niedrigsten Gewichtung in aufsteigender Reihenfolge der H\u00e4ufigkeit, d. h. der Knoten mit der niedrigsten H\u00e4ufigkeit muss zuerst extrahiert werden.<\/li>\n\n\n\n
  3. Erstelle einen neuen internen Knoten<\/strong> mit einer H\u00e4ufigkeit, die der Summe der H\u00e4ufigkeiten dieser beiden Knoten entspricht. Definiere den ersten extrahierten Knoten als den linken Sohn dieses Knotens und den zweiten Knoten als den rechten Sohn. F\u00fcge den neu erstellten Knoten zur Liste der verbleibenden Knoten hinzu.<\/li>\n\n\n\n
  4. Wiederhole die Schritte 2 und 3<\/strong>, bis du durch alle Knoten gegangen bist, die du in Schritt 1 erhalten hast. Der verbleibende Knoten ist die Wurzel des Baumes und die Konstruktion ist abgeschlossen.<\/li>\n<\/ol>\n\n\n\n

    Ein Beispiel zur Veranschaulichung der Verschl\u00fcsselung<\/h3>
    \"Diagramm,<\/figure>\n\n\n\n

    Um die Idee der Huffman Codierung zu veranschaulichen, betrachten wir die unten stehende Nachricht, die wir optimal in bin\u00e4rer Form darstellen werden:<\/p>\n\n\n\n

    aabbccddbbeaebdddfffdbffddabbbbbcdefaabbcccccaabbddfffdcecc<\/code><\/pre>\n\n\n\n
    Bei einer zu kodierenden Nachricht wie dieser beginnen wir zun\u00e4chst damit, die H\u00e4ufigkeit der verschiedenen Zeichen in der Nachricht zu z\u00e4hlen. Nach der Z\u00e4hlung erhalten wir das folgende Ergebnis:<\/p>\n\n\n\n
    a:8, b:15, c:11, d:12, e:4, f:9<\/code><\/pre>\n\n\n\n
    Wir werden den Algorithmus der Huffman Codierung<\/strong> an diesem Beispiel implementieren.<\/p>\n\n\n\n
    Der erste Schritt besteht darin, die am wenigsten h\u00e4ufigen Zeichen in der zu kodierenden Nachricht zu verwenden. Wir m\u00fcssen also mit den Buchstaben ‚e‘ und ‚a‘ beginnen, die die geringsten H\u00e4ufigkeiten haben, und dann ihre Gewichte summieren,<\/strong> d. h. die H\u00e4ufigkeiten ihres Auftretens summieren, um die beiden Zeichen durch ein neues, einzigartiges Zeichen zu ersetzen, dessen H\u00e4ufigkeit der Summe der H\u00e4ufigkeiten dieser beiden Zeichen in der Liste entspricht. Nach diesem ersten Schritt sieht die Liste wie folgt aus<\/p>\n\n\n\n
    new node:12, b:15, c:11, d:12, f:9<\/code><\/pre>\n\n\n\n
    wobei der Knoten new node die Knoten a und e mit einem Gewicht ersetzt, das der Summe ihrer jeweiligen Gewichte entspricht. [ new node : 12 = (a:8, e:4)]]<\/p>\n\n\n\n
    Dann w\u00e4hlst du aus der neuen Liste die beiden Elemente mit dem geringsten Gewicht aus und iterierst den Prozess, bis du den Knoten mit dem h\u00f6chsten Gewicht erh\u00e4ltst, d.h. mit dem Gewicht der Summe der H\u00e4ufigkeiten aller Zeichen. Am Ende des Aufbaus des Huffman-Baums<\/strong> sind alle verschiedenen Zeichen der urspr\u00fcnglichen Nachricht, die codiert werden soll, Bl\u00e4tter des Huffman-Baums, die auch als Leaf Nodes bezeichnet werden. Am Ende der Ausf\u00fchrung erh\u00e4lt man die folgenden Ergebnisse:<\/p>\n\n\n\n
    d -> 00 \ne -> 010 \na -> 011 \nb -> 10 \nf -> 110 \nc -> 111\t\t<\/code><\/pre>\n\n\n\n
    Wir erinnern uns, dass die Etiketten des Huffman-Baums<\/strong> markiert werden, indem wir die Konvention anwenden, eine 0 auf das linke Etikett und eine 1 auf das rechte Etikett in absteigender Reihenfolge zu setzen, d.h. von der Wurzel des Baums bis zu den Bl\u00e4ttern.<\/p>\n\n\n\n
    Die zeitliche Komplexit\u00e4t dieses Algorithmus ist quasi-linear, d.h. in O(nlogn), wobei n die Anzahl der eindeutigen Zeichen in der zu komprimierenden Liste ist, und die r\u00e4umliche Komplexit\u00e4t ist linear, d.h. in O(n).<\/p>\n\n\n\n
    string1 = 'aabbccddbbeaebdddfffdbffddabbbbbcdefaabbcccccaabbddfffdcecc'\nstring2 = 'abcdef'\n\n\ndef count(y):\n  i=0\n  for x in string1:\n    if x==y:\n      i=i+1\n  return i\n\nfor y in string2:\n  print(\"nombre d'occurences de la lettre\", y, (count(y)))\n  \n# L'arbre de Huffman\nimport heapq\n\n\nclass node:\n\tdef __init__(self, freq, symbol, left=None, right=None):\n\t\t#Fr\u00e9quence d'un symbole\n\t\tself.freq = freq\n\n\t\t# nom du symbole\n\t\tself.symbol = symbol\n\n\t\t# noeud de gauche\n\t\tself.left = left\n\n\t\t# noeud de droite\n\t\tself.right = right\n\n\t\t# direction de l'arbre (0\/1)\n\t\tself.huff = ''\n\n\tdef __lt__(self, nxt):\n\t\treturn self.freq < nxt.freq\n\n\n#fonction d'utilit\u00e9 pour afficher le codage de\n# Huffman pour tous les symboles pour l'arbre\n# de Huffman cr\u00e9e\ndef printNodes(node, val=''):\n\n\t# Code de Huffman\n\tnewVal = val + str(node.huff)\n\n\t# Si le noeud n'est pas un noeud de bord,\n\t# faire passer une ar\u00eate par ce dernier\n\tif(node.left):\n\t\tprintNodes(node.left, newVal)\n\tif(node.right):\n\t\tprintNodes(node.right, newVal)\n\n\t\t# Si c'est un noeud de bord,\n\t\t# extraire son codage de Huffman\n\tif(not node.left and not node.right):\n\t\tprint(f\"{node.symbol} -> {newVal}\")\n\n\n# caract\u00e8res du codage de Huffman\nchars = ['a', 'b', 'c', 'd', 'e', 'f']\n\n# fr\u00e9quence des caract\u00e8res\nfreq = [8, 15, 11, 12, 4, 9]\n\n# Liste contenant les noeuds non utilis\u00e9s\nnodes = []\n\n# conversion des caract\u00e8res et des fr\u00e9quences\n# en noeuds de l'arbre de Huffman\nfor x in range(len(chars)):\n\theapq.heappush(nodes, node(freq[x], chars[x]))\n\nwhile len(nodes) > 1:\n\n\t# Trier les noeuds par ordre croissant\n\t# de leur fr\u00e9quence\n\tleft = heapq.heappop(nodes)\n\tright = heapq.heappop(nodes)\n\n\t# Affecter des valeurs directionnelles \u00e0 ces noeuds\n\tleft.huff = 0\n\tright.huff = 1\n\n\t# Combiner les deux plus petits noeuds pour former un nouveau noeud\n\t# comme leur parent\n\tnewNode = node(left.freq+right.freq, left.symbol+right.symbol, left, right)\n\n\theapq.heappush(nodes, newNode)\n\n# L'arbre de Huffman est pr\u00eat !\nprintNodes(nodes[0])<\/code><\/pre>\n\n\n\n
    \n
    Lerne die Huffman-Codierung<\/a><\/div>\n<\/div>\n\n\n\n
    Wozu dient die Huffman codierung im Berufsleben?<\/h2>
    \"Diagramm,<\/figure>\n\n\n\n
    Zu den verschiedenen Anwendungen des Huffman-Codieralgorithmus<\/strong> f\u00fcr die Datenkomprimierung geh\u00f6ren die \u00dcbertragung von Faxen und Texten, konventionelle Komprimierungsformate wie GZIP, Multimedia-Software wie JPEG, PNG und MP3.<\/p>\n\n\n\n
    Im Allgemeinen ist die Datenkomprimierung n\u00fctzlich, um die Speicherkapazit\u00e4t des Arbeitsspeichers<\/a> oder die Geschwindigkeit der Daten\u00fcbertragung zu erh\u00f6hen. Bei der Erstellung des Baums gibt es Varianten der Huffman Codierung.<\/strong><\/p>\n\n\n\n
    Entweder ist das W\u00f6rterbuch statisch: Jedes Zeichen hat einen vordefinierten Code, der bekannt ist oder im Voraus ver\u00f6ffentlicht wird (und daher nicht \u00fcbertragen werden muss) ;<\/p>\n\n\n\n