2.3.5 · Huffman code trees

The tree makes frequent symbols cheaper.

Weighted leaves form a binary code tree where frequent symbols receive shorter paths, and the same representation drives both encoding and decoding.

Guiding question

How can one weighted tree determine both the bits we write and the symbols we recover?

Represent each leaf with one symbol and its frequency weight
Build a code tree by repeatedly merging the two lightest nodes
Encode a symbol by following branch membership from the root
Decode bits by walking to a leaf and restarting at the root

make-leaf-set orders the finite weighted symbols from lightest to heaviest. successive-merge removes the two lightest nodes, combines their symbol sets and weights, and inserts the new node back into that order until one tree remains. With the shipped weights, A receives a one-bit path while B, C, and D receive progressively deeper paths.

Encoding asks whether the next symbol belongs to the left or right branch and records 0 or 1 before continuing below that branch. Decoding consumes the same decisions in the opposite direction. Reaching a leaf emits its symbol and returns to the root for the next code word. Equal weights can admit another valid tree; the explicit insertion rule fixes the tree used by these runs.

SICP code2,224 of 1,048,576 UTF-8 bytes

(begin
  (define (append-symbols left right)
    (if (null? left)
        right
        (cons (car left) (append-symbols (cdr left) right))))
  (define (make-leaf symbol weight)
    (list 'leaf symbol weight))
  (define (leaf? object) (eq? (car object) 'leaf))
  (define (symbol-leaf leaf) (cadr leaf))
  (define (weight-leaf leaf) (caddr leaf))
  (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)
        (car (cdr (cdr (cdr tree))))))
  (define (make-code-tree left right)
    (list left
          right
          (append-symbols (symbols left) (symbols right))
          (+ (weight left) (weight right))))
  (define (adjoin-weighted node nodes)
    (cond ((null? nodes) (list node))
          ((< (weight node) (weight (car nodes)))
           (cons node nodes))
          (else
           (cons (car nodes)
                 (adjoin-weighted node (cdr nodes))))))
  (define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((entry (car pairs)))
          (adjoin-weighted
            (make-leaf (car entry) (cadr entry))
            (make-leaf-set (cdr pairs))))))
  (define (successive-merge nodes)
    (if (null? (cdr nodes))
        (car nodes)
        (successive-merge
          (adjoin-weighted
            (make-code-tree (car nodes) (cadr nodes))
            (cdr (cdr nodes))))))
  (define (symbol-in? symbol items)
    (cond ((null? items) #f)
          ((eq? symbol (car items)) #t)
          (else (symbol-in? symbol (cdr items)))))
  (define (encode-symbol symbol tree)
    (if (leaf? tree)
        '()
        (if (symbol-in? symbol (symbols (left-branch tree)))
            (cons 0 (encode-symbol symbol (left-branch tree)))
            (cons 1 (encode-symbol symbol (right-branch tree))))))
  (define tree
    (successive-merge
      (make-leaf-set '((A 4) (B 2) (D 1) (C 1)))))
  (list (weight tree)
        (symbols tree)
        (list (encode-symbol 'A tree)
              (encode-symbol 'B tree)
              (encode-symbol 'C tree)
              (encode-symbol 'D tree))))

(begin
  (define (append-symbols left right)
    (if (null? left)
        right
        (cons (car left) (append-symbols (cdr left) right))))
  (define (make-leaf symbol weight)
    (list 'leaf symbol weight))
  (define (leaf? object) (eq? (car object) 'leaf))
  (define (symbol-leaf leaf) (cadr leaf))
  (define (weight-leaf leaf) (caddr leaf))
  (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)
        (car (cdr (cdr (cdr tree))))))
  (define (make-code-tree left right)
    (list left
          right
          (append-symbols (symbols left) (symbols right))
          (+ (weight left) (weight right))))
  (define (adjoin-weighted node nodes)
    (cond ((null? nodes) (list node))
          ((< (weight node) (weight (car nodes)))
           (cons node nodes))
          (else
           (cons (car nodes)
                 (adjoin-weighted node (cdr nodes))))))
  (define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((entry (car pairs)))
          (adjoin-weighted
            (make-leaf (car entry) (cadr entry))
            (make-leaf-set (cdr pairs))))))
  (define (successive-merge nodes)
    (if (null? (cdr nodes))
        (car nodes)
        (successive-merge
          (adjoin-weighted
            (make-code-tree (car nodes) (cadr nodes))
            (cdr (cdr nodes))))))
  (define (symbol-in? symbol items)
    (cond ((null? items) #f)
          ((eq? symbol (car items)) #t)
          (else (symbol-in? symbol (cdr items)))))
  (define (encode-symbol symbol tree)
    (if (leaf? tree)
        '()
        (if (symbol-in? symbol (symbols (left-branch tree)))
            (cons 0 (encode-symbol symbol (left-branch tree)))
            (cons 1 (encode-symbol symbol (right-branch tree))))))
  (define tree
    (successive-merge
      (make-leaf-set '((A 4) (B 2) (D 1) (C 1)))))
  (list (weight tree)
        (symbols tree)
        (list (encode-symbol 'A tree)
              (encode-symbol 'B tree)
              (encode-symbol 'C tree)
              (encode-symbol 'D tree))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (8 (A B C D) ((0) (1 0) (1 1 0) (1 1 1))). The second returns ((0 1 1 1 1 0) (A D B)).

Trace focus

Follow the weighted merges that make the root, then compare each symbol-membership test with the emitted branch bit. During decoding, watch the same bits choose branches until a leaf emits a symbol and the walk restarts at the root. The execution trace records this tree and message under fixed runtime limits.

Try it yourself

Change the program and compare the result.

Encode (A B C D A) with the shipped tree. Before running it, predict the total bit count and explain why A contributes fewer bits than C or D.

Show hint

Read each code from the first example, concatenate the five paths, and count their branch decisions.

Complete this lesson

0 of 20 lessons complete in this chapter0%