Design, analyze and implement the algorithm of computing Huffman code. Step 1 (1
ID: 3760142 • Letter: D
Question
Design, analyze and implement the algorithm of computing Huffman code.
Step 1 (100 points if implementing priority queue Q using a min-heap, :
Input: 26 English characters (your can add some other characters, such as space, “,”, “.”) and their frequencies (the sum of the frequencies is 100).
Output: Huffman codewords of each character.
(1)Build Huffman code tree
(2)In-order transversal the tree to get the codewords
Step 2 (20 points): First encoding, and then, decoding a text file using the Huffman codewords (the output of the Task 1).
Input: a text file consists of the characters in Task 1
Output: Encoded the text file and decoded it back.
•Design the algorithms for Task 1 and Task 2.
• Two data structures have to be used in the algorithm for Task 1. One is a priority queue Q.
Each node in Q is the root of a binary tree which keeps Huffman codewords.
• Analyze the time complexity of each algorithm using O-notation. Note that the time
complexity depends on the implementation of the data structures.
• Implement the algorithms using C#.
• A simple user interface has to be contained. That is, the user can input the set of characters
and their frequencies, and output the Huffman code of each character. Also, they can encode and decode a text file.
Explanation / Answer
using System;
public static class GlobalMembers
{
public static node[] heap = new node[1000000];
public static int heapSize;
/*Initialize Heap*/
public static void Init()
{
heapSize = 0;
heap[0] = (node)malloc(sizeof(node));
heap[0].freq = -INT_MAX;
}
/*Insert an element into the heap */
public static void Insert(node element)
{
heapSize++;
heap[heapSize] = element; //Insert in the last place
/*Adjust its position*/
int now = heapSize;
while (heap[now / 2].freq > element.freq)
{
heap[now] = heap[now / 2];
now /= 2;
}
heap[now] = element;
}
public static node DeleteMin()
{
node minElement;
node lastElement;
int child;
int now;
minElement = heap[1];
lastElement = heap[heapSize--];
/* now refers to the index at which we are now */
for (now = 1; now * 2 <= heapSize ;now = child)
{
child = now * 2;
if (child != heapSize && heap[child + 1].freq < heap[child].freq)
{
child++;
}
if (lastElement.freq > heap[child].freq)
{
heap[now] = heap[child];
}
else // It fits there
{
break;
}
}
heap[now] = lastElement;
return minElement;
}
public static void print(node temp, ref string code)
{
if (temp.left == null && temp.right == null)
{
Console.Write("char {0} code {1} ",temp.ch,code);
return;
}
int length = code.Length;
string leftcode = new string(new char[512]);
string rightcode = new string(new char[512]);
leftcode = code;
rightcode = code;
leftcode = StringFunctions.ChangeCharacter(leftcode, length, '0');
leftcode = StringFunctions.ChangeCharacter(leftcode, length + 1, '');
rightcode = StringFunctions.ChangeCharacter(rightcode, length, '1');
rightcode = StringFunctions.ChangeCharacter(rightcode, length + 1, '');
print(temp.left, ref leftcode);
print(temp.right, ref rightcode);
}
static int Main()
{
Init();
int distinct_char;
string tempVar = ConsoleInput.ScanfRead();
if (tempVar != null)
{
distinct_char = int.Parse(tempVar);
}
sbyte ch;
int freq;
int iter;
for (iter = 0;iter < distinct_char;iter++)
{
string t = new string(new char[4]);
string tempVar2 = ConsoleInput.ScanfRead();
if (tempVar2 != null)
{
t = sbyte.Parse(tempVar2);
}
ch = t[0];
string tempVar3 = ConsoleInput.ScanfRead();
if (tempVar3 != null)
{
freq = int.Parse(tempVar3);
}
node temp = (node) malloc(sizeof(node));
temp.ch = ch;
temp.freq = freq;
temp.left = temp.right = null;
Insert(temp);
}
/* Special Case */
if (distinct_char == 1)
{
Console.Write("char {0} code 0 ",ch);
return 0;
}
for (iter = 0;iter < distinct_char - 1 ;iter++)
{
node left = DeleteMin();
node right = DeleteMin();
node temp = (node) malloc(sizeof(node));
temp.ch = 0;
temp.left = left;
temp.right = right;
temp.freq = left.freq + right.freq;
Insert(temp);
}
node tree = DeleteMin();
string code = new string(new char[512]);
code = StringFunctions.ChangeCharacter(code, 0, '');
print(tree, ref code);
}
}
public class node
{
public sbyte ch;
public int freq;
public node left;
public node right;
}
internal static class StringFunctions
{
internal static string ChangeCharacter(string sourceString, int charIndex, char changeChar)
{
return (charIndex > 0 ? sourceString.Substring(0, charIndex) : "")
+ changeChar.ToString() + (charIndex < sourceString.Length - 1 ? sourceString.Substring(charIndex + 1) : "");
}
internal static bool IsXDigit(char character)
{
if (char.IsDigit(character))
return true;
else if ("ABCDEFabcdef".IndexOf(character) > -1)
return true;
else
return false;
}
internal static string StrChr(string stringToSearch, char charToFind)
{
int index = stringToSearch.IndexOf(charToFind);
if (index > -1)
return stringToSearch.Substring(index);
else
return null;
}
internal static string StrRChr(string stringToSearch, char charToFind)
{
int index = stringToSearch.LastIndexOf(charToFind);
if (index > -1)
return stringToSearch.Substring(index);
else
return null;
}
internal static string StrStr(string stringToSearch, string stringToFind)
{
int index = stringToSearch.IndexOf(stringToFind);
if (index > -1)
return stringToSearch.Substring(index);
else
return null;
}
private static string activeString;
private static int activePosition;
internal static string StrTok(string stringToTokenize, string delimiters)
{
if (stringToTokenize != null)
{
activeString = stringToTokenize;
activePosition = -1;
}
//the stringToTokenize was never set:
if (activeString == null)
return null;
//all tokens have already been extracted:
if (activePosition == activeString.Length)
return null;
//bypass delimiters:
activePosition++;
while (activePosition < activeString.Length && delimiters.IndexOf(activeString[activePosition]) > -1)
{
activePosition++;
}
//only delimiters were left, so return null:
if (activePosition == activeString.Length)
return null;
//get starting position of string to return:
int startingPosition = activePosition;
do
{
activePosition++;
} while (activePosition < activeString.Length && delimiters.IndexOf(activeString[activePosition]) == -1);
return activeString.Substring(startingPosition, activePosition - startingPosition);
}
}
internal static class ConsoleInput
{
private static bool goodLastRead = false;
internal static bool LastReadWasGood
{
get
{
return goodLastRead;
}
}
internal static string ReadToWhiteSpace(bool skipLeadingWhiteSpace)
{
string input = "";
char nextChar;
while (char.IsWhiteSpace(nextChar = (char)System.Console.Read()))
{
//accumulate leading white space if skipLeadingWhiteSpace is false:
if (!skipLeadingWhiteSpace)
input += nextChar;
}
//the first non white space character:
input += nextChar;
//accumulate characters until white space is reached:
while (!char.IsWhiteSpace(nextChar = (char)System.Console.Read()))
{
input += nextChar;
}
goodLastRead = input.Length > 0;
return input;
}
internal static string ScanfRead(string unwantedSequence = null, int maxFieldLength = -1)
{
string input = "";
char nextChar;
if (unwantedSequence != null)
{
nextChar = '';
for (int charIndex = 0; charIndex < unwantedSequence.Length; charIndex++)
{
if (char.IsWhiteSpace(unwantedSequence[charIndex]))
{
//ignore all subsequent white space:
while (char.IsWhiteSpace(nextChar = (char)System.Console.Read()))
{
}
}
else
{
nextChar = (char)System.Console.Read();
if (nextChar != unwantedSequence[charIndex])
return null;
}
}
input = nextChar.ToString();
if (maxFieldLength == 1)
return input;
}
while (!char.IsWhiteSpace(nextChar = (char)System.Console.Read()))
{
input += nextChar;
if (maxFieldLength == input.Length)
return input;
}
return input;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.