<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Ryan Smith on Medium]]></title>
        <description><![CDATA[Stories by Ryan Smith on Medium]]></description>
        <link>https://medium.com/@ryansmith_62283?source=rss-1a8102b5ca94------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*mcbVzRzvUmxel6j2.</url>
            <title>Stories by Ryan Smith on Medium</title>
            <link>https://medium.com/@ryansmith_62283?source=rss-1a8102b5ca94------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 08:53:04 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ryansmith_62283/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Binary Search Trees, Huffman Codes, and Lossless Compression]]></title>
            <link>https://medium.com/@ryansmith_62283/ill-huff-and-i-ll-puff-and-i-ll-blow-your-text-down-into-fewer-bits-bc7e3a92e439?source=rss-1a8102b5ca94------2</link>
            <guid isPermaLink="false">https://medium.com/p/bc7e3a92e439</guid>
            <category><![CDATA[huffman-codes]]></category>
            <category><![CDATA[prefix-free-codes]]></category>
            <category><![CDATA[prefix-codes]]></category>
            <category><![CDATA[lossless-compression]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Ryan Smith]]></dc:creator>
            <pubDate>Mon, 07 Aug 2017 17:53:15 GMT</pubDate>
            <atom:updated>2017-10-31T16:57:23.627Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>Binary Search Trees, Huffman Codes, and Lossless Compression</strong></p><p><em>Here’s a somewhat mundane (maybe even boring?) question:</em> How does your computer store the character ‘a’?</p><p><em>And here’s an appropriately mundane answer:</em> in most contexts, the characters in a text file, including the letters you are reading right now, are stored as a string of (7 or 8) binary digits, or bits. The ASCII character ‘A’, for instance, is the number 65, stored in binary as 00100001. Meanwhile, ‘B’ is 66, or 00100010.</p><p>Encoding characters into binary in this way has some nice properties. For instance, if I want to send my friend Björn the name of my favorite Swedish disco group, I could simply give him the following binary:</p><p>00100001 00100010 00100010 00010001</p><p>The spaces probably won’t be there when I send this code to Björn. Yet there is no ambiguity over where one letter ends and another begins, because each letter is always exactly 8 bits long. So the first 8 bits represent ‘A’, the next 8 bits are the code for ‘B’, and pretty soon Björn is clued into my passion for europop sensation ABBA.</p><p>This lack of ambiguity is great! We want to hold onto that property in whatever system we use to encode characters as binary. But this system is subpar in other ways. For instance, if I were to send the entire contents of this article to my friend Björn, we’d probably see the character ‘e’ pop up a whole helluva lot more than, say, ‘Q’. And yet, both ‘e’ and ‘Q’ are represented by 8 bits. So what if we tried representing more common characters with shorter binary codes?</p><p>Okay, the letters ‘e’, ‘a’, and ’t’ appear a lot in English! Let’s give them really short code names! We’ll use the following code:</p><p>{‘e’ : 0, ‘a’ : 1, ‘t’ : 01}</p><p>I want to get some ‘tea’ with Björn so I send him:</p><p>0101</p><p>I waited for an hour at the café and Björn never showed. Before getting mad at him, though, I realize that he probably read 0, 1, 01 as ‘eat’ instead of 01, 0, 1 as ‘tea’. Björn is a wonderful (but confused and lonely) friend, and waited two hours for me at a restaurant down the block before leaving.</p><p>So our code words are short, but it’s no longer clear where one character ends and another begins. <em>How can we fix this mess?</em></p><p><strong><em>Computer Science Pioneer David A. Huffman to the rescue!</em></strong></p><p>In his famously concise Sc.D dissertation, Mr. Huffman developed an algorithm that generates a fabulous encoding system. The reason you should care about everything that follows is that <strong>all your favorite compression file formats use this encoding system for lossless data compression! </strong>JPEG, PNG, GZIP, PKZIP, you name it¹. They’re all using Huffman codes. Why, you ask? Because in his dissertation, Huffman proved that his code-generating algorithm produces the <em>most efficient possible prefix-free code for a set of characters</em>.</p><p>Hold up. That sentence is a tad confusing. What do I mean by ‘most efficient possible prefix-free code for a set of characters’? Let’s start with the word code.</p><p><strong>Code. </strong>A code has a set of characters, a set of codewords, and a rule that associates each character with one of the codewords. Each codeword is just a string of binary digits (0s and 1s). Okay, that’s not so bad. Let’s take it up a notch.</p><p><strong>Prefix-free code. </strong>A code where no codeword is a prefix of another codeword. Just to confuse you, prefix-free codes are also commonly referred to as prefix codes. Harken back to our old code {‘e’: 0, ‘a’: 1, ’t’: 01}. <strong>Since the codeword for ’t’ (01) begins with the codeword for ‘e’ (0), this is not a prefix code</strong>. So that’s how we ended up sending poor, unassuming Björn to the wrong place. Prefix codes have that nice property we mentioned earlier — there is no ambiguity over where one character ends and another begins.</p><p>Lets pause to consider an example. The day after our mishap with Björn, we wish to schedule tea with our dear friend Frida. Learning from our mistakes, we change our code to be a <strong>prefix-free code</strong>:</p><p>{‘e’: 0, ‘a’: 10, ’t’: 11}.</p><p>We send Frida:</p><p>11010</p><p>Frida knows the code and starts reading the digits we sent her. First she sees 1, and doesn’t know whether the first character is ‘a’ or ’t’, so she considers the next character as well. When Frida reads the first two digits, 11, she knows that the first character must be ’t’, since no other codeword begins with 11. Frida then reads the next digit, 0. Since ‘e’ is the only character with a codeword beginning with 0, the next character must be ‘e’! Frida moves to the fourth digit, which is a 1. Because she cannot determine whether the last character is an ‘a’ or a ’t’, she continues on to read the next digit too. Finally, Frida sees the last codeword is 10, which represents the character ‘a’. Frida and I are all set for tea!</p><p><strong>Most efficient possible prefix-code. </strong>By most efficient possible, we mean that given the expected frequency of each character in the message, out of all possible prefix-free codes we could produce, Huffman’s algorithm with produce the smallest expected length of an encoded message. We’ll expand on this idea more in my next article.</p><p><em>Enough already! How do I create a Huffman code to compress my messages?</em></p><p>Not so fast. First let’s briefly review my favorite data structure, the <strong>binary tree</strong>! For our purposes, we will say that a binary tree is a data structure that is either:</p><ol><li>A <strong>leaf</strong> object, which stores:</li></ol><p>i. a character (like ‘e’ or ‘Q’), and</p><p>ii. an expected frequency (how often we expect the character to occur in our message)</p><p>— or —</p><p>2. An branch object, which stores:</p><p>i. a cumulative expected frequency (the sum of all the expected frequencies of the leafs below that branch)</p><p>ii. a left sub-tree (itself a binary tree, either a branch or a leaf)</p><p>iii. a right sub-tree (also itself a binary tree)</p><p>Let’s suppose we want to create a Huffman code for the characters ‘a’, ‘b’, and ‘c’. We expect that our messages will be comprised of about 40% ‘a’ characters, 35% ‘b’ characters, and 25% ‘c’ characters. The corresponding binary tree will look something like figure 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b2bH20Ds5AhVb9j13rCYCg.png" /><figcaption>Figure 1</figcaption></figure><p>As described, the green ‘leaf’ nodes store a character we want to use in our code, along with the expected frequency with which they will appear in messages we send. They are terminal nodes in some sense, since they don’t store any sub-trees.</p><p>The brown ‘branch’ nodes, on the other hand, aren’t used to store a character in our code. Rather, they store left and right sub-trees (denoted by the arrows!), and the cumulative expected frequency of all of the characters that are stored in the leaves below it.</p><p>We will use this tree to generate our code. To get the codeword for ‘c’, we start at the top of the tree and travel down towards the node for ‘c’. Each time we move left, we add a 0 to the codeword. Each time we move right, we add a 1 to the code word. To get to ‘c’, we move right once and then left once. Hence our codeword for ‘c’ is 10. Before moving on, refer to Figure 1 and ask yourself:</p><ol><li><em>What is the codeword for b?</em></li><li><em>Can you encode the message ‘cab’?</em></li></ol><p>As we’ve mentioned, only the terminal leaf nodes store characters. <em>Why??? </em>If we stored a character in a branch that had sub-trees, then its codeword would be a prefix of the codewords for characters stored further down the tree! Then we would lose our lovely prefix-free property, so when we send a string of encoded characters, it would no longer be clear where one character ends and another begins. Mayhem. Limiting ourselves to storing characters in the terminal leaf nodes is what ensures the resulting code is prefix-free!</p><p>We’ve seen how we can use a Huffman tree like the one above to create a prefix free code and encode a message, and we know why the characters of the code are stored only in the leaves. But we can also use a Huffman tree to decode a message. Try using the Huffman tree in figure 2 to decode the message: ‘000111110100011111010010011011001’. If you want to take it a step further, try writing a function that accepts a Huffman tree and an encoded message, and decodes the message.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2GDLPr6IQQOKxsPjQtwF-A.png" /><figcaption>Figure 2 —Use this Huffman tree to decode ‘000111110100011111010010011011001’</figcaption></figure><p>By now you should have some experience using Huffman trees to encode and decode messages. But we’re missing one crucial step! How do we take a set of characters with expected frequencies and build a tree from them?</p><p>That about wraps up this intro to Huffman codes — bye bye buddy.</p><p>[1] Some of these file formats, like JPEG, aren’t lossless — but once lossy compression algorithms have done their job, the resulting data is further compressed using Huffman codes.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bc7e3a92e439" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>