Ask Question, Ask an Expert


Ask Computer Engineering Expert

Huffman Coding based Compression Library

Huffman code is used to compress data file, where the data is represented as a sequence of characters. Huffman's greedy algorithm uses a table giving how often each character occurs; it then uses this table to build up an optimal way of representing each character as a binary string. We call the binary string the codeword for that character. A property of Huffman code is that it is a prefix code, i.e., in Huffman coding, no codeword is a prefix of some other codeword. The advantage of prefix code is that it makes decoding easier, as we do not need to use delimiter between two successive codewords. Given the frequency of each of the character, we can devise a greedy algorithm for finding the optimal Huffman codeword of each of the characters. For details of the greedy algorithm, INTRODUCTION TO ALGORITHMS 3rd edition by CORMEN please read Section 16.3 of the textbook.

In this assignment, we will build a compression library that compress text files using Huffman coding scheme. This library will have two programs: compress, and decompress; compress accepts a text file and produces a compressed representation of that text file; decompress accepts a file that was compressed with the compress program, and recovers the original file.


Input to the compress is a text le with arbitrary size, but for this assignment we will sippose that data structure of the file fits in the main memory of a computer. Output of the program is a compressed representation of the original file. You will have to save the codetable in the header of the compressed file, so that you could use the codetable for decompressing the compressed file. Input to the decompress is a compressed file, from that the program recovers the original file. For sanity check, you must have a specific magic word at some position in the header of the compressed file, so that decompress can recognize whether the given file is a valid Huffman compressed file.

You must pay attention to the following issues:

The file that we would use for testing can be very large, having size in Gigabytes, so make sure that your program is bug-free and it works for large input file.

prepare efficient algorithm, we will take off as much as 20 points if we feel that the program is taking unusually long time.

You must make sure that your program runs on a Linux Machine, and identically follows the formatting instructions. For formatting error, as much as 15 points can be taken off .

You should provide a Make file to compile your programs. Also, a README.txt file must be provided that will have the instruction to compile and run the programs.

Command-Line options


C++:  ./compress  -f  myfile.txt  [-o  myfile.hzip  -s

Java:  sh  -f  myfile.txt  [-o  myfile.hzip  -s]


C++:  ./decompress  -f  myfile.hzip[-r  -v]

Java:  sh  -f  myfile.hzip  [-o  myfile.txt  -s]

The command-line options that are within the square bracket are optional. The option \-f" precedes the input le name, which always has a .txt extension. The \-s" option prints statistics, such as for compression it prints, how many distinct characters are there, what is the compression ratio, and the wall clock time that it took for performing the compression task. For decompression, it prints how many character were written, and the wall clock time it took for performing the decompression task. The \-o" option precedes the name of an output le. If the output file name is not given, then we will append .hzip at the end of the input filename to create the output filename.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91171

Have any Question? 

Related Questions in Computer Engineering

Assignment preparationfor this assignment review the

Assignment Preparation For this assignment, review the organization and the industry before applying the strategic models below to Ford Motor Company. You will need at least five current, scholarly or professional resour ...

Read the raygen company slumcase study and write an essay

Read the " Raygen Company Slum "case study and write an essay that describes how you would handle the situation. You essay should incorporate the leadership skills learned this week as well as challenges that many leader ...

Using the internet in figure 111 chapter 1 in the text show

Using the internet in Figure 1.11 (Chapter 1) in the text, show the layers of the TCP/IP protocol suite and the flow of data when two hosts, one on the west coast and the other on the east coast, exchange messages.

What are the fundamental differences between

What are the fundamental differences between cost-effectiveness analysis and cost-benefit analysis? When is each most appropriately used?

1 in a tcp connection the window size fluctuates between

1. In a TCP connection, the window size fluctuates between 60,000 bytes and 30,000 bytes. If the average RTT is 30 ms, what is the throughput of the connection? 2. If originally RTTS = 14 ms and α is set to 0.2, calculat ...

1 although there has been tremendous growth in the

1. Although there has been tremendous growth in the virtualization of computing resources, there are still many skeptics of the technology. List their concerns. Suggest ways to overcome those concerns. 2. Discuss the dif ...

Programming assignmentbackground informationfor this

Programming Assignment Background information For this assignment you need to write an object-oriented console application in the Java programming language which adheres to basic object-oriented programming principles sh ...

1 what is the difference between a threat agent and a

1. What is the difference between a threat agent and a threat? 2. What is the difference between vulnerability and exposure? 3. How is infrastructure protection (assuring the security of utility services) related to info ...

Line segment informationthis program allows the user to

Line Segment Information This program allows the user to draw a line segment and then displays some graphical and textual information about the line segment. Input: 2 mouse clicks for the end points of the line segment. ...

The random class implements a random number generator which

The Random class implements a random number generator, which produces sequences of numbers that appear to be random. To generate random integers, you construct an object of the Random class, and then apply the nextInt me ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro