How is the frequency table created for Huffman coding?

In Huffman coding, a frequency table is a type of data structure that stores the frequencies of characters (or symbols) present in the input data. It is used as a reference to determine the frequency of each character and construct the Huffman tree, which is the basis for generating variable-length codes for each character.

The frequency table typically associates each character with its corresponding frequency or occurrence count in the input data. The frequency of a character represents how often it appears in the data. The table can be implemented using various data structures such as an array, dictionary, or any other suitable data structure depending on the programming language and requirements.

In the following explanation on how to build a frequency table, we will use an example as well to better understand the concept.

Steps to create a frequency table

• Input: Take the input data for which you want to create the frequency table. This data can be in the form of a string, file, or any other source.
• Count the character frequency: Traverse through the input data and count the frequency of each character present. Record the count of each character in a frequency table or dictionary, where the characters are the keys and their frequencies are the values.
• Sort by frequency: Sort the frequency table based on the character frequencies in ascending order. This step ensures that the characters with the lowest frequencies will be at the top.
• Build a Huffman tree: Starting from the sorted frequency table, build a Huffman tree using the Huffman algorithm. The tree construction involves merging the two characters with the lowest frequencies into a single node, repeatedly, until all characters are merged into a single root node.
• Assign binary codes: Traverse the Huffman tree to assign binary codes to each character. The binary code assigned to each character is determined by the path from the root node to that character in the tree. Assign ‘0’ for each left branch and ‘1’ for each right branch. The resulting binary codes form the Huffman codes for the characters.
• Create a frequency table: Finally, create a frequency table that maps each character to its corresponding Huffman code. This table will be used during encoding and decoding processes.

Example problem

Let’s suppose we have an input string.

Input string: "ABRACADABRA"

1. The first step is character frequency count and the creation of a frequency table.

   Character frequency count:

• $A$ occurs 5 times.

• $B$ occurs 2 times.

• $R$ occurs 2 times.

• $C$ occurs 1 time.

• $D$ occurs 1 time.

  Frequency table:

• $A$: 5

• $B$: 2

• $R$: 2

• $C$: 1

• $D$: 1

2. The second step is to sort these by their frequencies.

• $C$: 1
• $D$: 1
• $B$: 2
• $R$: 2
• $A$: 5

3. The third step is to build the Huffman tree. Its methodology is as follows.

• Start merging the characters with the lowest frequencies.
• Merge $C$ and $D$ to create a subtree with frequency 2.
• Merge the subtree with frequency 2 and $B$ to create a subtree with frequency 4.
• Merge the subtrees with frequency 4 and $R$ to create a subtree with frequency 6.
• Merge the subtree with frequency 6 and $A$ to create the root node with frequency 11.

4. In the fourth step, we assign binary codes to each character. The following illustration will help us assign codes to each alphabet in our case.

Following are the binary codes assigned through the huffman tree that was designed.

• $A$: 0
• $R$: 10
• $B$: 110
• $C$: 1110
• $D$: 1111

This completes the process of making a frequency table for Huffman coding.