Huffman Encoding?

Huffman Encoding?

[Mark]

I'm currently writing a program that produces Huffman Encoding for text
input.  I'm trying to determine the best data structure to utilize for
sorting the character frequencies.  I used a linked-list of records to
store 1)character,
2)frequency, and 3) marked/unmarked.  (with the linked-list sorted
according to character)  From here I intended to populate the binary
tree, but must first sort according to frequency. I feel that there must
be a cleaner alternative.  Has anyone done this, and if so what did you
find to be the best approach?

Re: Huffman Encoding?

[Jerry van Dijk]

Mark (mrich22@bellatlantic.net) wrote:

: I'm currently writing a program that produces Huffman Encoding for text
: input.  I'm trying to determine the best data structure to utilize for
: sorting the character frequencies.

Hmmm, sounds like an assigment...

--
-- Jerry van Dijk | Leiden, Holland
-- Team Ada       | jdijk@acm.org
-- see http://stad.dsl.nl/~jvandyk

Re: Huffman Encoding?

[Roy Grimm]

Mark wrote:
> 
> I'm currently writing a program that produces Huffman Encoding for text
> input.  I'm trying to determine the best data structure to utilize for
> sorting the character frequencies.  I used a linked-list of records to
> store 1)character,
> 2)frequency, and 3) marked/unmarked.  (with the linked-list sorted
> according to character)  From here I intended to populate the binary
> tree, but must first sort according to frequency. I feel that there must
> be a cleaner alternative.  Has anyone done this, and if so what did you
> find to be the best approach?

When I wrote my Huffman encoder for my graduate algorithms class (which
is the only reason most people would bother doing it...), I used a
method of storing the bounded list of character frequency in a data
structure that had O(1) lookup time.  I'll leave the implementation as
an exercise for the reader.

p.s.  If you're looking to optimise space, there is a way to eliminate
one field from your list of elements.  That's an exercise for the
advanced students...

-- 
Roy A. Grimm

Mathematics and alcohol don't mix. Don't drink and derive.

Re: Huffman Encoding?

[Martin C. Carlisle]

Actually, at an undergraduate level (where we give a very similar assignment)
I would expect the students to understand a heap data structure.  
It can be created in linear time (vice nlogn for comparison based sorts),
and allows extracting the minimum and inserting new items (both required for
Huffman [the standard algorithm for it anyway]) in logarithmic time.

With a linked list, you have O(n) insert, but O(1) extract min.

--Martin

ps.  You can sort 5 elements in constant time.

In article <3708B1B2.715FC009@bigfoot.com>,
Roy Grimm  <ragrimm@bigfoot.com> wrote:
>Mark wrote:
>> 
>> I'm currently writing a program that produces Huffman Encoding for text
>> input.  I'm trying to determine the best data structure to utilize for
>> sorting the character frequencies.  I used a linked-list of records to

>method of storing the bounded list of character frequency in a data
>structure that had O(1) lookup time.  I'll leave the implementation as
>an exercise for the reader.
>
>p.s.  If you're looking to optimise space, there is a way to eliminate
>one field from your list of elements.  That's an exercise for the
>advanced students...
>
>-- 
>Roy A. Grimm
>
>Mathematics and alcohol don't mix. Don't drink and derive.


-- 
Martin C. Carlisle, Asst Prof of Computer Science, US Air Force Academy
carlislem@acm.org, http://www.usafa.af.mil/dfcs/bios/carlisle.html
DISCLAIMER:  This content in no way reflects the opinions, standards or 
policy of the US Air Force Academy or the United States Government.