Trong bài tập này, chúng ta sẽ cùng làm việc với một hệ thống nó sử dụng cây Huffman để mã hóa và giải mã thông điệp và tạo ra cây Huffman tương ứng với thuật toán đã đề cập ở trên. Chúng ta sẽ bắt đầu bằng việc thảo luận cách để trình bày cây Huffman.
Các nút cảu cây được trình bày bởi một danh sách bao gồm các nút lá biểu tượng, hệ thống ở nút lá và weight tương ứng
(define (make-leaf symbol weight) (list 'leaf symbol weight))
(define (leaf? object) (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))Một cây sẽ là một danh sách của một nhánh trái và phải và một set của các symbol, và weight. Set của các symbol đơn giản là một danh sách các biểu tượng. Khi chúng ta tạo một cây bằng việc hợp hai node, chúng ta đạt được độ cao của tree như là tổng weight của các node, và set các symbol như là tập hợp của các set symbol cho các node. Từ đó set symbol được trình bày như là một danh sách, chúng ta có tập hợp chúng bằng cách sử dụng procedure append chúng ta đã định nghĩa trong bài trước.
(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))
Nếu chúng ta tạo một cây theo cách này, chúng ta sẽ có một procedure truy xuất các nhánh như sau
(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)
(cadddr tree)))Các procedure symbol và weight phải làm các việc khác nhau phụ thuộc liệu rằng chúng ta đang gọi đến một nút là hay một tree. Sau đây là một vài ví dụ của các procedure ( các procedure có thể xử lý các loại data khác nhau)
Procedure giải mã thông điệp
Procedure sau thực thị một thuật toán giải mã. Đối số của nó là danh sách của 0 và 1, cùng với một Huffman tree.
(define (decode bits tree)
(define (decode-1 bits current-branch)
(if (null? bits)
'()
(let ((next-branch
(choose-branch (car bits) current-branch)))
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (cdr bits) tree))
(decode-1 (cdr bits) next-branch)))))
(decode-1 bits tree))(define (choose-branch bit branch)
(cond ((= bit 0) (left-branch branch))
((= bit 1) (right-branch branch))
(else (error "bad bit: CHOOSE-BRANCH" bit))))Procedure decode-1 cần hai đối số: danh sách các bit còn lại và vị trí hiện tại trong cây. Tiếp tục dịch chuyển xuống cây, chọn nhánh trái hoặc nhanh phải tương ứng với liệu rằng bit tiếp theo là 0 hay 1 ( được thực hiện trong procedure choose-branch). Khi tới nút lá, nó trả về symbol ở nút lá như là symbol tiếp theo trong thông điệp, và cứ thế tiếp tục lại ở phần gốc của tree.
Sets of weighted elements
In our representation of trees, each non-leaf node contains a set of symbols, which we have represented as a simple list. However, the tree generating algorithm discussed above requires that we also work with
sets of leaves and trees, successively merging the two smallest items.
Since we will be required to repeatedly find the smallest item in a set, it
is convenient to use an ordered representation for this kind of set.
Trong việc trình bày cây, mỗi node không phải lá bao gồm một set các symbol, chúng ta đã biễu diễn chúng dưới dạng một list cơ bản. Tuy nhiên, thuật toán tạo cây Huffman yêu cầu chúng ta cần làm việc với các set của lá cảu và các tree, liên tục hợp hai item nhỏ nhất. Từ đó chúng ta sẽ được yêu cầu lặp lại để tìm item nhỏ nhất trong một set, nó là một sự tiện nghi để sử dụng một sự trình bày một list đã được sắp xếp cho loại set này.
Chúng ta sẽ trình bày một set của lá và cây như là một danh sách các thành phần, sắp xếp chúng theo thứ tự tăng dần của weight. Procedure adjoin-set cho việc khởi tạo các set, tuy nhiên, các item được so sánh với weight của chúng, và thành phần được thêm vào set chưa từng xuất hiện trong cây.
(define (adjoin-set x set)
(cond ((null? set) (list x))
((< (weight x)
(weight (car set))) (cons x set))
(else (cons (car set)
(adjoin-set x (cdr set))))))
Procedure theo sau như một list của cặp symbol và độ xuất hiện thường xuyên của chúng như là ((A 4) (B 2) (C 1) (D 1)) và khởi tạo một set các nút đã được sắp xếp, sẵn sàng để hợp nhất theo như thuật toán Huffman.(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(adjoin-set (make-leaf (car pair) ; symbol
(cadr pair)) ; frequency
(make-leaf-set (cdr pairs))))))
