* Re: Huffman Encoding?
1999-04-05 0:00 ` Roy Grimm
@ 1999-04-05 0:00 ` Martin C. Carlisle
0 siblings, 0 replies; 4+ messages in thread
From: Martin C. Carlisle @ 1999-04-05 0:00 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Huffman Encoding?
@ 1999-04-05 0:00 Mark
1999-04-05 0:00 ` Roy Grimm
1999-04-05 0:00 ` Jerry van Dijk
0 siblings, 2 replies; 4+ messages in thread
From: Mark @ 1999-04-05 0:00 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Huffman Encoding?
1999-04-05 0:00 Huffman Encoding? Mark
1999-04-05 0:00 ` Roy Grimm
@ 1999-04-05 0:00 ` Jerry van Dijk
1 sibling, 0 replies; 4+ messages in thread
From: Jerry van Dijk @ 1999-04-05 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Huffman Encoding?
1999-04-05 0:00 Huffman Encoding? Mark
@ 1999-04-05 0:00 ` Roy Grimm
1999-04-05 0:00 ` Martin C. Carlisle
1999-04-05 0:00 ` Jerry van Dijk
1 sibling, 1 reply; 4+ messages in thread
From: Roy Grimm @ 1999-04-05 0:00 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~1999-04-05 0:00 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1999-04-05 0:00 Huffman Encoding? Mark
1999-04-05 0:00 ` Roy Grimm
1999-04-05 0:00 ` Martin C. Carlisle
1999-04-05 0:00 ` Jerry van Dijk
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox