Solved

Huffman Encoding, Output bits

Posted on 2009-04-02
3
587 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 47

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

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

This article will show, step by step, how to integrate R code into a R Sweave document
A short article about a problem I had getting the GPS LocationListener working.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

760 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

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now