Code

#lang racket

; encoding tree

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))

(define (leaf? object)
  (eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right)) ; or union-set
        (+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))

(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

; encoding procedure

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (encode-symbol symbol tree)
  (cond
    ((leaf? tree) '())
    ((element-of-set? symbol (symbols (left-branch tree)))
     (cons 0 (encode-symbol symbol (left-branch tree))))
    ((element-of-set? symbol (symbols (right-branch tree)))
     (cons 1 (encode-symbol symbol (right-branch tree))))
    (else (error "bad symbol: ENCODE_SYMBOL" symbol))))

; ordered-by-weight set of leaves

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair) (cadr pair))
                    (make-leaf-set (cdr pairs))))))

(define (successive-merge set)
  (if (eq? (cdr set) '())
      (car set)
      (let ((leaf1 (car set))
            (leaf2 (cadr set)))
        (successive-merge (adjoin-set (make-code-tree leaf1 leaf2)
                                      (cddr set))))))

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

; tests

(define h1 (generate-huffman-tree '((A 1) (B 2) (C 4) (D 8) (E 16))))
(encode '(A) h1)
(encode '(B) h1)
(encode '(C) h1)
(encode '(D) h1)
(encode '(E) h1)

(newline)

(define h2 (generate-huffman-tree '((A 1) (B 2) (C 4) (D 8) (E 16) (F 32) (G 64) (H 128) (I 256) (J 512))))
(encode '(A) h2)
(encode '(B) h2)
(encode '(C) h2)
(encode '(D) h2)
(encode '(E) h2)
(encode '(F) h2)
(encode '(G) h2)
(encode '(H) h2)
(encode '(I) h2)
(encode '(J) h2)

Output

'(0 0 0 0)
'(0 0 0 1)
'(0 0 1)
'(0 1)
'(1)

'(0 0 0 0 0 0 0 0 0)
'(0 0 0 0 0 0 0 0 1)
'(0 0 0 0 0 0 0 1)
'(0 0 0 0 0 0 1)
'(0 0 0 0 0 1)
'(0 0 0 0 1)
'(0 0 0 1)
'(0 0 1)
'(0 1)
'(1)

One bit is required to encode the most frequent symbol. \(n-1\) bits are required to encode the least frequent symbol.