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).

See also
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/
Before you buy.



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
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html



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  
 
 [ 4 post ] 

 Relevant Pages 

1. huffman tree

2. HUFFMAN TREE.

3. tree traversal & sort problems (huffman)

4. Sweat equity programmer wanted for consumer harware startup

5. I am not deaf, but am I mute?

6. Self-Adjusting Binary Search Trees (Splay Trees)

7. Self-Adjusting Binary Search Trees (Splay Trees)

8. TREE browse .. Ultra Tree Template - Att Marius

9. Huffman

10. About Huffman ...

11. help! i need an example of huffman encoding

12. Huffman's Algorithm

 

 
Powered by phpBB® Forum Software