Algorithm: Huffman codes without a tree.

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
blackeye
Posts: 105
Joined: Mon Jul 30, 2007 4:41 am UTC

Algorithm: Huffman codes without a tree.

Postby blackeye » Thu Mar 11, 2010 1:47 am UTC

So my data structures teacher assigned us a project to generate the huffman codes for a file and I was thinking that I hate the implementation of trees. So I was wondering if it is even possible to generate huffman codes without using trees given the number the number of unique characters in a file and their frequency. I mean sure I could do it with the trees but where's the fun in that? :twisted:
cat?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm: Huffman codes without a tree.

Postby Yakk » Thu Mar 11, 2010 2:23 am UTC

What do you hate about trees? And what libraries can you use?

The Huffman code describes a tree. You can do it "without a tree", but you have a tree description from the encoding of the symbols. I guess in theory you could not have an easiliy assembled tree, just the symbol values -- but picking the symbol values sort of requires knowing what the "shape" of the distribution of other probabilities is.

Hmm. Figuring out the Huffman coding of a given symbol is tricky without having something similar to a tree, because the relative frequency of the other symbols determines your coding.

Nope, I can't figure it out. Every time I try it without a tree, I get a pseudo-tree like structure that is basically equivalent to a tree.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
blackeye
Posts: 105
Joined: Mon Jul 30, 2007 4:41 am UTC

Re: Algorithm: Huffman codes without a tree.

Postby blackeye » Thu Mar 11, 2010 10:48 am UTC

my ideal implementation is just an array sorted from max frequency to min frequency. Though the more I think about it I can make the heap in the array...
cat?

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Algorithm: Huffman codes without a tree.

Postby headprogrammingczar » Thu Mar 11, 2010 2:18 pm UTC

My advice is to just give up and use a tree. If you look hard enough, everything is a tree, and you might as well learn it now so you don't have to later.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm: Huffman codes without a tree.

Postby Yakk » Thu Mar 11, 2010 2:53 pm UTC

Yes, you can build a tree inside an array. You still end up with a tree.

If you go to wikipedia, there is a two-queue solution that claims to be able to run the "Huffman coding" algorithm in O(n) time, but the entries in the queues are trees not elements.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Leibnix
Posts: 9
Joined: Thu Apr 01, 2010 10:24 am UTC

Re: Algorithm: Huffman codes without a tree.

Postby Leibnix » Thu Apr 01, 2010 10:37 am UTC

This is like asking: "Can I implement quicksort without an array?"

Trees are beautiful. Learn to love them! :D

User avatar
blackeye
Posts: 105
Joined: Mon Jul 30, 2007 4:41 am UTC

Re: Algorithm: Huffman codes without a tree.

Postby blackeye » Mon Apr 05, 2010 12:01 am UTC

Leibnix wrote:This is like asking: "Can I implement quicksort without an array?"

Trees are beautiful. Learn to love them! :D

just looking for a more efficient way of doing things. God forbid someone makes an advance in the CS field. Trees are easy but feel so clunky to me.
cat?

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Algorithm: Huffman codes without a tree.

Postby phlip » Mon Apr 05, 2010 11:54 am UTC

Leibnix wrote:This is like asking: "Can I implement quicksort without an array?"

Quicksort works just as well with a linklist... [/pedantry]

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Bubbles McCoy
Posts: 1106
Joined: Wed Jul 09, 2008 12:49 am UTC
Location: California

Re: Algorithm: Huffman codes without a tree.

Postby Bubbles McCoy » Tue Apr 06, 2010 9:48 am UTC

Wouldn't you still need a fairly static address system in order to quickly generate pivots? I vaguely remember having cause to use quicksort on a list once and running into (theoretical) problems where getting a decently middle-of-the pack pivot was too dependent on randomizations over the list, which completely killed any time advantage unless you could instantly compute the offsets.

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Algorithm: Huffman codes without a tree.

Postby phlip » Tue Apr 06, 2010 10:12 am UTC

Well, if you always use the head of the list as the pivot, then it works fine. Sure, that strategy has its faults (eg passing in an already-sorted list is the worst-case scenario for performance) but it works fine.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Algorithm: Huffman codes without a tree.

Postby Berengal » Tue Apr 06, 2010 10:21 am UTC

Mergesort is the way to sort linked lists anyway, but now we're getting off topic.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests