Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

Huffman Coding based Compression Library
Background

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.

Implementation

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

Compression:

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

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

Decompression:

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

Java:  sh  decompress.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

The web server on the dmz web server system renames

The Web server on the DMZ Web server system renames temporary files used to record transactions. The name has the form trns followed by the integer representation of the date and time, followed by one or more digits. Why ...

Create at least two different ways of distributing turtles

Create at least two different ways of distributing turtles randomly across the screen. In one method, use only turtle motion commands such as forward , left , and right . In another method, use set or setxy . Create butt ...

In this exercise we will explore the control unit for a

In this exercise, we will explore the control unit for a cache controller for a processor with a write buffer. Use the finite state machine found in Figure 5.40 as a starting point for designing your own finite state mac ...

1 list and describe the five vulnerability assessment

1. List and describe the five vulnerability assessment processes described in the text. Can you think of some other assessment processes that might exist? 2. What is digital forensics, and when is it used in a business s ...

1 assume object x has two simple variables an integer and

1. Assume object x has two simple variables: an integer and an IP address. What is the identifier for each variable? 2. Assume object x has only one table with two columns. What is the identifier for each column? 3. Assu ...

Modify your implementation of the big integer adt from the

Modify your implementation of the Big Integer ADT from the previous question by adding the assignment combo operators that can be performed on the self and rhsInt big integers. Allow for any of the following operations t ...

How could an evolutionary process like ge be used to

How could an evolutionary process, like GE be used to evolve 1. Neural networks? 2. Production systems? Describe in some detail. In particular, how would the crossover operation be implemented? Comment on whether or not ...

You receive a computer system from the officer who tagged

You receive a computer system from the officer who tagged and bagged the evidence at a crime scene in a suspects home. You examine the computer and discover that is uses SCSI (small computer system interface) drive on Wi ...

Given is a dhke algorithm the modulus p has 1024 bit and

Given is a DHKE algorithm. The modulus p has 1024 bit and α is a generator of a subgroup where ord(α) ≈ 2160. 1. What is the maximum value that the private keys should have? 2. How long does the computation of the sessio ...

Consider a game tree in which there are six marbles and

Consider a game tree in which there are six marbles, and players 1 and 2 take turns picking from one to three marbles. The player who takes the last marble loses the game. a. Draw the complete game tree for this game. b. ...

  • 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