Solved

Huffman Encoding, Output bits

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Protect jar file - windows app 2 39
Apps blocked by Java 9 64
ForLoop Example 3 40
Plain Text Editor for iPad 6 60
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

867 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

22 Experts available now in Live!

Get 1:1 Help Now