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/

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/

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:
}

(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

 Page 1 of 1 [ 2 post ]

Relevant Pages