Question

The basic intuition behind Huffman’s algorithm, that frequent blocks should have short encodings and infrequent blocks should have long encodings, is also at work in English, where typical words like I, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer.

However, words like fire!, help!, and run! are short not because they are frequent, but perhaps because time is precious in situations where they are used.

To make things theoretical, suppose we have a file composed of m different words, with frequencies ${\mathbf{f}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{f}}_{\mathbf{m}}$. Suppose also that for the ${\mathbf{i}}_{\mathbf{th}}$word, the cost per bit of encoding is ${\mathbf{c}}_{\mathbf{i}}$. Thus, if we find a prefix-free code where the ${\mathbf{i}}_{\mathbf{th}}$word has a codeword of length ${\mathbf{I}}_{\mathbf{i}}$, then the total cost of the encoding will be localid="1659078764835" $\mathbf{\sum }_{}{\mathbf{f}}_{\mathbf{i}}\mathbf{·}{\mathbf{c}}_{\mathbf{i}}\mathbf{·}{\mathbf{l}}_{\mathbf{i}}$.

Show how to modify Huffman’s algorithm to find the prefix-free encoding of minimum total cost.

Short answer

Combine the two trees with a short spectral region until you reach the root node. Then, with each character, verify the tree as well as traverse it to create the code word.

Step-by-step solution

Step 1: Minimum total cost of prefix-free encoding

Let's say we have a file containing "m" distinct terms and their accompanying frequency distributions. ${\mathrm{f}}_1,{\mathrm{f}}_2,...{\mathrm{f}}_{\mathrm{m}}$and cost per bit for “${\mathrm{i}}_{\mathrm{th}}$” word is denoted as.

Step 2: Cost of prefix-free encoding

Huffman’s algorithm to find the cost of prefix-free encoding is given below:

$cost={\sum }_{i=1}^m{f}_i\cdot l_i$

Where,

“${\mathrm{f}}_1$” denotes as frequency distribution of the “${\mathrm{i}}_{\mathrm{th}}$” word.

“${\mathrm{I}}_{\mathrm{i}}$” denotes as length of the “${\mathrm{i}}_{\mathrm{th}}$” word.

The cost of prefix-free encoding can also be represented as,

$cost={\sum }_{i=1}^m{f}_i\cdot l_i$

Where,

“${\mathrm{f}}_{\mathrm{i}}.{\mathrm{c}}_{\mathrm{i}}$” denotes as frequency of the “${\mathrm{i}}_{\mathrm{th}}$” word.

“$I_i$” denotes as length of the “${\mathrm{i}}_{\mathrm{th}}$” word.

Step 3: Minimum cost of prefix-free encoding

Here, Huffman developed a greedy algorithm to solve this problem and produces the minimum cost prefix code. The generated code is called as Huffman encoding.

Huffman encoding is an easy method.

• Each tree contains only one node, which corresponds to each letter.

• Join the pair of tree with the small range of frequency until to get the root node.

• Then, check the tree for each character and traverse the tree to write the code word.

o Here, “0” bit for left side traversal of tree.

o “1” bit for right side traversal of tree.

Note that the depth of the leaf in “${\mathrm{i}}_{\mathrm{th}}$” word in a tree “${\mathrm{d}}_{\mathrm{i}}$” is equal to the length of the “${\mathrm{i}}_{\mathrm{th}}$” word “${\mathrm{I}}_{\mathrm{i}}$” with that leaf.

Then, the minimum cost of prefix-free encoding can also be represented as,

$\mathrm{cost}={\sum }_{\mathrm{i}=1}^{\mathrm{m}}{\mathrm{f}}_{\mathrm{i}}\cdot {\mathrm{d}}_{\mathrm{i}}$

Where,

“localid="1658922807296" ${\mathrm{f}}_{\mathrm{i}}$” denotes as frequency distribution of the“localid="1658922791600" ${\mathrm{i}}_{\mathrm{th}}$” word.

“localid="1658922833155" ${\mathrm{d}}_{\mathrm{i}}$” denotes as depth of the“localid="1658922841716" ${\mathrm{i}}_{\mathrm{th}}$” word.

Therefore, the Huffman encoding is considered as the minimum cost of prefix-free encoding.

For example:

Construction of the Huffman encoding tree:

Inputs are,

• Character A with frequency of 31%, character C with frequency of 20%, character G with frequency of 9%, and character T with frequency of 40%.

• Huffman encoding is shown below and frequencies are shown in square brackets.

From the Huffman encoding tree,

• Traverse the tree for character “A” from the root node is, 01 .

• Traverse the tree for character “C” from the root node is, 000 .

• Traverse the tree for character “G” from the root node is, 001 .

• Traverse the tree for character “T” from the root node is, 1 .

Hence, the Huffman encoding table is shown below: