Anonymous user
Huffman coding: Difference between revisions
wrote code using example described
(→{{header|Scheme}}: Marked incorrect.) |
(wrote code using example described) |
||
Line 4,572:
</pre>
=={{header|Scheme}}==
(define (leaf? object)▼
(eq? (car object) 'leaf))▼
(define (make-code-tree left right)▼
(define (left-branch tree) (car tree))▼
(define (symbols tree)▼
(define (weight tree)▼
<lang scheme>(define (
(if
table
((= bit 1) (right-branch branch))▼
(char-freq
(if (null? bits)▼
'()▼
(decode-1 (cdr bits) next-branch)))))▼
(define (
(cond
((eq? (caar table)
(map (lambda (x) (list x '() '())) table))
(define node-freq cadar)
(let ((queue (sort nodes (lambda (x y) (< (node-freq x) (node-freq y))))))
(if
(null? (cdr queue))
(car queue)
(huffman-tree
(cons
(list 'notleaf (+ (node-freq (car queue)) (node-freq (cadr queue))))
(car queue)
(cadr queue))
(cddr queue))))))
(for-each (lambda (c) (format #t "~a:~a~%" c (encode c tree))) chars))
(cond
(#t
(let ((left (encode char (cadr tree))) (right (encode char (caddr tree))))
(cond
(left (cons #\1 left))
(right (cons #\0 right)))))))
(cond
((not (eq? (caar tree) 'notleaf)) (caar tree))
((eq? (car digits) #\0) (decode (cdr digits) (cadr tree)))
(define input "this is an example for huffman encoding")
(define freq-table (char-freq (open-input-string input) '()))
(define tree (huffman-tree (nodeify freq-table)))
(list-encodings tree (map car freq-table))</lang>
Output:
<pre>
t:(1 0 0 1 1)
h:(1 0 0 0)
i:(
s:(1 0 1 1)
:(0 0 0)
a:(0 0 1 0)
n:(1 1 0)
e:(0 1 0 1)
x:(1 0 0 1 0)
m:(1 0 1 0)
p:(1 1 1 0 1)
l:(1 1 1 0 0)
f:(0 1 0 0)
o:(0 1 1 1)
r:(1 1 1 1 1)
u:(1 1 1 1 0)
c:(0 1 1 0 0 1)
d:(0 1 1 0 0 0)
g:(0 1 1 0 1)
</pre>
|