scheme实现huffman编码的完整代码-阿里云开发者社区

开发者社区> boxti> 正文

scheme实现huffman编码的完整代码

简介: 来自sicp的完整代码,包括书中给出的代码以及习题,实现了huffman树的生成、解码、编码过程,总共67行代码,同样的代码有空用java、ruby改写下,看看会有什么不同。 (define (make-leaf symbol weight)   (list 'leaf symbol wei
+关注继续查看
来自sicp的完整代码,包括书中给出的代码以及习题,实现了huffman树的生成、解码、编码过程,总共67行代码,同样的代码有空用java、ruby改写下,看看会有什么不同。
(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)))
;解码
(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 (display "bad bit --CHOOSE-BRANCH"))))
(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) (cadr pair)) (make-leaf-set (cdr pairs))))))

;编码
(define (encode message tree)
  (
if (null? message)
      
'()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))
(define (encode
-symbol symbol tree)
  (define (iter branch)
    (
if (leaf? branch)
        
'()
        (if (memq symbol (symbols (left-branch branch)))
            (cons 0 (iter (left
-branch branch)))
            (cons 
1 (iter (right-branch branch))))
        ))
  (
if (memq symbol (symbols tree))
      (iter tree)
      (display 
"bad symbol -- UNKNOWN SYMBOL")))
;生成hufman树
(define (generate
-huffman-tree pairs)
  (successive
-merge (make-leaf-set pairs)))

(define (successive
-merge leaf-set)
  (
if (null? (cdr leaf-set))
      (car leaf
-set)
      (successive
-merge (adjoin-set (make-code-tree (car leaf-set)
                                                    (cadr leaf
-set))
                                    (cddr leaf
-set)))))
文章转自庄周梦蝶  ,原文发布时间 2007-07-23

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Netbeans源代码编辑技巧——使用代码补全和代码生成
原文 Netbeans源代码编辑技巧——使用代码补全和代码生成 使用代码补全生成代码 一般来说,代码补全对于自动填充缺失的代码是有帮助的,例如标识符和关键字。截至 NetBeans IDE 6.0,您现在甚至可以用代码补全来生成整个方法。
837 0
DES安全编码组件
  DES安全编码组件   支持 DES、DESede(TripleDES,就是3DES)、AES、Blowfish、RC2、RC4(ARCFOUR)   DES           key size must be equal to 56   DESede(TripleDES) key size must be equal to 112 or 168   AES      
981 0
新型可扩展的数据保护方式——擦除编码
一、概述   在之前存储系统中,一般都采用RAID技术来对数据进行保护,一旦阵列中某块硬盘损坏,可通过RAID技术所形成的镜像来对丢失数据进行恢复。但随着海量数据问题的出现,RAID越来越难发挥其作用。
1102 0
【GIFDecoder】GIFDecoder的排错以及修改另附完整代码和demo
前言 好久没有写技术类的博客了,今天有些小的收获,记录下来,留作备份 Gif图片的处理 由于业务需求,需要对gif动图的第一帧进行截取,然后我就搜索,发现了GIFDecoder这样的一个类,是做gif图片的处理的,怎奈国内人博客环境还是那么差,各种网站博客到处抄抄抄,没有一个完整的内容,经过多个站的资料整理,终于能用了。
826 0
+关注
boxti
12535
10037
文章
1327
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载