Huffman coding/huffman tree 
Author Message
 Huffman coding/huffman tree

I want to know if somebody can help me implement this simple problem in
C.  All what I want to is to build a huffman tree, base on this vector.
X=[1 27 30 32 34 41 67 69].

thanks

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Sat, 10 Aug 2002 03:00:00 GMT  
 Huffman coding/huffman tree

Quote:

> I want to know if somebody can help me implement this
> simple problem in
> C.  All what I want to is to build a huffman tree,
> base on this vector.
> X=[1 27 30 32 34 41 67 69].
> thanks
> Sent via Deja.com http://www.deja.com/
> Before you buy.

The problem isn't so simple. I'd say it's of medium
complexity for a homework exercise.

I won't do everything for you and compression algorithms
themselves are off-topic here, though the C-language issues
are not.

If execution speed is not a major concern I would advise
you to implement the huffman codes as ascii strings. This
avoids the problem of code length overflowing the size of
an integer.

You want to prototype the function

/*
  generate a huffman codebook
  params: count - a list of counts of each letter
          N - the number of letters in the alphabet
  returns: malloced list of malloced codes as strings.
*/
char **huffman(int *count, int N)

Essentially you build the codebook in reverse. Take the two
lowest counts, assign the lowest index a 0 and the highest
a 1, and replace them by a single entry with a combined
count. Repeat until only one entry remains.

How do we organise this ? The easiest way is to define a
node structure

typedef struct node
{
  int letter; /* only filled for leaf nodes */
  struct node *kid0;
  struct node *kid1;
  int code;   /* one or zero */
  int count;  /* count plus count of sub-nodes */

Quote:
}

start with an array of nodes for each letter, and fill
additional ones.

(You can get away with only using the kid0 and kid1 members
if you are careful, however it is probably easier to
maintain more data).

* Sent from AltaVista http://www.altavista.com Where you can also find related Web Pages, Images, Audios, Videos, News, and Shopping.  Smart is Beautiful



Sat, 10 Aug 2002 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. huffman tree source code

2. huffman tree/coding

3. Huffman Coding Source Code in C

4. dynamic huffman coding (source code) ????

5. HELP with Huffman Tree

6. HELP with Huffman Tree Traversal - huff2.c (1/1)

7. HELP with Huffman Tree Traversal - huff2.c (1/1)

8. HELP with Huffman Tree Traversal - huff2.c (0/1)

9. HELP Huffman Tree Traversal

10. Help on Huffman trees 2

11. Help on Huffman trees

12. Smallest Huffman Binary Decoding Tree Header

 

 
Powered by phpBB® Forum Software