2.3.4 Example: Huffman Encoding TreesをPythonでやってみた

scheme
;2.3.4  Example: Huffman Encoding Trees
;Representing Huffman trees

(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))

(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

(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)))

;The decoding procedure
(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))))

;Sets of weighted elements
(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))))))

(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))))))
python
#2.3.4  Example: Huffman Encoding Trees
#Representing Huffman trees

def make_leaf(symbol, weight):
return ['leaf', symbol, weight]
def leaf_q(object):
return object == 'leaf'
def symbol_leaf(x):
return x[1]
def weight_leaf(x):
return x[2]

def make_code_tree(left, right):
return [left, right, symbols(left) + symbols(right), \
weight(left) + weight(right)]

def left_branch(tree):
return tree[0]

def right_branch(tree):
return tree[1]

def symbols(tree):
if leaf_q(tree):
return [symbol_leaf(tree)]
return tree[2]
def weight(tree):
if leaf_q(tree):
return weight_leaf(tree)
return tree[3]

#The decoding procedure
def decode_f(bits, tree):
def decode_1(bits, current_branch):
if not bits:
return []
next_branch = choose-branch(bits[0], current_branch)
if leaf_q(next_branch):
return [symbol_leaf(next_branch), decode_1(bits[1:], tree)]
return decode_1(bits[1:], next_branch)
return decode_1(bits, tree)
def choose_branch(bits, branch):
if bit == 0:
return left_branch(branch)
if bit == 1:
return right_branch(branch)
else:
print "error bad bit -- CHOOSE-BRANCCH", bit

#Sets of weighted elements
def adjoin_set(x, set):
if not set:
return [x]
if weight(x) < weight(set[0]):
return [x, set]
else:
return [set[0], adjoin_set(x, set[1:])]

def make_leaf_set(pairs):
if not pairs:
return []
pair = pairs[0]
return adjoin_set(make_leaf(pair[0], pair[1]), make_leaf_set(pairs[1:]))

いまひとつ理解できなかった(つдT)