Solved

Huffman Encoding, Output bits

Posted on 2009-04-02
3
618 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

Question has a verified solution.

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

This is an explanation of a simple data model to help parse a JSON feed
This is about my first experience with programming Arduino.
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
Suggested Courses

737 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