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

import javax.swing.JOptionPane; import java.io.*; import gray.adts.heap.*; import gray.adts.binarytree.*; /** * Focus on Problem Solving solution. Encoding a text file using * Huffman coding. */ public class HuffmanCompress { private static final byte BITS_IN_A_BYTE = 8; private int[] frequencyTable; private String[] ASCIIcodeTable; private byte[] binaryCodeTable; private byte numberOfCodes; private Heap treeHeap; private BinaryTree huffmanTree; /** * Constructor - Allocate all the objects we'll need to build * a Huffman Tree. */ public HuffmanCompress(){ frequencyTable = new int[128]; treeHeap = new ArrayMinHeap( new HuffmanComparator() ); huffmanTree = null; numberOfCodes = 0; ASCIIcodeTable = new String[128]; binaryCodeTable = new byte[128]; } /** * Build the frequency table from the text found in file * fileName. * @param inFilename is not null and is the name of a file that * exists (NOT VALIDATED) */ private void buildFrequencyTable( String inFilename ) throws java.io.IOException { int len; char[] buffer = new char[128]; BufferedReader in = new BufferedReader( new InputStreamReader( new FileInputStream( inFilename ) ) ); while ( ( len = in.read( buffer, 0, 128 ) ) != -1 ) 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.