In 1952, David Huffman published a paper called “A Method for the Construction of Minimum-RedundancyCodes”. It was a seminal paper. Given a text of characters where each character occurs with a frequencygreater than 0, Huffman found a way to encode each character as a unique sequence of 0’s and 1’s suchthat the overall length (number of bits) of the encoded text was minimized.Huffman recognized that characters with a greater frequency should have shorter codes than those witha lower frequency. Therefore, to disambiguate two codes, no shorter code of 0’s and 1’s can serve as theprefix (beginning) of a longer code. For example, if letter ‘a’ has a code of 010, no other character canhave a code that begins with 010.To find these codes, a Huffman tree is constructed. The Huffman tree is a binary tree where the left edgeof each node is associated with the number 0 and the right edge is associated with the number 1. Allcharacters are stored as leaf nodes and the code associated with each character is the sequence of 0’sand 1’s along the path from the root to the character.RequirementsAs a start, read up on Huffman Codes in your text. Then, implement the Huffman class which tackles eachof the following tasks.Task 1: Determine the Character FrequenciesDetermine the frequency of each character in the given text and store it in an array using the characteritself to map to an index. Assume all printable ASCII characters, codes 32 to 126, may be used as part ofthe text (see AnalyzeText).Task 2: Build the Huffman TreeUsing a priority queue of binary trees, a Huffman tree is constructed for the given text. Initially, thepriority queue is populated with as many as 95 individual nodes (binary trees of size 1) where each nodestores a character and its frequency. The priority queue is ordered by frequency where a binary tree witha lower total frequency has a higher priority than one with a higher total frequency (see Build).Task 3: Create the CodesThe final Huffman tree is then traversed in a prefix manner such that the code for each character is storedas a string of 0s and 1s and placed in an instance of the C# Dictionary class using its associated characteras the key (see CreateCodes) and the string as the value.Task 4: EncodeUsing the dictionary of codes, a given text is converted into a string of 0s and 1s (see Encode).Task 5: DecodeUsing the Huffman tree, a given string of 0s and 1s to converted back into the original text (see Decode).Page 5 of 7To help implement your program, consider the following skeleton of code.class Node : IComparable{public char Character { get; set; }public int Frequency { get; set; }public Node Left { get; set; }public Node Right { get; set; }public Node (char character, int frequency, Node left, Node right) { … }// 2 markspublic int CompareTo ( Object obj ) { … }}class Huffman{private Node HT; // Huffman tree to create codes and decode textprivate Dictionary<char,string> D; // Dictionary to store the codes for each character// Constructor// Invokes AnalyzeText, Build and CreateCodespublic Huffman ( string S ) { … }// 4 marks// Return the frequency of each character in the given textprivate int[ ] AnalyzeText ( string S ) { … }// 10 marks// Build a Huffman tree based on the character frequencies greater than 0private void Build ( int[ ] F ) { PriorityQueue<Node> PQ; … }// 8 marks// Create the code of 0s and 1s for each character by traversing the Huffman tree// Store the codes in Dictionary D using the char as the keyprivate void CreateCodes ( ) { … }// 4 marks// Encode the given text and return a string of 0s and 1spublic string Encode ( string S ) { … }// 6 marks// Decode the given string of 0s and 1s and return the original textpublic string Decode ( string S ) { … }
In 1952, David Huffman published a paper called “A Method for the Construction of Minimum-Redundancy
Codes”. It was a seminal paper. Given a text of characters where each character occurs with a frequency
greater than 0, Huffman found a way to encode each character as a unique sequence of 0’s and 1’s such
that the overall length (number of bits) of the encoded text was minimized.
Huffman recognized that characters with a greater frequency should have shorter codes than those with
a lower frequency. Therefore, to disambiguate two codes, no shorter code of 0’s and 1’s can serve as the
prefix (beginning) of a longer code. For example, if letter ‘a’ has a code of 010, no other character can
have a code that begins with 010.
To find these codes, a Huffman tree is constructed. The Huffman tree is a binary tree where the left edge
of each node is associated with the number 0 and the right edge is associated with the number 1. All
characters are stored as leaf nodes and the code associated with each character is the sequence of 0’s
and 1’s along the path from the root to the character.
Requirements
As a start, read up on Huffman Codes in your text. Then, implement the Huffman class which tackles each
of the following tasks.
Task 1: Determine the Character Frequencies
Determine the frequency of each character in the given text and store it in an array using the character
itself to map to an index. Assume all printable ASCII characters, codes 32 to 126, may be used as part of
the text (see AnalyzeText).
Task 2: Build the Huffman Tree
Using a priority queue of binary trees, a Huffman tree is constructed for the given text. Initially, the
priority queue is populated with as many as 95 individual nodes (binary trees of size 1) where each node
stores a character and its frequency. The priority queue is ordered by frequency where a binary tree with
a lower total frequency has a higher priority than one with a higher total frequency (see Build).
Task 3: Create the Codes
The final Huffman tree is then traversed in a prefix manner such that the code for each character is stored
as a string of 0s and 1s and placed in an instance of the C# Dictionary class using its associated character
as the key (see CreateCodes) and the string as the value.
Task 4: Encode
Using the dictionary of codes, a given text is converted into a string of 0s and 1s (see Encode).
Task 5: Decode
Using the Huffman tree, a given string of 0s and 1s to converted back into the original text (see Decode).
Page 5 of 7
To help implement your program, consider the following skeleton of code.
class Node : IComparable
{
public char Character { get; set; }
public int Frequency { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node (char character, int frequency, Node left, Node right) { … }
// 2 marks
public int CompareTo ( Object obj ) { … }
}
class Huffman
{
private Node HT; // Huffman tree to create codes and decode text
private Dictionary<char,string> D; // Dictionary to store the codes for each character
// Constructor
// Invokes AnalyzeText, Build and CreateCodes
public Huffman ( string S ) { … }
// 4 marks
// Return the frequency of each character in the given text
private int[ ] AnalyzeText ( string S ) { … }
// 10 marks
// Build a Huffman tree based on the character frequencies greater than 0
private void Build ( int[ ] F ) { PriorityQueue<Node> PQ; … }
// 8 marks
// Create the code of 0s and 1s for each character by traversing the Huffman tree
// Store the codes in Dictionary D using the char as the key
private void CreateCodes ( ) { … }
// 4 marks
// Encode the given text and return a string of 0s and 1s
public string Encode ( string S ) { … }
// 6 marks
// Decode the given string of 0s and 1s and return the original text
public string Decode ( string S ) { … }
Step by step
Solved in 2 steps
