## 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

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

### Algorithm: Huffman codes without a tree.

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?
cat?

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.

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.

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

### Re: Algorithm: Huffman codes without a tree.

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?

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

### Re: Algorithm: Huffman codes without a tree.

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!
<Cheese> I love you

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.

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.

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

Trees are beautiful. Learn to love them!

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

### Re: Algorithm: Huffman codes without a tree.

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

Trees are beautiful. Learn to love them!

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?

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.

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]

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

### Re: Algorithm: Huffman codes without a tree.

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.

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.

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]

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.

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.