Huffman tree...i am sweating!!!!
Author Message
Huffman tree...i am sweating!!!!

I would need to write an implementation of the decoding procedure (the
procedure takes a list of bits and a tree , it must return the message decoded)
and the encoding procedure (the procedure takes the message and a tree it must
return the bits)

(i already have the implementation of the tree)

Muchas Gracias for any help...cabrillo..

Mon, 18 Mar 2002 03:00:00 GMT
Huffman tree...i am sweating!!!!

Quote:
> I would need to write an implementation of the decoding procedure (the
> procedure takes a list of bits and a tree , it must return the message
decoded)
> and the encoding procedure (the procedure takes the message and a tree
it must
> return the bits)

> (i already have the implementation of the tree)

> Muchas Gracias for any help...cabrillo..

See http://alexvn.homepage.com/alexvn.html

Click on
n-ary Huffman Template Algorithm (file)
or
n-ary Huffman Template Algorithm (message to newsgroup).

Paul Black's Dictionary of Algorithms, Data Structures, and Problems

http://hissa.ncsl.nist.gov/~black/CRCDict

Alex

Sent via Deja.com http://www.deja.com/

Mon, 18 Mar 2002 03:00:00 GMT
Huffman tree...i am sweating!!!!

Quote:

>I would need to write an implementation of the decoding procedure (the
>procedure takes a list of bits and a tree , it must return the message decoded)
>and the encoding procedure (the procedure takes the message and a tree it must
>return the bits)

>(i already have the implementation of the tree)

I have a working implementation written in AutoLISP, but I don't know if
this could help you because it doesn't use vectors and has to deal with
avoiding NULL bytes in the stream, which makes the code
overly-complicated.

my encoding is fast but decoding is slow. to be of any practical use it
should be the other way round :)

see "ANSI Common Lisp" by Paul Graham for CL code.
(is it on OnLisp as well? cannot remember now)
--
Reini Urban

Mon, 18 Mar 2002 03:00:00 GMT
Huffman tree...i am sweating!!!!

Quote:

> I would need to write an implementation of the decoding procedure (the
> procedure takes a list of bits and a tree , it must return the message decoded)
> and the encoding procedure (the procedure takes the message and a tree it must
> return the bits)

> (i already have the implementation of the tree)

> Muchas Gracias for any help...cabrillo..

Here is an implementation of Huffman decode (with no
abstract syntax) :

(define (decode-huffman code tree0) =
(let self ((code code) (tree tree0))
(if (pair? tree)
(if (pair? code)
(self (cdr code) (if (zero? (car code)) (car tree) (cdr tree)))
(error "incomplete code"))
(if (null? code) (list tree) (cons tree (self code tree0))))))

where "code" is a list of 0's and 1's
and  "tree0 " is an huffman tree represented as an improper list of letters

test :
(define h '(a ((g . h) e . f) (c . d) . b))
(decode-huffman  '(1 1 1 1 0 1 0 1 1 0 1) h)
=> (b e d)

Thu, 21 Mar 2002 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages