假设我们已经有了可运行的 encode
函数,那么对于 练习 2.67 的 sample-tree
:
(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
表达式 (encode (list 'A 'D 'A 'B 'B 'C 'A) sample-tree)
的执行过程应该是:
(encode (list 'A 'D 'A 'B 'B 'C 'A) sample-tree)
(append (encode-symbol 'A sample-tree)
(encode (list 'D 'A 'B 'B 'C 'A) sample-tree))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(encode (list 'A 'B 'B 'C 'A) sample-tree)))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(encode (list 'B 'B 'C 'A) sample-tree))))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'B sample-tree)
(encode (list 'B 'C 'A sample-tree))))))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'B sample-tree)
(encode (list 'C 'A) sample-tree))))))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'C sample-tree)
(encode (list 'A) sample-tree)))))))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'C sample-tree)
(append (encode-symbol 'A sample-tree)
(encode '() sample-tree))))))))
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'D sample-tree)
(append (encode-symbol 'A sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'B sample-tree)
(append (encode-symbol 'C sample-tree)
(append (encode-symbol 'A sample-tree)
'())))))))
(append (list 0) ; A
(append (list 1 1 0) ; D
(append (list 0) ; A
(append (list 1 0) ; B
(append (list 1 0) ; B
(append (list 1 1 1) ; C
(append (list 0) ; A
'())))))))
'( 0 1 1 0 0 1 0 1 0 1 1 1 0)
其中 encode-symbol
就是题目要我们写出的函数,它的返回值是相应的符号的编码位。
对于 sample-tree
,可以用一个图形来表示它:
[A B D C]
*
/ \
A \
* [B D C]
/ \
B \
* [D C]
/ \
D C
要使用 encode-symbol
函数获取给定符号的编码位,其实就是要求我们在给定的树中查找给定符号的叶子节点,并记录下寻找过程中的左右方向,每次向左前进一层就用一个 0
表示,每次向右前进一层就用 1
表示,直到到达给定的符号所在的树叶为止。
比如说, (encode-symbol 'D sample-tree)
的穿行过程就有以下步骤:
当前位置 | 方向 | 当前位 | 已编码信息位 |
---|---|---|---|
[A B D C] | 无 | 无 | 无 |
[B D C] | 右 | 1 | 1 |
[D C] | 右 | 1 | 11 |
D | 左 | 0 | 110 |
有了前面的线索,现在可以给出 encode-symbol
的定义了:
;;; 68-encode-symbol.scm
(load "p112-huffman.scm")
(define (encode-symbol symbol tree)
(cond ((leaf? tree) ; 如果已经到达叶子节点,那么停止积累
'())
((symbol-in-tree? symbol (left-branch tree)) ; 符号在左分支(左子树),组合起 0
(cons 0
(encode-symbol symbol (left-branch tree))))
((symbol-in-tree? symbol (right-branch tree)) ; 符号在右分支(右子树),组合起 1
(cons 1
(encode-symbol symbol (right-branch tree))))
(else ; 给定符号不存在于树,报错
(error "This symbol not in tree: " symbol))))
(define (symbol-in-tree? given-symbol tree)
(not
(false?
(find (lambda (s) ; 使用 find 函数,在树的所有符号中寻找给定符号
(eq? s given-symbol))
(symbols tree))))) ; 取出树中的所有符号
测试 encode-symbol
:
1 ]=> (load "p112-huffman.scm")
;Loading "p112-huffman.scm"... done
;Value: weight
1 ]=> (define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
;Value: sample-tree
1 ]=> (load "68-encode-symbol.scm")
;Loading "68-encode-symbol.scm"...
; Loading "p112-huffman.scm"... done
;... done
;Value: symbol-in-tree?
1 ]=> (encode-symbol 'D sample-tree)
;Value 14: (1 1 0)
1 ]=> (encode-symbol 'A sample-tree)
;Value 15: (0)
1 ]=> (encode-symbol 'hello sample-tree) ; 符号不存在于树
;This symbol not in tree: hello
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.
2 error>
测试 symbol-in-tree?
:
1 ]=> (symbol-in-tree? 'a sample-tree)
;Value: #t
1 ]=> (symbol-in-tree? 'hello sample-tree)
;Value: #f
有了 encode-symbol
,现在可以给出完整的 encode
定义了:
;;; 68-encode.scm
(load "68-encode-symbol.scm")
(define (encode message tree)
(if (null? message)
'()
(append (encode-symbol (car message) tree)
(encode (cdr message) tree))))
测试:
1 ]=> (load "68-encode.scm")
;Loading "68-encode.scm"...
; Loading "68-encode-symbol.scm"...
; Loading "p112-huffman.scm"... done
; ... done
;... done
;Value: encode
1 ]=> (encode (list 'A 'D 'A 'B 'B 'C 'A) sample-tree)
;Value 16: (0 1 1 0 0 1 0 1 0 1 1 1 0)