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

1 study the history of the development of computer products

1. Study the history of the development of computer products security evaluation and suggest the reasons that led to the development of ISO-based CC. 2. Study and give the effects of ISO on a criterion. Does ISO affiliat ...

Write a program to plot a horizontal bar chart of student

Write a program to plot a horizontal bar chart of student exam scores. Your program should get input from a file. The first line of the file contains the count of the number of students in the file, and each subsequent l ...

Set sorting searching and hashingoverviewquestions 1b and

Set: Sorting, Searching and Hashing Overview: Questions 1(b) and 2(a) of this assignment require a C++ compiler. As usual, you must submit the actual source code files (ending in .cpp) so that I can compile and run your ...

Writenbspa java program non-gui preferred to demonstrate

Write  a Java program (non-GUI preferred) to demonstrate the use of JDBC. The program should allow a user to do the following: Write a list of animal and its characteristics to a database using JDBC Display the character ...

Database design consider the following supply chain

Database design . Consider the following Supply Chain information system description. The system should support a collaborative supply chain composed of suppliers, manufacturers, shippers, and end customers. Items of dif ...

1 what are nested loops give an example where a nested loop

1. What are nested loops? Give an example where a nested loop is typically used. 2. Explain the differences between these debugger operations: • Stepping into a method • Stepping over a method

Create a gas price windows form applicationallow user to

Create a "Gas Price" Windows Form Application, Allow user to enter gas prices for 12 month from the textbox and click the Enter button. Create a 12 element 1-dimensional array of Decimal type Store the prices in the arra ...

1 consider proposed implementations of a systolic array you

1. Consider proposed implementations of a systolic array (you can find these in on the Internet or in technical publications). Then attempt to program the loop provided in Exercise 6.11 using this MISD model. Discuss any ...

1nbspa methodology describes how things should be done

1:  A methodology describes how things should be done , design a table showing how you can map the main activities of " Hospital  Management Project  "into the knowledge areas ? Q 2: Using Microsoft Project 2007/2010 too ...

1 how does technological obsolescence constitute a threat

1. How does technological obsolescence constitute a threat to information security? How can an organization protect against it? 2. Does the intellectual property owned by an organization usually have value? If so, how ca ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen