Write a program that performs Huffman encoding and compression using a binary tr

Question

Write a program that performs Huffman encoding and compression using a binary tree. Huffman coding is an algorithm devised by David A. Huffman of MIT in 1952 for compressing text data to make a file occupy a smaller number of bytes. The idea of Huffman coding is to abandon the rigid 8-bits-per-character requirement of ASCII encoding and use different-length binary encodings for different characters. The advantage of doing this is that if a character occurs frequently in the file, such as the letter e, it could be given a shorter encoding (fewer bits), making the file smaller. Your program should contain methods to read an input text file, count its characters, and use these counts to build a Huffman tree for the characters by frequency. Use this Huffman tree to output an encoded and compressed version of the file. Also write a method to read and decompress this file later. You may want to use helper classes for reading and writing a file one bit at a time. You can find classes called BitInputStream and BitOutputStream at our web site, http://buildingjavaprograms.com.

Explanation / Answer

public class Huffman { // alphabet size of extended ASCII private static final int R = 256; // Do not instantiate. private Huffman() { } // Huffman trie node private static class Node implements Comparable { private final char ch; private final int freq; private final Node left, right; Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } // is the node a leaf node? private boolean isLeaf() { assert ((left == null) && (right == null)) || ((left != null) && (right != null)); return (left == null) && (right == null); } // compare, based on frequency public int compareTo(Node that) { return this.freq - that.freq; } } /** * Reads a sequence of 8-bit bytes from standard input; compresses them * using Huffman codes with an 8-bit alphabet; and writes the results * to standard output. */ public static void compress() { // read the input String s = BinaryStdIn.readString(); char[] input = s.toCharArray(); // tabulate frequency counts int[] freq = new int[R]; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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