Scribd
Upload
12 views2 pages

Huffman Coding: Tree Construction Guide

Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequencies. The document outlines the construction of a Huffman tree using given symbols and their frequencies, resulting in optimal prefix codes. The final Huffman codes for the symbols are provided, showing the assigned binary codes based on their traversal paths in the tree.

Uploaded by

harshsarwankar19
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
12 views2 pages

Huffman Coding: Tree Construction Guide

Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequencies. The document outlines the construction of a Huffman tree using given symbols and their frequencies, resulting in optimal prefix codes. The final Huffman codes for the symbols are provided, showing the assigned binary codes based on their traversal paths in the tree.

Uploaded by

harshsarwankar19
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

Huffman Coding - Construction and Code Assignment

1. Definition

Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes

to input characters, with shorter codes assigned to more frequent characters. It results in an optimal

prefix code tree.

2. Given Data

Symbols: p, g, e, r, i

Frequencies: 20, 17, 33, 25, 40

3. Step-by-Step Construction

Step 1: Arrange nodes in increasing order of frequency: g(17), p(20), r(25), e(33), i(40)

Step 2: Combine g(17) + p(20) -> Node A = 37

Step 3: Combine r(25) + e(33) -> Node B = 58

Step 4: Combine A(37) + i(40) -> Node C = 77

Step 5: Combine B(58) + C(77) -> Root = 135

4. Huffman Tree Traversal and Code Assignment

Assign 0 to left branches and 1 to right branches.

i: Path = Right of C -> 1 -> Left -> 10

g: Path = Left of A -> 1100

p: Path = Right of A -> 1101

r: Path = Left of B -> 00

e: Path = Right of B -> 01

5. Final Huffman Codes

Symbol Frequency Huffman Code

i 40 10
g 17 1100

p 20 1101

r 25 00

e 33 01

You might also like