Advanced algorithms Question 3 (40 POINTS): 3.A.) (20 POINTS) Write a program to

Question

Advanced algorithms

Question 3 (40 POINTS): 3.A.) (20 POINTS) Write a program to read a string A and display each distinct character in A, their frequencies, and the Huffman Code per distinct character in a tabular form. A sample output is listed below: Enter a text: this is an example Character Frequency Codeword 011 001 101 11010 1100 0001 1000 010 1001 11011 1 UL (total time: 6 seconds) You can choose any programming language, and for the sake of simplicity you may assume that all letters in string A are lowerca se 3.B.) (5 POINTS) Manually draw the Huffiman tree for the string A- "mississippi". Please note that your Huffman tree should be correct to get credit for the following questions. Please show your work.

Explanation / Answer

import java.util.*;

abstract class HuffmanTree implements Comparable<HuffmanTree>
{
public final int frequency; // Frequency Of This Tree
public HuffmanTree(int freq)
{
frequency = freq;
}

// Compare On Frequency
public int compareTo(HuffmanTree tree)
{
return frequency - tree.frequency;
}
}

class HuffmanLeaf extends HuffmanTree
{
public final char value; // Character This Leaf Represents

public HuffmanLeaf(int freq, char val)
{
super(freq);
value = val;
}
}

class HuffmanNode extends HuffmanTree
{
public final HuffmanTree left, right; // Subtrees

public HuffmanNode(HuffmanTree l, HuffmanTree r)
{
super(l.frequency + r.frequency);
left = l;
right = r;
}
}

public class HuffmanCode
{
public static HuffmanTree buildTree(int[] charFreqs)
{
PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();

for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

assert trees.size() > 0;

while (trees.size() > 1)
{
HuffmanTree a = trees.poll();
HuffmanTree b = trees.poll();

trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}

public static void printCodes(HuffmanTree tree, StringBuffer prefix)
{
assert tree != null;
if (tree instanceof HuffmanLeaf)
{
HuffmanLeaf leaf = (HuffmanLeaf)tree;

// Print Character, Frequency And Code
System.out.println(leaf.value + " " + leaf.frequency
+ " " + prefix);

}
else if (tree instanceof HuffmanNode)
{
HuffmanNode node = (HuffmanNode)tree;

// Traverse Left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);

// Traverse Right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}

public static void main(String[] args)
{

// For accurate result use string without user input
//String test = "this is an example";

String test;
Scanner s = new Scanner(System.in);
System.out.print(" Enter String Without Space ");
System.out.print(" Enter String : ");
test = s.next();


int[] charFreqs = new int[1024];

for (char c : test.toCharArray())
charFreqs[c]++;

HuffmanTree tree = buildTree(charFreqs);

// Print Out Results
System.out.println("Character Frequency Codeword");
printCodes(tree, new StringBuffer());
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.