Adaptive Huffman Coding

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.

Thanks in advance!

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

[Narue]

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

[BestJewSinceJC]

http://www.csee.umbc.edu/courses/undergraduate/341/spring09/projects/proj5/HuffmanExplanation.html

Is that helpful at all? One of the projects I did in school. I don't know if that is "static" huffman coding or adaptive... I always assumed it was the only huffman coding TBH.

http://www.csee.umbc.edu/courses/undergraduate/341/spring09/projects/proj5/HuffmanExplanation.html

Is that helpful at all? One of the projects I did in school. I don't know if that is "static" huffman coding or adaptive... I always assumed it was the only huffman coding TBH.

Thanks for the answer, but it's only static Huffman Coding....

[Rashakil Fol]

Is this not sufficient?

http://en.wikipedia.org/wiki/Adaptive_Huffman_coding

Is this not sufficient?

http://en.wikipedia.org/wiki/Adaptive_Huffman_coding

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);
    
    tmp = add(myt,'a');
    add(tmp,'b');
    
    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?

[BestJewSinceJC]

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

[Zlatan25]

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