Huffman Encoding data structure assignment solution

Huffman encoding is computer algorithm used for data compression.

History:

               This algorithm is devised by David A. Huffman in 1951.

Working:

                  This algorithm is based on creating a binary tree of nodes.

1. First of all we count the frequency of the letters appear in the string.
2. We build the tree as the letters coming with higher frequency are at the bottom.
3. Then with higher frequency letters are come.
4. This process ends with a single node “root”.
5. We mark from root to leaf as the left child as “zero” and right child as “one”.
6. So we can calculate Huffman code of each character.
7. Each character has a unique code.

Example:

Consider the following phrase:

Welcome to virtual university

 

Letter	Frequency
NL	1
SP	3
A	1
C	1
E	3
I	3
L	2
M	1
N	1
O	2
R	2
S	1
T	3
U	2
V	2
W	1
Y	1
Total	30

 

 NL used for null character and SP for space.

·         Draw Huffman tree         

                                                                                                   

·         Huffman code for each character        

Letter	code
NL	01010
SP	1010
A	01011
C	01110
E	1000
I	0110
L	0100
M	01111
N	10010
O	1111
R	1110
S	10101
T	00
U	1100
V	1101
W	10110
Y	10111

                                                        

 

·         Encode the above phrase using Huffman codes calculated above

welcome to virtual university

10110 1000 0100 01110 1111 01111 1000 1010 00 1111 1010 1101 0110 1110 00 1100 01011 0100 1010 1100 10010 0110 1101 1000 1110 10101 0110 00 10111 01010

Difference between aggregation and composition:

Composition:

                        Composition is an association in which an object is composed with other smaller objects. This part relationship with whole is called composition.

Composition is stronger relationship because

• Composed object becomes a part of the composer.
• Composed object cannot exist independently.

Representation:

Composition is represented by a line with filled diamond hand towards the composer.

Example:

• A chair’s body is made of up of different parts. They can not exist independently.

• A person is made up of different body parts. They can not exist independent of person.

Aggregation:

In aggregation an object is a collection of other objects, it is a relationship between containers and contained.

Aggregation is weak relationship, because

• Aggregate object is not a part of the container.
• Aggregate object can exist independently.

Representation:

Aggregation is represented by a line with unfilled-diamond head towards the container.

Example:

Relationship between room and its furniture because furniture can be shifted to another room, so can exist independent of a particular room.

Difference between laptop and notebook

 NoteBook

Notebook is similar with laptop but there are differences also. Notebook is light weight with full keyboard. It is perfect for wireless communication and internet access.

1. Notebooks have no internal CD/DVD ROM.
2. No floppy disks.
3. No built in optics.
4. Low power consumption.
5. Minimum graphics subsystem.
6. Smallest possible keyboard.
7. Much thinner than laptop.
8. Provide mobile computing.

Laptop

Laptop is personal computer for mobile use. Laptop has rechargeable battery in it. Laptop has all features that a personal computer can have.

1. High quality graphic system.
2. High resolution TFT screen.
3. Have CD/DVD ROM and floppy drives.
4. 3 to 4 hours battery timing.
5. Upgradeable
6. Integrated wi-fi, Bluetooth, modem, network.
7. Laptops are designed to replace the entire personal computer with all its features.