Scribd
Upload
145 views13 pages

Lect34 Huffman Coding

The document discusses the Huffman algorithm. It begins by explaining that the Huffman algorithm was created in 1951 by David Huffman. It assigns values to nodes in a tree structure, with the lowest values forming leaves and higher values forming parents of the nodes below. This allows it to construct an optimal prefix code for the characters by minimizing the expected codeword lengths. Examples are given to illustrate how it assigns codes and improves on fixed length encoding. Assignments related to implementing the algorithm are also mentioned.

Uploaded by

jai singhal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
145 views13 pages

Lect34 Huffman Coding

The document discusses the Huffman algorithm. It begins by explaining that the Huffman algorithm was created in 1951 by David Huffman. It assigns values to nodes in a tree structure, with the lowest values forming leaves and higher values forming parents of the nodes below. This allows it to construct an optimal prefix code for the characters by minimizing the expected codeword lengths. Examples are given to illustrate how it assigns codes and improves on fixed length encoding. Assignments related to implementing the algorithm are also mentioned.

Uploaded by

jai singhal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1

Extended binary trees


Huffman Algorithm
Lecture 34

Dr. Poonam Rani


Assistant professor
Computer Science and Engineering
NSUT

Huffman Algorithm 6/29/21


Huffman Algorithm

•  1951, David Huffman


•  In Huffman Algorithm, a set of nodes assigned with values if fed to the
algorithm.
•  Initially 2 nodes are considered and their sum forms their parent node.

•  When a new element is considered, it can be added to the tree.

•  Its value and the previously calculated sum of the tree are used to form the
new node which in turn becomes their parent.

6/29/21 Huffman 2
Algorithm
Introduction
character frequencies
E 10 ①  8 bit Ascii coding –
T 7
Number of bits required (nb)
O 5
A 3 nb= 10x8+7x8+5x8+3x8 = 200bits

Character frequencies code


A 3 00
②  Fixed encoding
O 5 01
T 7 10
nb=3*2+5*2+7*2+10*2
E 10 11 =06+10+14+20 =50bits

6/29/21 Huffman 3
Algorithm
Character frequencies
A 3
O 5
T 7
* 8
E 10
* 15

6/29/21 Huffman 4
Algorithm
Character frequencies code
A 3 110
O 5 111
T 7 10
E 10 0

③  Using Huffman algorithm


nb=3*3+5*3+7*2+10*1
=09+15+14+10 =48bits
i.e
(50-48)/50*100%=4%
6/29/21 Huffman 5
Algorithm
Example –
Q - Create huffman coding for following
A B B C D B C C D A A B B E E E B E A B

6/29/21 Huffman 6
Algorithm
A B B C D B C C D A A B B E E E B E A B
Character frequency Code
20 D 2 100
0
1
C 3 101
8 12 E 4 00
0 1 0 1 A 4 01
4 4 5 7 B 7 11

E A 0 1 B
Nb= (2x3 + 3x3 + 4x2 + 4x2 + 7x2)
2 3 = 6+9+8+8+14
D C = 45 bits
Transmitted code –
011111101100111011011000101……………………….
****** No code is prefix of other
6/29/21 Huffman 7
Algorithm

Huffman Algorithm
Assignment 1
Value Frequencies
1 5
2 7
3 10
4 15
5 20
6 45

6/29/21 Huffman 8
Algorithm
Huffman Algorithm
Assignment2
Value C D E K L M U Z
Frequency 32 42 120 7 42 24 37 2

6/29/21 Huffman 9
Algorithm
Huffman Algorithm
•  Find code for
•  DEED
•  MUCK

•  Try to decode the bit string


1011001110111101

6/29/21 Huffman 10
Algorithm
Assignments
•  Slides at myblog
[Link]
structure-and-algorithm/

•  Assignments at github
[Link]
signments/assignment_7

6/29/21 Huffman 11
Algorithm
Reference
•  [Link]
eg/mpegfaq/huffman_tutorial.html
•  [Link]
•  [Link]
•  [Link]
•  [Link]
•  [Link]
_structure.htm

6/29/21 Huffman 12
Algorithm
Doubts???

6/29/21 Huffman 13
Algorithm

You might also like