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.

7 Years
Discussion Span
Last Post by Zlatan25

>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)?
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
	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;

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?


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->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;
                             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)
    cout << "w: " << t->weight << " | numb: " << t->number << " | c: " << t->c << endl;;

int main()
    Tree* myt = new Tree;
    Tree* tmp;
    tmp = add(myt,'a');
    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?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.