Scribd
Upload
139 views12 pages

Huffman Coding

Huffman coding is a variable-length encoding technique that assigns variable-length codewords to input characters based on their frequencies, with shorter codewords assigned to more frequent characters. It involves constructing a Huffman tree where each leaf node represents a character and the path from the root to the leaf is the codeword. The algorithm starts by assigning each unique character its own tree and then repeatedly combines the two trees with the lowest frequencies until a single tree remains. This results in a prefix-free code where codewords are not prefixes of other codewords, allowing for unambiguous decoding. Huffman coding achieves compression by replacing the original fixed-length character codes with more efficient variable-length codes.

Uploaded by

6 4 8 3 7 JAYAASRI K
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
139 views12 pages

Huffman Coding

Huffman coding is a variable-length encoding technique that assigns variable-length codewords to input characters based on their frequencies, with shorter codewords assigned to more frequent characters. It involves constructing a Huffman tree where each leaf node represents a character and the path from the root to the leaf is the codeword. The algorithm starts by assigning each unique character its own tree and then repeatedly combines the two trees with the lowest frequencies until a single tree remains. This results in a prefix-free code where codewords are not prefixes of other codewords, allowing for unambiguous decoding. Huffman coding achieves compression by replacing the original fixed-length character codes with more efficient variable-length codes.

Uploaded by

6 4 8 3 7 JAYAASRI K
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

Huffman Coding

• Suppose we have to encode a text that comprises symbols from some n-symbol
alphabet by assigning to each of the text’s symbols some sequence of bits called
the codeword.
• For example, we can use a fixed-length encoding that assigns to
each symbol a bit string of the same length m (m ≥ log2 n). This is exactly what
the standard ASCII code does.
• Variable-length encoding, which assigns codewords of different lengths to
different symbols, introduces a problem that fixed-length encoding does not have.
Namely, how can we tell how many bits of an encoded text represent the first (or,
more generally, the ith) symbol? To avoid this complication, we can limit ourselves
to the so-called prefix-free (or simply prefix) codes.
Compression Technique
Message  BCCABBDDAECCBBAEDDCC
LENGTH= 20
ASCII Code binary form
A 65 01000001
B 66 01000010
C 67
D 68
E 69
Total no. of bits for the message= 8x20 = 160 bits
Huffman Coding
• Huffman’s algorithm
Step 1 Initialize n one-node trees and label them with the symbols of the
alphabet given. Record the frequency of each symbol in its tree’s root
to indicate the tree’s weight. (More generally, the weight of a tree will
be equal to the sum of the frequencies in the tree’s leaves.)
Step 2 Repeat the following operation until a single tree is obtained. Find
two trees with the smallest weight (ties can be broken arbitrarily, but
see Problem 2 in this section’s exercises). Make them the left and right
subtree of a new tree and record the sum of their weights in the root
of the new tree as its weight.
A tree constructed by the above algorithm is called a Huffman tree. It
defines—in the manner described above—a Huffman code.
Fixed size Codes
Total no. of bits for the message= 3x20 = 60 bits

Character count frequency Code

A 3 3/20 000

B 5 5/20 001

C 6 6/20 010

D 4 4/20 011

E 2 2/20 100
So for the table,
5x8 bits  characters
5x3 bits  codes

40+15 = 55 bits  table


60 bits  message

Table + message = 60+55 = 115 bits

Reduced 35% to 40%


HUFFMAN CODING
Message  BCCABBDDAECCBBAEDDCC
LENGTH= 20

Character count frequency

A 3 3/20 =.15

B 5 5/20=.25

C 6 6/20=.3

D 4 4/20=.2

E 2 2/20=.1
HUFFMAN CODING
Huffman Coding
Variable size Codes
Total no. of bits for the message= 3x20 = 60 bits

Character count Code

A 3 001

B 5 10

C 6 11

D 4 01

E 2 000
Huffman Coding

So for the table,


5x8 bits  characters
12 bits  codes

40+12 = 52 bits  table


45 bits  message
Table + message = 52+45 = 97 bits

Still reduced. You could also decode.


Huffman Coding – Example 2
Thank you

You might also like