Anonymous user
Huffman coding: Difference between revisions
common lisp huffman codes
(common lisp huffman codes) |
|||
Line 201:
return 0;
}</lang>
=={{header|Common Lisp}}==
This implementation uses a tree built of <code>huffman-node</code>s, and a hash table mapping from elements of the input sequence to <code>huffman-node</code>s. The priority queue is implemented as a sorted list. (For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)
<lang lisp>(defstruct huffman-node
(weight 0 :type number)
(element nil :type t)
(encoding nil :type (or null bit-vector))
(left nil :type (or null huffman-node))
(right nil :type (or null huffman-node)))
(defun initial-huffman-nodes (sequence &key (test 'eql))
(let* ((length (length sequence))
(increment (/ 1 length))
(nodes (make-hash-table :size length :test test))
(queue '()))
(map nil #'(lambda (element)
(multiple-value-bind (node presentp) (gethash element nodes)
(if presentp
(incf (huffman-node-weight node) increment)
(let ((node (make-huffman-node :weight increment
:element element)))
(setf (gethash element nodes) node
queue (list* node queue))))))
sequence)
(values nodes (sort queue '< :key 'huffman-node-weight))))
(defun huffman-tree (sequence &key (test 'eql))
(multiple-value-bind (nodes queue)
(initial-huffman-nodes sequence :test test)
(do () ((endp (rest queue)) (values nodes (first queue)))
(destructuring-bind (n1 n2 &rest queue-rest) queue
(let ((n3 (make-huffman-node
:left n1
:right n2
:weight (+ (huffman-node-weight n1)
(huffman-node-weight n2)))))
(setf queue (merge 'list (list n3) queue-rest '<
:key 'huffman-node-weight)))))))1
(defun huffman-codes (sequence &key (test 'eql))
(multiple-value-bind (nodes tree)
(huffman-tree sequence :test test)
(labels ((hc (node length bits)
(let ((left (huffman-node-left node))
(right (huffman-node-right node)))
(cond
((and (null left) (null right))
(setf (huffman-node-encoding node)
(make-array length :element-type 'bit
:initial-contents (reverse bits))))
(t (hc left (1+ length) (list* 0 bits))
(hc right (1+ length) (list* 1 bits)))))))
(hc tree 0 '())
nodes)))
(defun print-huffman-code-table (nodes &optional (out *standard-output*))
(format out "~&Element~10tWeight~20tCode")
(loop for node being each hash-value of nodes
do (format out "~&~s~10t~s~20t~s"
(huffman-node-element node)
(huffman-node-weight node)
(huffman-node-encoding node))))</lang>
Example:
<pre>> (print-huffman-code-table
(huffman-codes "this is an example for huffman encoding"))
Element Weight Code
#\t 1/39 #*10010
#\d 1/39 #*01101
#\m 2/39 #*0100
#\f 1/13 #*1100
#\o 2/39 #*0111
#\x 1/39 #*100111
#\h 2/39 #*1000
#\a 1/13 #*1010
#\s 2/39 #*0101
#\c 1/39 #*00010
#\l 1/39 #*00001
#\u 1/39 #*00011
#\e 1/13 #*1101
#\n 4/39 #*001
#\g 1/39 #*01100
#\p 1/39 #*100110
#\i 1/13 #*1011
#\r 1/39 #*00000
#\Space 2/13 #*111</pre>
=={{header|Java}}==
| |||