环路生成树算法(SICPHuffman编码树习题2.672.68)

#lang sicp ;辅助方法 (define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2)))) ;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))) ;解码过程--以huffman树为依据将消息转换为表示的字符序列(解密) (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)))) ;编码过程--以huffman树为依据将字符序列转换为0/1二进制序列(加密) (define (encode message tree) (if (null? message) '() (append (encode-symbol (car message) tree) (encode (cdr message) tree)))) (define (encode-symbol symbol tree) (cond ((leaf? tree) '()) ((symbol-in-tree? symbol (left-branch tree)) (cons 0 (encode-symbol symbol (left-branch tree)))) ((symbol-in-tree? symbol (right-branch tree)) (cons 1 (encode-symbol symbol (right-branch tree)))) (else (error "bad symbol -- ENCODE-SYMBOL" symbol)))) (define (symbol-in-tree? symbol tree) (define (iter-symbols symbols) (cond ((null? symbols) #f) ((eq? symbol (car symbols)) #t) (else (iter-symbols (cdr symbols))))) (iter-symbols (symbols tree))) ;;根据字符频度表生成huffman树 (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)) ;weight (make-leaf-set (cdr pairs)))))) (define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs))) (define (successive-merge ordered_pairs) (let ((len (length ordered_pairs))) (cond ((> len 1) (let ((first (car ordered_pairs)) (second (cadr ordered_pairs))) (set! ordered_pairs (adjoin-set (make-code-tree first second) (cddr ordered_pairs)))) (successive-merge ordered_pairs)) ((= len 1) (car ordered_pairs))))) ;; 2.67 (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-bits '(0 1 1 0 0 1 0 1 0 1 1 1 0)) (decode sample-bits sample-tree) ;; 2.68 (define sample-message '(A D A B B C A)) (encode sample-message sample-tree) ;; 2.69 (define huffman-tree (generate-huffman-tree (list '(A 4) '(B 2) '(C 1) '(D 1)))) (encode sample-message huffman-tree) (decode sample-bits huffman-tree) ;; 2.70 (define song-code-tree (generate-huffman-tree (list '(A 2) '(NA 16) '(BOOM 1) '(SHA 3) '(GET 2) '(YIP 9) '(JOB 2) '(WAH 1)))) (length (encode '(GET A JOB SHA NA NA NA NA NA NA NA NA GET A JOB SHA NA NA NA NA NA NA NA NA WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP SHA BOOM) song-code-tree)) ;; 共84个二进制位 ;; 如采用定长编码8个频度的字符需要3个bit,歌曲中共包含3*2 9*2 10 2=36个字符,共需要36*3=108个二进制位,我来为大家科普一下关于环路生成树算法?下面希望有你要的答案,我们一起来看看吧!

环路生成树算法(SICPHuffman编码树习题2.672.68)

环路生成树算法

#lang sicp ;辅助方法 (define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2)))) ;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))) ;解码过程--以huffman树为依据将消息转换为表示的字符序列(解密) (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)))) ;编码过程--以huffman树为依据将字符序列转换为0/1二进制序列(加密) (define (encode message tree) (if (null? message) '() (append (encode-symbol (car message) tree) (encode (cdr message) tree)))) (define (encode-symbol symbol tree) (cond ((leaf? tree) '()) ((symbol-in-tree? symbol (left-branch tree)) (cons 0 (encode-symbol symbol (left-branch tree)))) ((symbol-in-tree? symbol (right-branch tree)) (cons 1 (encode-symbol symbol (right-branch tree)))) (else (error "bad symbol -- ENCODE-SYMBOL" symbol)))) (define (symbol-in-tree? symbol tree) (define (iter-symbols symbols) (cond ((null? symbols) #f) ((eq? symbol (car symbols)) #t) (else (iter-symbols (cdr symbols))))) (iter-symbols (symbols tree))) ;;根据字符频度表生成huffman树 (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)) ;weight (make-leaf-set (cdr pairs)))))) (define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs))) (define (successive-merge ordered_pairs) (let ((len (length ordered_pairs))) (cond ((> len 1) (let ((first (car ordered_pairs)) (second (cadr ordered_pairs))) (set! ordered_pairs (adjoin-set (make-code-tree first second) (cddr ordered_pairs)))) (successive-merge ordered_pairs)) ((= len 1) (car ordered_pairs))))) ;; 2.67 (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-bits '(0 1 1 0 0 1 0 1 0 1 1 1 0)) (decode sample-bits sample-tree) ;; 2.68 (define sample-message '(A D A B B C A)) (encode sample-message sample-tree) ;; 2.69 (define huffman-tree (generate-huffman-tree (list '(A 4) '(B 2) '(C 1) '(D 1)))) (encode sample-message huffman-tree) (decode sample-bits huffman-tree) ;; 2.70 (define song-code-tree (generate-huffman-tree (list '(A 2) '(NA 16) '(BOOM 1) '(SHA 3) '(GET 2) '(YIP 9) '(JOB 2) '(WAH 1)))) (length (encode '(GET A JOB SHA NA NA NA NA NA NA NA NA GET A JOB SHA NA NA NA NA NA NA NA NA WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP SHA BOOM) song-code-tree)) ;; 共84个二进制位 ;; 如采用定长编码8个频度的字符需要3个bit,歌曲中共包含3*2 9*2 10 2=36个字符,共需要36*3=108个二进制位

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页