{"id":1311,"date":"2026-09-03T07:02:01","date_gmt":"2026-09-03T07:02:01","guid":{"rendered":"https:\/\/ffritze.de\/?p=1311"},"modified":"2026-09-03T07:31:08","modified_gmt":"2026-09-03T07:31:08","slug":"daten-komprimieren-mit-koepfchen-teil-2-huffman-code-in-python-umsetzen","status":"publish","type":"post","link":"https:\/\/ffritze.de\/en\/daten-komprimieren-mit-koepfchen-teil-2-huffman-code-in-python-umsetzen\/","title":{"rendered":"Compressing Data with Smart (Part 2) \u2013 Converting Huffman Code in Python"},"content":{"rendered":"

In the first part, the example of KAFFEPAUSE<\/strong> was shown how the Huffman algorithm uses character frequency to create a binary tree and extract space-saving, unique codes from it. The basics are explained in detail in Teil 1<\/a> on ffritze.de.<\/p>\n\n\n\n

In this second part, the Huffman algorithm is implemented in Python<\/strong> and gradually traced in a Jupyter Notebook<\/strong>. The focus is not only on the finished program. The individual data structures and processing steps are made visible so that the construction of the Huffman tree and the generation of the codes can be tried out directly.<\/p>\n\n\n\n\n\n\n\n

\n
\n
\n
<\/div>\n\n\n\n
\"\"\n\t\t\t\n\t\t\t\t\n\t\t\t<\/svg>\n\t\t<\/button><\/figure>\n\n\n\n
<\/div>\n<\/div>\n<\/div>\n\n\n\n
\n

The abstract data type BinTree<\/code><\/strong> is used to display the tree. This is based on the abstract data types that play a role in the Lower Saxony computer science curriculum. The associated Python implementations and further information on abstract data types, including the binary tree, are described here: Abstract data types in school: Python implementations for download<\/a>.<\/p>\n<\/div>\n<\/div>\n\n\n\n

The notebook thus combines the theoretical foundations from Teil 1<\/a> with a concrete programming. Starting from a text, a frequency analysis is first carried out. On this basis, a Huffman tree is created, on which the coding of the text is subsequently tested.<\/p>\n\n\n\n

\n

Open Jupyter Notebook<\/h2>\n\n\n\n
\n
\n

The entire notebook can be opened directly in JupyterLite and run there. In addition to the frequency analysis and the creation of the Huffman tree, the file also contains other functions for generating the Huffman codes as well as for encoding and decoding texts. Open the notebook and play through the entire process once with the word \"KAFFEPAUSE\"<\/strong>:<\/p>\n<\/div>\n\n\n\n

\n
\"\"\n\t\t\t\n\t\t\t\t\n\t\t\t<\/svg>\n\t\t<\/button><\/figure>\n<\/div>\n<\/div>\n\n\n\n

Open Huffman's algorithm in JupyterLite<\/a><\/a><\/p>\n\n\n\n

After opening the code at the top right, first set the code to \"Trusted\"<\/strong>and then select Python<\/strong> as the kernel. Each code cell can be executed one after the other with Shift + Enter<\/strong>.<\/p>\n<\/div>\n\n\n\n

Determine the frequencies of the characters<\/h2>\n\n\n\n

Before the Huffman tree can be created, it is first necessary to examine how often each character occurs in the source text. This frequency analysis is used by the function frequency_analysis_of(text)<\/code>.<\/p>\n\n\n\n

As a result, the function provides a dictionary (dictionary<\/code>). In it, each character is assigned its absolute frequency. The text is scrolled through character by character:<\/p>\n\n\n\n

\n
\n
    \n
  • If a character is already included in the dictionary, its numerator is increased by one.<\/li>\n\n\n\n
  • If a character appears for the first time, it is recorded with the value 1<\/code>.<\/li>\n\n\n\n
  • At the end, the dictionary contains all the characters that appear in the text with their respective frequency.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
    \n
    \n
    <\/div>\n\n\n\n
    \"\"\n\t\t\t\n\t\t\t\t\n\t\t\t<\/svg>\n\t\t<\/button><\/figure>\n\n\n\n
    <\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
    def frequency_analysis_of(text):\n    frequencies = {}\n    for char in text:\n        if char in frequencies:\n            frequencies[char] += 1\n        else:\n            frequencies[char] = 1\n    return frequencies<\/code><\/pre>\n\n\n\n
    The variable frequencies<\/code> stores the frequency table. By calling the function with any text, this table can then be used for the structure of the Huffman tree.<\/p>\n\n\n\n
    The Huffman Tree<\/h2>\n\n\n\n
    For the creation of the Huffman tree, two preparatory steps are first carried out. This is followed by the actual function huffman_tree_from(frequencies)<\/code>.<\/p>\n\n\n\n
    1. Import of the class BinTree<\/code><\/h3>\n\n\n\n
    The class BinTree<\/code> is loaded directly from a GitHub repository. As a result, no additional file has to be stored on your own computer. However, an Internet connection is required to run this code.<\/p>\n\n\n\n
    from urllib.request import urlopen\nfrom types import ModuleType\nimport sys\n\nurl = \"https:\/\/raw.githubusercontent.com\/ffritzemedia\/ADT_Python\/main\/ADT\/adt.py\"\n\nadt_remote = ModuleType(\"adt_remote\")\n\nwith urlopen(url) as antwort:\n    quelltext = antwort.read().decode(\"utf-8\")\n\nexec(compile(quelltext, url, \"exec\"), adt_remote.__dict__)\n\nsys.modules[\"adt_remote\"] = adt_remote\n\nBinTree = adt_remote.BinTree<\/code><\/pre>\n\n\n\n
    2. Auxiliary class for the tree knots<\/h3>\n\n\n\n
    Both the sign and its frequency should be stored in the tree nodes. The help class item<\/code> is used for this purpose.<\/p>\n\n\n\n
    class item:\n    def __init__(self, weight, char):\n        self.weight = weight\n        self.char = char\n\n    def __lt__(self, other):\n        return self.weight < other.weight<\/code><\/pre>\n\n\n\n
    The attribute weight<\/code> stores the weight or frequency of a character. The attribute char<\/code> contains the associated character.<\/p>\n\n\n\n
    The __lt__<\/code> method determines how to compare two objects of the item<\/code> class. Their weights are compared. This allows the trees to be sorted later according to their frequency.<\/p>\n\n\n\n
    3. Huffman Tree Creation Feature<\/h3>\n\n\n\n
    The huffman_tree_from(frequencies)<\/code> function creates a Huffman tree from a dictionary with character frequencies. The principle of the Huffman algorithm is implemented: the two trees with the smallest weights are always selected and combined to form a new tree.<\/p>\n\n\n\n
    First, the class BinTree<\/code> is extended by the comparison function bin_tree_lt<\/code>. As a result, the tree objects can be compared and sorted with each other based on the weight of their contents:<\/p>\n\n\n\n
    def bin_tree_lt(self, other):\n    return self.getItem() < other.getItem()\n\nBinTree.__lt__ = bin_tree_lt<\/code><\/pre>\n\n\n\n
    Subsequently, a separate tree is created for each character from the dictionary with a content of the class item<\/code>. In this content, the character and its frequency are stored:<\/p>\n\n\n\n
    trees = []\n\nfor char, weight in frequencies.items():\n    tree = BinTree(item(weight, char))\n    trees.append(tree)<\/code><\/pre>\n\n\n\n
    The resulting trees are sorted according to their weight. As long as there is more than one tree, the two trees with the smallest weights are removed:<\/p>\n\n\n\n
    trees = sorted(trees)\n\nwhile len(trees) > 1:\n    left = trees.pop(0)\n    right = trees.pop(0)<\/code><\/pre>\n\n\n\n
    From these two trees a new common tree is created. Its weight is the sum of the two individual weights. Since the new node does not correspond to a single character, its character is specified with None<\/code>:<\/p>\n\n\n\n
    merge = BinTree(\n    item(left.getItem().weight + right.getItem().weight, None),\n    left,\n    right\n)<\/code><\/pre>\n\n\n\n
    The new tree will be added back to the list. After that, the list is sorted again so that the two trees with the smallest weights can be selected again in the next run:<\/p>\n\n\n\n
    trees.append(merge)\ntrees = sorted(trees)<\/code><\/pre>\n\n\n\n
    This process is repeated until only a single tree remains. This tree is the complete Huffman tree and will be returned at the end:<\/p>\n\n\n\n
    return trees.pop(0)<\/code><\/pre>\n\n\n\n
    The weight sum of the root node corresponds to the total number of all characters of the text examined. The sheets contain the individual characters, while the inner nodes only store the aggregated weight sums.<\/p>\n\n\n\n
    Conclusion<\/h2>\n\n\n\n
    \n
    \n
    This makes the path from the frequency analysis to the structure of the Huffman tree to the coding and decoding of a text completely comprehensible. The notebook offers the possibility to try out the individual steps yourself and to explore the principle of lossless data compression in practice. Good luck experimenting with the Huffman algorithm!<\/p>\n<\/div>\n\n\n\n
    \n
    \"\"\n\t\t\t\n\t\t\t\t\n\t\t\t<\/svg>\n\t\t<\/button><\/figure>\n<\/div>\n<\/div>","protected":false},"excerpt":{"rendered":"
    Im ersten Teil wurde am Beispiel von KAFFEEPAUSE gezeigt, wie der Huffman-Algorithmus anhand von Zeichenh\u00e4ufigkeiten einen Bin\u00e4rbaum erstellt und daraus platzsparende, eindeutige Codes gewinnt. Die Grundlagen werden in Teil 1 auf ffritze.de ausf\u00fchrlich erkl\u00e4rt. In diesem zweiten Teil wird der Huffman-Algorithmus in Python implementiert und in einem Jupyter Notebook schrittweise nachvollzogen. Dabei steht nicht nur das fertige Programm im Mittelpunkt. Die einzelnen Datenstrukturen […]<\/p>\n","protected":false},"author":2,"featured_media":1314,"comment_status":"open","ping_status":"open","sticky":false,"template":"seite-thoughts-beitrag","format":"standard","meta":{"footnotes":""},"categories":[19,7,21],"tags":[90,88,91,22],"class_list":["post-1311","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithms","category-programs","category-python","tag-codes","tag-huffman","tag-jupyter","tag-python"],"_links":{"self":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/posts\/1311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/comments?post=1311"}],"version-history":[{"count":0,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/posts\/1311\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/media\/1314"}],"wp:attachment":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/media?parent=1311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/categories?post=1311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/tags?post=1311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}