SICP

Exercise 2.68. The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message.

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

Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message.

encode-symbol 将会去对一个字符进行编码。按照一棵树，路径往左则编码前缀 0，往右则是 1。

因为我们的选择函数 symbols 能够分辨出这棵树到底是 leaf 还是不是，所以我们可以统一地使用 symbols 来求一个节点往下的所有节点的字符集合。借用这个集合，我们可以知道当前节点处应该使用 0 还 1（往左还是往右）。

;;; decide the branch
(define (encoding sym tree)
  (if (not (element-of-set? sym (symbols tree)))
      (error 'encode-symbol "symbol NOT FOUND" sym " in " tree)
      (let ((left (left-branch tree))
            (right (right-branch tree)))
        (if (element-of-set? sym (symbols left))
            0
            1))))

有了这个过程，我们就可以在 encode-symbol 中判断路径了。

;;; recursively encode the symbol
(define (encode-symbol sym tree)
  (if (leaf? tree)
      '()
      (let ((code (encoding sym tree)))
        (if (= code 1)
            (cons code
                  (encode-symbol sym
                                 (right-branch tree)))
            (cons code
                  (encode-symbol sym
                                 (left-branch tree)))))))
;;; 2. 
;;; decide the branch
(define (encoding sym tree)
  (if (not (element-of-set? sym (symbols tree)))
      (error 'encode-symbol "symbol NOT FOUND" sym " in " tree)
      (let ((left (left-branch tree))
            (right (right-branch tree)))
        (if (element-of-set? sym (symbols left))
            0
            1))))

;;; tests begin
(load "../testframe.scm")

(assertequal? (encode '(a d a b b c a) sample-tree)
              sample-message)

(assert/exn (encode '(a e a) sample-tree) "NOT FOUND")

最后是测试：

(load "huffman-tree.scm")

(load "67-decode-sample.scm")

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

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

;;; 1.
;;; recursively encode the symbol
(define (encode-symbol sym tree)
  (if (leaf? tree)
      '()
      (let ((code (encoding sym tree)))
        (if (= code 1)
            (cons code
                  (encode-symbol sym
                                 (right-branch tree)))
            (cons code
                  (encode-symbol sym
                                 (left-branch tree)))))))
;;; 2. 
;;; decide the branch
(define (encoding sym tree)
  (if (not (element-of-set? sym (symbols tree)))
      (error 'encode-symbol "symbol NOT FOUND" sym " in " tree)
      (let ((left (left-branch tree))
            (right (right-branch tree)))
        (if (element-of-set? sym (symbols left))
            0
            1))))

SICP 全笔记