Huffman Coding Objective: Implement the Huffman Coding algorithm, analyze a text

Question

Huffman Coding

Objective:

Implement the Huffman Coding algorithm, analyze a text file, and print out the codes for each letter. Huffman coding is used as a way to encode data in such a way that the symbols that appear more frequently have a smaller code representation vs. ones that appear more infrequently. This is generally done by constructing a binary tree, where each link has a value 0 or 1. For more information check here:

http://en.wikipedia.org/wiki/Huffman_coding

Demonstrate the algorithm works by printing out the frequency of each letter along with its code.

Explanation / Answer

import java.util.Scanner;

public class HuffmanCode {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a text: ");
String text = input.nextLine();
  
int[] counts = getCharacterFrequency(text); // Count frequency

System.out.printf("ASCII Code", "Character", "Frequency", "Code");
  
Tree tree = getHuffmanTree(counts);
String[] codes = getCode(tree.root);
  
for (int i = 0; i < codes.length; i++)
if (counts[i] != 0) // (char)i is not in text if counts[i] is 0
System.out.printf(i, (char)i + "", counts[i], codes[i]);
}
  
public static String[] getCode(Tree.Node root) {
if (root == null) return null;
String[] codes = new String[2 * 128];
assignCode(root, codes);
return codes;
}
  

private static void assignCode(Tree.Node root, String[] codes) {
if (root.left != null) {
root.left.code = root.code + "0";
assignCode(root.left, codes);
  
root.right.code = root.code + "1";
assignCode(root.right, codes);
}
else {
codes[(int)root.element] = root.code;
}
}
  

public static Tree getHuffmanTree(int[] counts) {
Heap<Tree> heap = new Heap<Tree>();
for (int i = 0; i < counts.length; i++) {
if (counts[i] > 0)
heap.add(new Tree(counts[i], (char)i));
}
  
while (heap.getSize() > 1) {
Tree t1 = heap.remove();
Tree t2 = heap.remove();
heap.add(new Tree(t1, t2));
}

return heap.remove();
}
  
  
public static int[] getCharacterFrequency(String text) {
int[] counts = new int[256];
  
for (int i = 0; i < text.length(); i++)
counts[(int)text.charAt(i)]++; // Count the character in text
  
return counts;
}
  

public static class Tree implements Comparable<Tree> {
Node root; // The root of the tree

public Tree(Tree t1, Tree t2) {
root = new Node();
root.left = t1.root;
root.right = t2.root;
root.weight = t1.root.weight + t2.root.weight;
}
  

public Tree(int weight, char element) {
root = new Node(weight, element);
}
  

public int compareTo(Tree t) {
if (root.weight < t.root.weight) // Purposely reverse the order
return 1;
else if (root.weight == t.root.weight)
return 0;
else
return -1;
}

public class Node {
char element; // Stores the character for a leaf node
int weight; // weight of the subtree rooted at this node
Node left; // Reference to the left subtree
Node right; // Reference to the right subtree
String code = ""; // The code of this node from the root

/** Create an empty node */
public Node() {
}
  
/** Create a node with the specified weight and character */
public Node(int weight, char element) {
this.weight = weight;
this.element = element;
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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