【Scheme】Huffman树

(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))) ;由上面make-code-tree可知，weight位于表第4个位置

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

(define (adjoin-set x set)

  (cond ((null? set) (list x))

        ((< (weight x) (weight (car set))) (cons x set))   ;x<min(set) 所以放集合最前

        (else (cons (car set)

                    (adjoin-set x (cdr set)))))) ; x比当前set元素大,所以x属于(cdr set)

(define (make-leaf-set pairs)

  (if (null? pairs)

      '()

      (let ((pair (car pairs)))

        (adjoin-set (make-leaf (car pair)

                               (cadr pair))

                    (make-leaf-set(cdr pairs))))))

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

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0)) ;测试编码

(decode sample-message sample-tree) ;解码
巴特西

【Scheme】Huffman树

最新文章

热门文章
