Member Avatar for elektro123

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.

  • 5 Contributors
  • 8 Replies
  • 3K Views
  • 6 Years Discussion Span
  • Latest Post Latest Post by Zlatan25
Member Avatar for 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.

Member Avatar for elektro123

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.

Member Avatar for elektro123

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?

Member Avatar for BestJewSinceJC

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

Member Avatar for Zlatan25

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, networking, learning, and sharing knowledge.