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.
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.
(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))))- Output
- —
- Value
- —
- Diagnostic
- —
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)).
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 bounded trace explains only this fixed tree and message.
Change the program before you read the hint.
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 one hint
Read each code from the first example, concatenate the five paths, and count their branch decisions.