1 665c255d 2023-08-04 jrmu (define (test-case actual expected)
3 665c255d 2023-08-04 jrmu (display "Actual: ")
4 665c255d 2023-08-04 jrmu (display actual)
6 665c255d 2023-08-04 jrmu (display "Expected: ")
7 665c255d 2023-08-04 jrmu (display expected)
10 665c255d 2023-08-04 jrmu (define (make-leaf symbol weight)
11 665c255d 2023-08-04 jrmu (list 'leaf symbol weight))
12 665c255d 2023-08-04 jrmu (define (leaf? object)
13 665c255d 2023-08-04 jrmu (eq? (car object) 'leaf))
14 665c255d 2023-08-04 jrmu (define (symbol-leaf x) (cadr x))
15 665c255d 2023-08-04 jrmu (define (weight-leaf x) (caddr x))
17 665c255d 2023-08-04 jrmu (define (make-code-tree left right)
20 665c255d 2023-08-04 jrmu (append (symbols left) (symbols right))
21 665c255d 2023-08-04 jrmu (+ (weight left) (weight right))))
23 665c255d 2023-08-04 jrmu (define (left-branch tree) (car tree))
24 665c255d 2023-08-04 jrmu (define (right-branch tree) (cadr tree))
25 665c255d 2023-08-04 jrmu (define (symbols tree)
26 665c255d 2023-08-04 jrmu (if (leaf? tree)
27 665c255d 2023-08-04 jrmu (list (symbol-leaf tree))
28 665c255d 2023-08-04 jrmu (caddr tree)))
29 665c255d 2023-08-04 jrmu (define (weight tree)
30 665c255d 2023-08-04 jrmu (if (leaf? tree)
31 665c255d 2023-08-04 jrmu (weight-leaf tree)
32 665c255d 2023-08-04 jrmu (cadddr tree)))
34 665c255d 2023-08-04 jrmu (define (decode bits tree)
35 665c255d 2023-08-04 jrmu (define (decode-1 bits current-branch)
36 665c255d 2023-08-04 jrmu (if (null? bits)
38 665c255d 2023-08-04 jrmu (let ((next-branch
39 665c255d 2023-08-04 jrmu (choose-branch (car bits) current-branch)))
40 665c255d 2023-08-04 jrmu (if (leaf? next-branch)
41 665c255d 2023-08-04 jrmu (cons (symbol-leaf next-branch)
42 665c255d 2023-08-04 jrmu (decode-1 (cdr bits) tree))
43 665c255d 2023-08-04 jrmu (decode-1 (cdr bits) next-branch)))))
44 665c255d 2023-08-04 jrmu (decode-1 bits tree))
45 665c255d 2023-08-04 jrmu (define (choose-branch bit branch)
46 665c255d 2023-08-04 jrmu (cond ((= bit 0) (left-branch branch))
47 665c255d 2023-08-04 jrmu ((= bit 1) (right-branch branch))
48 665c255d 2023-08-04 jrmu (else (error "bad bit -- CHOOSE-BRANCH" bit))))
50 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
51 665c255d 2023-08-04 jrmu (cond ((null? set) (list x))
52 665c255d 2023-08-04 jrmu ((< (weight x) (weight (car set))) (cons x set))
53 665c255d 2023-08-04 jrmu (else (cons (car set)
54 665c255d 2023-08-04 jrmu (adjoin-set x (cdr set))))))
55 665c255d 2023-08-04 jrmu (define (make-leaf-set pairs)
56 665c255d 2023-08-04 jrmu (if (null? pairs)
58 665c255d 2023-08-04 jrmu (let ((pair (car pairs)))
59 665c255d 2023-08-04 jrmu (adjoin-set (make-leaf (car pair)
60 665c255d 2023-08-04 jrmu (cadr pair))
61 665c255d 2023-08-04 jrmu (make-leaf-set (cdr pairs))))))
63 665c255d 2023-08-04 jrmu (define (encode message tree)
64 665c255d 2023-08-04 jrmu (if (null? message)
66 665c255d 2023-08-04 jrmu (append (encode-symbol (car message) tree)
67 665c255d 2023-08-04 jrmu (encode (cdr message) tree))))
69 665c255d 2023-08-04 jrmu (define (element-of-set x set)
70 665c255d 2023-08-04 jrmu (and (not (null? set))
71 665c255d 2023-08-04 jrmu (or (equal? x (car set))
72 665c255d 2023-08-04 jrmu (element-of-set x (cdr set)))))
74 665c255d 2023-08-04 jrmu (define (encode-symbol sym tree)
75 665c255d 2023-08-04 jrmu (cond ((null? tree) (error "empty tree"))
76 665c255d 2023-08-04 jrmu ((not (element-of-set sym (symbols tree)))
77 665c255d 2023-08-04 jrmu (error "symbol not in tree"))
78 665c255d 2023-08-04 jrmu ((leaf? tree) '())
79 665c255d 2023-08-04 jrmu ((element-of-set sym (symbols (left-branch tree)))
80 665c255d 2023-08-04 jrmu (cons 0 (encode-symbol sym (left-branch tree))))
81 665c255d 2023-08-04 jrmu ((element-of-set sym (symbols (right-branch tree)))
82 665c255d 2023-08-04 jrmu (cons 1 (encode-symbol sym (right-branch tree))))))
84 665c255d 2023-08-04 jrmu (define (generate-huffman-tree pairs)
85 665c255d 2023-08-04 jrmu (successive-merge (make-leaf-set pairs)))
87 665c255d 2023-08-04 jrmu (define (successive-merge leaf-set)
88 665c255d 2023-08-04 jrmu (cond ((null? leaf-set) (error "no leaves in leaf-set"))
89 665c255d 2023-08-04 jrmu ((null? (cdr leaf-set)) (car leaf-set))
90 665c255d 2023-08-04 jrmu (else (successive-merge (adjoin-set (make-code-tree (cadr leaf-set)
91 665c255d 2023-08-04 jrmu (car leaf-set))
92 665c255d 2023-08-04 jrmu (cddr leaf-set))))))
94 665c255d 2023-08-04 jrmu ;; Exercise 2.71. Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^n-1. Sketch the tree for n=5; for n=10. In such a tree (for general n) how many bits are required to encode the most frequent symbol? the least frequent symbol?
96 665c255d 2023-08-04 jrmu ;; for a tree of n symbols, 1 bit for most frequent; n-1 bits for least frequent symbol
98 665c255d 2023-08-04 jrmu ;; Exercise 2.72. Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.
100 665c255d 2023-08-04 jrmu (define (encode message tree)
101 665c255d 2023-08-04 jrmu (if (null? message)
103 665c255d 2023-08-04 jrmu (append (encode-symbol (car message) tree)
104 665c255d 2023-08-04 jrmu (encode (cdr message) tree))))
106 665c255d 2023-08-04 jrmu (define (element-of-set x set)
107 665c255d 2023-08-04 jrmu (and (not (null? set))
108 665c255d 2023-08-04 jrmu (or (equal? x (car set))
109 665c255d 2023-08-04 jrmu (element-of-set x (cdr set)))))
111 665c255d 2023-08-04 jrmu (define (encode-symbol sym tree)
112 665c255d 2023-08-04 jrmu (cond ((null? tree) (error "empty tree"))
113 665c255d 2023-08-04 jrmu ;; we're going to pretend this isn't here to speed up the procedure
114 665c255d 2023-08-04 jrmu ;; ((not (element-of-set sym (symbols tree)))
115 665c255d 2023-08-04 jrmu ;; (error "symbol not in tree"))
116 665c255d 2023-08-04 jrmu ((leaf? tree) '())
117 665c255d 2023-08-04 jrmu ((element-of-set sym (symbols (left-branch tree)))
118 665c255d 2023-08-04 jrmu (cons 0 (encode-symbol sym (left-branch tree))))
119 665c255d 2023-08-04 jrmu ((element-of-set sym (symbols (right-branch tree)))
120 665c255d 2023-08-04 jrmu (cons 1 (encode-symbol sym (right-branch tree))))))
122 665c255d 2023-08-04 jrmu we must call encode-symbol the same number of times as the length of message
123 665c255d 2023-08-04 jrmu So, if message is m elements long, we must call encode-symbol m times
125 665c255d 2023-08-04 jrmu Within encode-symbol, we must check through the list of symbols either on the left-branch or on the right-branch. If the symbol is on the left-branch, we just check 1 element. Otherwise, we must check, on average, (n-1)/2 elements. There is roughly a 50-50 chance that the symbol will be on the left-branch vs. right-branch.
128 665c255d 2023-08-04 jrmu 25%: (n-1)/2 + 1
129 665c255d 2023-08-04 jrmu 12.5%: (n-1)/2 + (n-2)/2 + 1
132 665c255d 2023-08-04 jrmu Most frequent symbols O(1), but least-frequent symbol is O(n^2)
