In this blog post, we’ll explore the basic principles of data compression—which we use every day—and examine how Huffman coding, a leading method of lossless compression, efficiently reduces data size.
How to Store Data in a Smaller Space
In the 21st century, it feels as though we couldn’t survive even a single day without a computer. We can now share photos on social media anytime, anywhere; download songs we want to listen to; and search for and watch videos. Now that we’ve grown accustomed to this convenience, most of us simply fulfill our role as users without fully understanding the underlying principles that make this possible. However, everyone has probably wondered at least once how all the data we see, hear, and exchange can fit into such small devices as computers, laptops, and smartphones. I aim to show that this curiosity can be satisfied through simple principles that anyone can easily understand.
Everyone would agree that the larger the amount of data, the more difficult it is not only to store it efficiently on storage devices but also to transmit it over communication networks. Computer scientists have solved this problem by compressing data. Data compression refers to the technology—or the actual application of that technology—used to efficiently store data in less space than the original while preserving its meaning. We already use data compression frequently. Not only do compression programs such as Alzip, WinZip, and WinRAR reduce file sizes, but files like MP3s and JPEGs are also examples of data compression in use. Even today, lossless compression methods such as Huffman coding are utilized in various compression technologies.
How do lossy and lossless compression differ?
Data compression can be broadly divided into two categories: lossless compression and lossy compression. Lossy compression is a method in which some of the original data is lost after compression, making it impossible to fully restore the data to its original state; it typically compresses data by deleting or simplifying certain parts within a range that does not significantly affect the information a person can see or hear. Multimedia files such as MP3s and JPEGs are prime examples of lossy compression. Lossless compression is a method that compresses data without damaging the original, ensuring that the decompressed data is identical to the original. A well-known example is compression software like Alzip. This compression method is used for critical data where even the slightest corruption would alter its meaning. While there are various data compression methods, this article will take a closer look at Huffman coding, an example of lossless compression.
Huffman coding is a method that assigns codes based on the frequency of characters, using longer codes for less frequent characters and shorter codes for more frequent ones. This method of assigning codes of varying lengths to characters based on their frequency of use is called “variable-length coding.” This approach can also be seen in Morse code, which was used in early telegraph communications. In Morse code, “E” is represented by a single short pulse (·), and “T” is represented by a single long pulse (-). Less common characters, such as “Q” or “Z,” are represented by up to four “·” and “–” symbols. Since “T” and “E” appear much more frequently than “Q” and “Z” in English sentences, the more frequent characters are represented using fewer symbols. Isn’t this a truly simple yet brilliant method? Now, let’s take a step-by-step look at how Huffman codes are created.
Character
Code
m000
o001
l010
h011
e100
Creating Huffman Codes Based on Character Frequency
First, let’s encode the sentence “hello mom” as a simple example. To simplify the explanation, we’ll omit spaces and assign codes only to the characters. First, to assign unique codes to five characters without overlap, we need at least three digits per character. This is because a two-digit binary number can represent only four digits. If we represent the five digits from 0 to 4 in binary and assign a code to each character, we get the result shown in the table above. Using standard encoding, the given sentence can be encoded as 011100010010001000001000, requiring a total of 24 digits.
So, what about using Huffman coding? As mentioned earlier, Huffman coding creates codes based on the frequency of characters. Before creating the code, the first step is to determine how often each character appears and what percentage of the total characters it accounts for. Looking at the sentence, we can see that among the eight characters in “hello mom,” l, m, and o appear twice each, while e and h appear once each. After determining the frequency of all characters that appear in this way, we select the two characters with the lowest frequencies and combine their frequencies. In this case, those two characters are h and e, and their combined frequency is 2/8. Now, treat the newly created h+e(2/8) as a single character, and repeat this process until all characters are combined into one. In the next step, l(2/8) and h+e(2/8) are combined to form l+h+e(4/8). There is no need to worry if there are multiple 2/8 segments remaining at this point. Since they all appear with the same frequency, it does not matter which character’s code is longer or shorter. Once this process is complete, a tree-like structure is formed. Let’s think of each character as a leaf on this tree. If we arbitrarily assign a “1” to one branch and a “0” to the other each time the tree branches, the process of creating the code is complete. The code for a character is the sum of all the numbers attached to the branching paths from the very top of the tree down to that character. For example, since “h” follows the branch path 1→1→0, the code for “h” is 110. If we find the code for every character in this way, we end up with unique codes for each character, and the results are as follows. Huffman coding is a method that actually uses the frequency of symbols appearing in the data to assign shorter bit sequences to symbols that appear more frequently.
Character
Frequency
Huffman Code
m200
o201
l210
h1110
e1111
Why is it possible to use shorter codes?
Using the completed Huffman codes, the given sentence is transformed into 110111101001000100; since it can be represented using a total of 18 digits, this reduces the number of digits by 6 compared to using standard codes. In other words, the number of digits is reduced from 24 to 18, making the code 75% the size of the original and saving 25% of the space. In this way, by assigning codes of different lengths to each character based on its frequency of occurrence, we can reduce the total number of bits required for the data.
Finally, let’s verify whether creating codes this way actually reduces the amount of information without any significant issues.
For this method to work without issues, one code must not be a prefix of another code—a property known as prefix property. The process of converting a compressed document back to its original content is called decoding. If, during decoding, one code could be a prefix of another without knowing the exact length of the codes representing each character, problems could arise. For example, suppose “e” is represented as “01” and “f” is represented as “010.” In that case, during the decoding process, as soon as “010” is encountered, it becomes difficult to decide whether to interpret “01” as “e” or “010” as “f.” Fortunately, Huffman coding satisfies this prefix property. For a shorter code to overlap with the beginning of another code, a code must be assigned while the tree is branching; however, in Huffman coding, all characters assigned codes correspond to leaves. Therefore, the code for one character is never included in the beginning of another character’s code, and even if the codes are read in order from the beginning, it is possible to distinguish which character each code represents.
Understanding the Principles of Data Compression
By now, you’ve gained a basic understanding of data compression and, in particular, learned about Huffman coding in detail. Even with just this much knowledge, you’ve become a user on a completely different level compared to when you used compression without understanding its principles at all. You might even find yourself saying, “Short codes mean they appear frequently!” when you see a scene in a movie where the protagonist uses Morse code. I hope that in the future, whenever you have questions, rather than just brushing them off, you’ll take the time to learn and understand these simple principles one by one.
