-
Notifications
You must be signed in to change notification settings - Fork 0
/
2_67.el
44 lines (41 loc) · 1.51 KB
/
2_67.el
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(defun make-leaf (symbol weight) (list 'leaf symbol weight))
(defun leaf? (object) (equal (car object) 'leaf))
(defun symbol-leaf (x) (cadr x))
(defun weight-leaf (x) (caddr x))
(defun make-code-tree (left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))
(defun left-branch (tree) (car tree))
(defun right-branch (tree) (cadr tree))
(defun symbols (tree)
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))
(defun weight (tree)
(if (leaf? tree)
(weight-leaf tree)
(cadddr tree)))
(defun decode (bits tree)
(defun decode-1 (bits current-branch)
(if (not 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))
(defun choose-branch (bit branch)
(cond ((= bit 0) (left-branch branch))
((= bit 1) (right-branch branch))
(t (error "bad bit: CHOOSE-BRANCH" bit))))
(defvar 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)))))
(defvar sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
(decode sample-message sample-tree) ; (A D A B B C A)