Compression - Adaptive Huffman Compression... Node Count...

Author

Adaptive Huffman Compression... Node Count...

Skybuck Flying

2004-10-28, 8:55 am

Hi,

I am trying to understand precisely how the Adaptive Huffman algorithm
works.

There is ony thing which I wonder about....

Why is the node count 'decremented' ? ( I don't like this.. I rather
increment it )

Take a look at this site and applet... is it really necessary to decrement
the node count ???

http://www.cs.sfu.ca/cs/CC/365/li/s...aptiveHuff.html

Bye,
Skybuck.

Skybuck Flying

2004-10-28, 8:55 am

Oops... I ment Node Number hehe... why is it decremented ?

"Skybuck Flying" <nospam@hotmail.com> wrote in message news:...
> Hi,
>
> I am trying to understand precisely how the Adaptive Huffman algorithm
> works.
>
> There is ony thing which I wonder about....
>
> Why is the node count 'decremented' ? ( I don't like this.. I rather
> increment it )
>
> Take a look at this site and applet... is it really necessary to decrement
> the node count ???
>
> http://www.cs.sfu.ca/cs/CC/365/li/s...aptiveHuff.html
>
> Bye,
> Skybuck.
>
>

Skybuck Flying

2004-10-30, 8:55 pm

Well I have examined the code at this website a little bit

http://www.cs.sfu.ca/cs/CC/365/li/s...aptiveHuff.html

Same site as original post ;)

To me it seems the algorithm is using an array to store the tree nodes in.

The algorithm/source code also uses a function to find the highest (?) node
with a certain frequency (?)

It does this by 'walking' the array. To me this seems like cheating since an
array is not a tree... So it's not really an adaptive huffman tree is it ?

I also think the algorithm/source code is also cheating by knowing how large
the alphabet is from the start ?! This is ofcourse not known in a real world
scenerio. Ofcourse the array could be resized but that could be quite
expensive. The array could be replaced with a linked list but then the rest
of the algorithm will probably be very slow because indexes can no longer be
used... the whole list has to be traversed.

Here is some code:

public int highestInBlock (int count)
{
int highest = -1;
for (int i=0; i < 2*ALPH_SIZE; i++)
{
if (tree[i].count == count) highest=i;
}
if (highest == -1) throw new NoSuchElementException("No such node
with count of " + count);
return highest;
}

My question about this tree array is... is this array sorted ?

My next question is the following:

All websites I have seen so far use arrays etc...

Is there an algorithm for adaptive huffman tree which uses a tree
implementation only ?

That means traversing left, right and up only.

( Personally I wonder if the 'swapping' idea is still efficient for a tree
only implementation... since this highest in block function has to be
replaced with a tree traversal function, Let's hope that's the only thing
that needs to be replaced... if that's the case then it might still be
efficient with a tree only implementation... I am not sure what other parts
of the java source code/algorithm might need to be replaced... for a tree
only implementation )

Bye,
Skybuck.

Sponsored Links