 Hello!
I have to implement Adaptive Huffman Coding in C++. I can't find good source of knowledge about this algorithm.

If someone know websites describing Adpative Huffman Coding in intelligible way, please post them. In addition, I prefer pseudocode, than steps/block scheme.

PS. If I posted my thread in a wrong board, please move it. Thanks.

## All 8 Replies

>I can't find good source of knowledge about this algorithm.
Unless by "good" you mean "full source code that I can understand at my newbie level and instructions on exactly how it works so that I can paste it into my homework and get away with it", I'd say you didn't look very hard. I never wanted full source code (where I wrote it?)...

I found some websites, e.g.:
http://www.cs.cf.ac.uk/Dave/Multimedia/node212.html <- but what does Initialize_model()? or encode (c, output)?
or
http://en.wikipedia.org/wiki/Adaptive_Huffman_coding#Vitter_algorithm - what mean transmit in this case? How to do it?

Yes, I'm newbie and my English is not very good, so I need something like this (this is Static Huffman Coding):

``````Store the k leaves in a list L;
while L contains at least two nodes do
begin
Remove form L two nodes x and y of smallest weight;;
Create a new node p, and make p the parent of x and y;
p's weight := x's weight + y's weight;
Insert p into L;
end;``````

It's simple and clear for me.
Using this, few days ago I implemented Static Huffman Coding in C++ and it works very well. Now, my task is harder and I need good source of knowledge to solve it.

I understand generally the idea of Adaptive Huffman Coding, but I need something similar to included pseudocode.

Is this not sufficient? Is this not sufficient?

Because I have less time, I will try do something reading wikipedia.

Here is my source:

``````#include <iostream>

using namespace std;

struct Tree
{
int weight;
int number;

char c;

Tree* parent;
Tree* left;
Tree* right;
};

Tree* add(Tree* t, char c)
{
if(t)
{
if(t->c == '!')
{

if(t->right == 0)
{
t->right = new Tree;

t->right->left = 0;
t->right->right = 0;

t->right->parent = t;

t->right->c = c;
t->right->weight = 0;
t->right->number = t->number-1;
t->right->parent = t;
}

if(t->left == 0)
{
t->left = new Tree;

t->left->left = 0;
t->left->right = 0;

t->left->parent = t;
t->left->c = '!';
t->left->weight = 0;
t->left->number = t->number-2;
t->left->parent = t;

}
t->c = '?';

Tree* temp = t->right;

while(temp)
{
temp->weight++;
temp = temp->parent;
}
return t->left;
}
}
}
void initTree(Tree* t)
{
t->weight = 0;
t->number = 256;
t->c = '!';
t->parent =0;
t->left = 0;
t->right = 0;
}
void inOrder(Tree* t)
{
if(t->left)
inOrder(t->left);

cout << "w: " << t->weight << " | numb: " << t->number << " | c: " << t->c << endl;;

if(t->right)
inOrder(t->right);
}

int main()
{
Tree* myt = new Tree;
Tree* tmp;
initTree(myt);

inOrder(myt);
system("PAUSE");
return 0;
}``````

I know that it's not perfect, but it works. Now I have problem. I stuck in this place:

Go to that leaf node, 253. We have a block of weights of 1 and the biggest number in the block is 255, so swap the weights and symbols of nodes 253 and 255, increase weight, go to root, increase weight for root.

I should count the weights and if I find a block of them I need to swap lowest with biggest number? Can someone give me hint how to solve this stemp?

There is a C code forum... this is not it

Can anyone provide me with C++ implementation of Adaptive Huffman Coding ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.