{"id":1308,"date":"2026-08-30T21:19:40","date_gmt":"2026-08-30T21:19:40","guid":{"rendered":"https:\/\/ffritze.de\/?p=1308"},"modified":"2026-09-04T08:33:42","modified_gmt":"2026-09-04T08:33:42","slug":"daten-komprimieren-mit-koepfchen-teil-1-der-huffman-algorithmus-einfach-erklaert","status":"publish","type":"post","link":"https:\/\/ffritze.de\/en\/daten-komprimieren-mit-koepfchen-teil-1-der-huffman-algorithmus-einfach-erklaert\/","title":{"rendered":"Compressing Data with Smarts (Part 1) \u2013 The Huffman Algorithm Explained Simply"},"content":{"rendered":"

Conventional computer codes give each letter the same storage space - the common 'E'<\/strong> consumes as much as the rare 'K'<\/strong>.<\/p>\n\n\n\n

The Huffman algorithm<\/strong> chooses a smarter way: frequent characters get very short codes, rare a little longer. Thus, the amount of data shrinks without any loss of information.<\/p>\n\n\n\n

How to create an elegant Huffman tree<\/strong> from character frequencies step by step, let's look directly at the example word: KAFFEPAUSE<\/strong>.<\/p>\n\n\n\n\n\n\n\n

The classic approach: The block code (fixed length code)<\/h2>\n\n\n\n

With the traditional block code<\/strong>, each character is assigned a binary code of equal length. The creation can be displayed wonderfully as a uniform decision tree:<\/p>\n\n\n\n

    \n
  1. count characters:<\/strong> The word COFFEE BREAK<\/strong> consists of 11 letters, but uses only 7 different characters<\/strong> (K<\/code>, A<\/code>, F<\/code>, E<\/code>, P<\/code>, U<\/code>, S<\/code>).<\/li>\n\n\n\n
  2. Set Bits:<\/strong> To clearly distinguish 7 different characters, we need a 3-bit code (2^3 = 8 combinations). In the graph, this corresponds to a tree with exactly 3 levels.<\/li>\n\n\n\n
  3. Assign Paths:<\/strong> Each branch to the left stands for a 0<\/code>, to the right for a 1<\/code>. Each letter is at the end of an exactly 3 step long path.<\/li>\n<\/ol>\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

    Code table (block code)<\/h3>\n\n\n\n

    Since the tree is exactly 3 levels deep, each character receives a 3-bit code:<\/p>\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

    The coded text for KAFFEEPAUSE<\/h3>\n\n\n\n

    Translated letter by letter:<\/p>\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

    Total binary code:<\/strong>
    000001010010011011100001101110011<\/code><\/p>\n\n\n\n

    Length:<\/strong> 11 letters \u22c5 3 bits = 33 bits<\/strong><\/p>\n\n\n\n

    The problem with this:<\/h3>\n\n\n\n

    Although the E<\/strong> occurs three times and K<\/strong> only once, both consume exactly 3 bits<\/strong>. In addition, the eighth combination (the empty circle at the bottom right) remains completely unused.<\/p>\n\n\n\n

    Some codes may be shorter: The flex code<\/h2>\n\n\n\n

    In the block code, all characters have three digits. Although this is clear, it is not absolutely necessary: As soon as the path 11<\/code> is reached, we already know that only the character 'S' can be meant. The additional branching would therefore be superfluous.<\/p>\n\n\n\n

    \n
    \n

    Therefore, the 'S' in the code tree can move one plane upwards and receives the shorter code 11<\/code>. The remaining characters retain their three-digit codes. This creates a Flexcode<\/strong>: The code words may be of different lengths, but remain unambiguously decipherable, unless there is a letter further down in the tree than another.<\/p>\n<\/div>\n\n\n\n

    \n
    \"Codebaum\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
    \n
    \n
    \"\"\n\t\t\t\n\t\t\t\t\n\t\t\t<\/svg>\n\t\t<\/button><\/figure>\n<\/div>\n\n\n\n
    \n

    For KAFFEEPAUSE<\/strong> this results in:<\/p>\n\n\n\n

    00000101001001101110000110111011<\/code><\/p>\n<\/div>\n<\/div>\n\n\n\n

    The flex code now requires 32 bits<\/strong> instead of 33 bits for the block code. This is only a small difference - but the principle is crucial: not every character has to be given the same amount of space.<\/p>\n\n\n\n

    Why do we need the Huffman algorithm?<\/h2>\n\n\n\n

    We have already seen with the flex code: codes may be of different lengths. In order to save even more storage space, it would make sense in our example to move the frequently occurring 'E'<\/strong> further up in the tree. Finally, it appears three times in the word, while about 'K'<\/strong>, 'P'<\/strong>, 'U'<\/strong> and \u201aS<\/strong>\u201a only occur once each.<\/p>\n\n\n\n

    \n
    \n

    With only seven characters, you can still consider which arrangement could be particularly favorable. However, with longer texts with many different characters, this quickly becomes confusing. There are then a lot of possible code trees - trying out all variants and comparing them with each other would take far too long.<\/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

    This is exactly where the Huffman algorithm<\/strong> helps: It systematically creates a space-saving, clearly readable code tree from the frequencies of the characters. Frequent characters end up as high as possible in the tree and receive short codes; rare characters get longer codes.<\/p>\n\n\n\n

    Frequency analysis<\/h3>\n\n\n\n

    For the word 'KAFFEEPAUSE'<\/strong>, it is first determined how often each letter occurs: 'E' <\/strong>appears three times, 'A'<\/strong> and 'F'<\/strong> twice each, 'K<\/strong>', 'P'<\/strong>, 'U'<\/strong> and 'S'<\/strong> once each. These frequencies form the basis for the Huffman tree.<\/p>\n\n\n\n

    Explanation of the procedure<\/h3>\n\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\n\n\n
    \n

    First, the knots are arranged according to their frequency or weight.<\/p>\n<\/div>\n<\/div>\n\n\n\n

    \n
    \n

    In the next step, the two nodes with the lowest frequencies are always selected and connected to a new node. The frequencies of the two nodes are added. First, for example, K<\/strong> and P<\/strong> are combined:<\/p>\n\n\n\n

    1+1=2<\/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

    Thus, a new node with the frequency 2 arises from the two individual nodes.<\/p>\n\n\n\n

    Subsequently, the two remaining characters are connected with the frequency 1, i.e. U<\/strong> and S<\/strong>:<\/p>\n\n\n\n

    1+1=2<\/p>\n\n\n\n

    Now there are no single nodes with the frequency 1. What remains are four nodes with the frequency 2 \u2013 the subtrees KP<\/strong>, US<\/strong> and the individual characters A<\/strong> and F<\/strong> \u2013 and the node E<\/strong> with the frequency 3.<\/p>\n\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\n\n\n
    \n

    Now the two smallest nodes are selected again. The subtrees KP<\/strong> and US<\/strong> are connected:<\/p>\n\n\n\n

    2+2=4<\/p>\n<\/div>\n<\/div>\n\n\n\n

    This creates a larger subtree with the frequency of 4. After that, A<\/strong> and F<\/strong> are combined:<\/p>\n\n\n\n

    2+2=4<\/p>\n\n\n\n

    \n
    \n

    The frequencies 3, 4 and 4 are now available. The two smallest nodes are E<\/strong> with 3 and one of the two 4 nodes. In the construction shown, E<\/strong> and the subtree AF<\/strong> are connected:<\/p>\n\n\n\n

    3+4=7<\/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
    \n
    \n

    Finally, the two remaining subtrees are merged with the frequencies 4 and 7:<\/p>\n\n\n\n

    4+7=11<\/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

    This means that the Huffman tree is complete. The number 11<\/strong> at the root corresponds to the total number of all characters in the word.<\/p>\n\n\n\n

    How the codes are created<\/h3>\n\n\n\n

    Subsequently, each edge of the tree is assigned a binary digit, for example the 0 on the left and the 1 on the right. The code of a character results from the path from the root to its leaf.<\/p>\n\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\n\n\n
    \n

    Frequent characters are as high as possible in the tree and receive short codes. Rare characters are further down and receive longer codes. For the example shown, this means that E<\/strong> with the frequency 3 receives a shorter code than the only once occurring characters K<\/strong>, P<\/strong>, U<\/strong> and S<\/strong>.<\/p>\n<\/div>\n<\/div>\n\n\n\n

    At equal frequencies, there are several equivalent possibilities for which nodes are connected to each other. Therefore, different Huffman trees can arise. It is crucial that in each step the two nodes are combined with the smallest frequencies.<\/p>\n\n\n\n

    Code board for \"KAFFEEPAUSE\"<\/h3>\n\n\n\n

    The codes are read from the Huffman tree: The path from the root to a character corresponds to its code.<\/strong> Each edge is labeled with a 0<\/strong> or 1<\/strong>.<\/p>\n\n\n\n

    \n
    \n

    Example of E<\/strong>:<\/p>\n\n\n\n

    Root<\/mtext>\u2192<\/mo>7<\/mn>\u2192<\/mo>E<\/mi><\/mo>11<\/mn><\/mn><\/mrow>\\text{root} \\rightarrow 7 \\rightarrow E = \\mathbf{11}<\/annotation><\/semantics><\/math><\/div>\n\n\n\n

    The codes of the individual characters may look different depending on the inscription of the branches. <\/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

    It is important that each path is unambiguous and that frequent characters receive as short codes as possible.<\/p>\n\n\n\n

    With code board, the word KAFFEPAUSE<\/strong> is encoded as follows:<\/p>\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

    The complete bit sequence is:<\/p>\n\n\n\n

    000<\/mn> <\/mtext>100<\/mn> <\/mtext>101<\/mn> <\/mtext>101<\/mn> <\/mtext>11<\/mn> <\/mtext>11<\/mn> <\/mtext>001<\/mn> <\/mtext>100<\/mn> <\/mtext>010<\/mn> <\/mtext>011<\/mn> <\/mtext>11<\/mn><\/mrow>000\\ 100\\ 101\\ 101\\ 11\\ 11\\ 001\\ 100\\ 010\\ 011\\ 11<\/annotation><\/semantics><\/math><\/div>\n\n\n\n

    Without separators, the result is:<\/p>\n\n\n\n

    0001001011011111001100010001001111<\/mn>0001001011011111001100010001001111<\/annotation><\/semantics><\/math><\/div>\n\n\n\n

    For control: The individual codes must be read by the Huffman tree during decoding, as the code words are different in lengths.<\/p>\n\n\n\n

    Final conclusion<\/h3>\n\n\n\n

    The Huffman algorithm shows how data can be displayed in a space-saving manner by a clever arrangement of codes of different lengths.<\/p>\n\n\n\n

    \n
    \n

    Common characters such as E<\/strong> receive short codes, while rare characters receive longer codes. For the word KAFFEEPAUSE<\/strong> a Huffman tree is built step by step from the determined frequencies.<\/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

    If you then read the path from the root to each character, a unique code is created for each character. In this way, the word can be encoded without loss of information and decoded again later. The Huffman algorithm thus combines frequency analysis, tree structure and efficient data compression<\/strong>.<\/p>","protected":false},"excerpt":{"rendered":"

    Herk\u00f6mmliche Computercodes geben jedem Buchstaben starr denselben Speicherplatz \u2013 das h\u00e4ufige ‚E‘ verbraucht genauso viel wie das seltene ‚K‘. Der Huffman-Algorithmus w\u00e4hlt einen clevereren Weg: H\u00e4ufige Zeichen bekommen sehr kurze Codes, seltene etwas l\u00e4ngere. So schrumpft die Datenmenge ohne jeden Informationsverlust. Wie aus Zeichenh\u00e4ufigkeiten Schritt f\u00fcr Schritt ein eleganter Huffman-Baum entsteht, schauen wir uns direkt am Beispielwort an: KAFFEEPAUSE.<\/p>","protected":false},"author":2,"featured_media":1313,"comment_status":"open","ping_status":"open","sticky":false,"template":"seite-thoughts-beitrag","format":"standard","meta":{"footnotes":""},"categories":[19],"tags":[89,88],"class_list":["post-1308","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithms","tag-code","tag-huffman"],"_links":{"self":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/posts\/1308","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=1308"}],"version-history":[{"count":0,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/posts\/1308\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/media\/1313"}],"wp:attachment":[{"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/media?parent=1308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/categories?post=1308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ffritze.de\/en\/wp-json\/wp\/v2\/tags?post=1308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}