Member Avatar

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.

Recommended Answers

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.

Member Avatar

I never wanted full source code (where I wrote it?)...

I found some websites, e.g.: <- but what does Initialize_model()? or encode (c, output)?
or - 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.

Member Avatar

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?

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.