Solved

Huffman Encoding, Output bits

Posted on 2009-04-02
3
610 Views
Last Modified: 2012-05-06
Last week I had to write a version of the Huffman encoding / Compression Algorithm. I managed to hack it together. It took perhaps 5 pages of printed code. I am wondering is someone has code they would be willing to share that is much more efficient. (NOTE: this is not for a project that I am submitting - rather now for my own edification.) My university has switched to java from c++ and I am having to teach myself a lot since I started in C++; I am having trouble with the various things involved.

I am well versed on the theory behind it and can do it quite well on paper, it is the efficient java form that escapes me. I have found numerous examples of code online, but none that really fit my specific question well enough.

What I am looking for: an efficient method to read a string in from a file, calculate frequency, construct binary tree with values, traverse the tree and create prefix codes. Output (in a new file) the bit values.

What I think I understand: Input and Output is fairly simple as it isn't that much different from other languages I use. I understand the concept of parsing but haven't had any luck implementing (in the program I submitted I created a variable for each expected value and then just incremented it).

Thanks in advance,
NML

(again I understand if people avoid this for suspicion reasons.)
0
Comment
Question by:Dragonfyre2825
3 Comments
 
LVL 84

Assisted Solution

by:ozo
ozo earned 20 total points
ID: 24056814
a search for huffman, java gets lots of hits,
0
 
LVL 48

Accepted Solution

by:
dbrunton earned 115 total points
ID: 24057758
>> an efficient method to read a string in from a file

Old school stuff in Turbo Pascal and for text operations you'd declare a buffer to be associated with the file.  That sped stuff up quite well.  I think you can associate a buffer for Java file operations as well.  I'd make the read string size a multiple of 512 and your buffer a multiple of your read string size.

For searching within a string look up the Boyer Moore algorithm.  That's usually the fastest out there.

As for the rest I can't help there.
0
 
LVL 16

Assisted Solution

by:imladris
imladris earned 115 total points
ID: 24060797
The heart of the algorithm is this (from your description):

>What I am looking for: an efficient method to read a string in from a file, calculate frequency, construct binary tree with values, traverse the tree and create prefix codes.

That sounds right from my remaining conceptual understanding of Huffman. It also sounds like a fairly involved set of things to be doing. Java is not all that different from C++. Can you imagine a way of doing this in a couple of pages with C++? If not, you probably shouldn't expect Java to be able to either.

The main difference I can think of is that Java contains an abstract Collections interface that supplies an ordered tree structure. C++ has STL, which provides a map which has equivalent functionality, but you can't control how it actually does things.
0

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question