Huffman code (long, sorry) 
Author Message
 Huffman code (long, sorry)

I have spent 3 hours looking all over the net for sample algorithm or code for
Huffman encoding.  Admittedly I just might not know what I'm doing...

I am working on a program for school that reads in a text file, encodes it into
Huffman codes, writes that code to another file, then can read that file and
decode it write it into another file.  I have a program I wrote a year ago that
decodes the file with coded material in it, which I plan to add to what I'm
writing now.  At this moment, I can count the chars in a file, and assign a
percentage that they occur in the file, and then mergesort the array of
character records into descending order by the value field of the character
record.  So now I have an array in which the least occurring letters are first,
up to the most occurring at the end, that I need to use to construct the
huffman code.  I understand how to do this on paper, by adding together the two
least values to create a mini tree, and going from there to create the whole
tree.  This part is easy to find on the web.  The part I can't find is an
algorithm of some sort, in Pascal.  One place I visited went into bitwise
operations, and I really don't want to get into asm in this program...

Anyway, enough with the background, here's the question:  Does anybody have an
algorithm they'd be willing to explain or share, or can anyone just walk with
me in getting me started with this?  My thoughts at this time are:  Does this
require some kind of interim array in which the mini trees may be stored?  I'm
seeing a kind of array of lists, or trees, like with all the roots in the
array...  and sorting the roots after each combination of the least values...
I can't get past this one, and just need some tutoring, I guess...

I will be at the above address until tomorrow afternoon(sunday), and then I

get any message posted here.  (usually, that is)  Thank you, anyone, for any
advice.  Please note that I don't wish anyone to just do this for me...  :-)
--
~teresa~

^..^  Thou shalt remember the Eleventh Commandment and keep it Wholly. ^..^
      Notebooks of Lazarus Long, Robert A. Heinlein
      Eat the .cat.nip to email...                                      
      "Blert!"



Wed, 18 Jun 1902 08:00:00 GMT  
 Huffman code (long, sorry)


Wed, 18 Jun 1902 08:00:00 GMT  
 Huffman code (long, sorry)

Quote:

> I have spent 3 hours looking all over the net for sample algorithm
> or code for Huffman encoding.  Admittedly I just might not know
> what I'm doing...

Look for Joe Jared in the source chapter of the TP-links
http://www.geocities.com/SiliconValley/2926/tp.html
He is the Huffmann guru.

Franz Glaser



Wed, 18 Jun 1902 08:00:00 GMT  
 Huffman code (long, sorry)


Wed, 18 Jun 1902 08:00:00 GMT  
 Huffman code (long, sorry)

Quote:
>I have implemented a Huffman encoding a year or so ago and I used an
>array[1..511] to store the Huffman tree, and I built the tree bottom
>up (starting from 511)   It was a non-trivial code.    If I still
>have some copy I'll post it.

If I may ask, what's the significance of 511, and for storing the tree, I was
thinking about an array of pointers, 1..25(even that much is probably
unnecessary), where each pointer is to a mini tree until the tree starts
building on itself, so that at the end you have a full tree and an empty array.
 Does that make sense?  Thanks for the code, I'd like to see it so that I know
if I'm going in the right direction...
--
~teresa~

^..^  Thou shalt remember the Eleventh Commandment and keep it Wholly. ^..^
      Notebooks of Lazarus Long, Robert A. Heinlein
      Eat the .cat.nip to email...                                      
      "Blert!"



Wed, 18 Jun 1902 08:00:00 GMT  
 Huffman code (long, sorry)

Quote:
>> If I may ask, what's the significance of 511, and for storing the tree,

>A Huffman tree will contain at most 511 nodes and leaves -- of these
>at most 256 contains a a character (it's a leaf) and at most 255 are
>internal nodes and hence contains a "pointer" to its children that
>could either be another internal node, or a leaf.

Okay, I follow.

Quote:
>Implementing the Huffman tree in an array sounds a little strange,
>but I didn't have to use pointers and dynamic allocation, though
>I had to 'normalize' the tree if there were less than 256 distinct
>characters in the input file.

Is it acceptable to continue discussion of this here?  I'd like to know more
about this, since I abhor pointers...

Quote:
>> I was
>> thinking about an array of pointers, 1..25(even that much is probably
>> unnecessary),

>             O
>            / \
>           o   o

>This is perfectly legal tree, and you'll most likely have a lot more
>than 25 of these.

I was thinking of building the tree inside the array, and I also didn't have
all the information about the assignment until today.  I have a bit more work
to do than I thought, but I would like to discuss this with you if I may, by
email, unless the others here wish it to stay?

--
~teresa~

^..^  Thou shalt remember the Eleventh Commandment and keep it Wholly. ^..^
      Notebooks of Lazarus Long, Robert A. Heinlein
      Eat the .cat.nip to email...                                      
      "Blert!"



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Huffman coding in pascal code//~~ Hellp~~~~

2. Huffman Coding in Pascal

3. FLE and Huffman coding in Pascal

4. Help !!! Huffman Coding

5. Need help for Huffman Coding

6. Huffman Coding

7. Huffman Coding

8. searching for huffman source code

9. searching huffman source code

10. I need huffman code

11. Help pleaseee :) i need Huffman code

12. Code lines too long

 

 
Powered by phpBB® Forum Software