作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (5): 49-51. doi: 10.3969/j.issn.1000-3428.2010.05.018

• 软件技术与数据库 • 上一篇    下一篇

Huffman算法程序的形式化推导

王昌晶1,2,3,罗海梅4,左正康1,2,3,薛锦云1,2   

  1. (1. 江西师范大学高性能计算技术重点实验室,南昌 330022;2. 中国科学院软件研究所,北京 100190; 3. 中国科学院研究生院,北京 100190;4. 江西师范大学物理与通讯电子学院,南昌 330022)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-03-05 发布日期:2010-03-05

Formal Derivation of Huffman Algorithm Program

WANG Chang-jing1,2,3, LUO Hai-mei4, ZUO Zheng-kang1,2,3, XUE Jin-yun1,2   

  1. (1. Key Laboratory for High-Performance Computing Technology, Jiangxi Normal University, Nanchang 330022; 2. Institute of Software, Chinese Academy of Sciences, Beijing 100190; 3. Graduate University of Chinese Academy of Sciences, Beijing 100190; 4. Institute of Physics and Communication Electronics, Jiangxi Normal University, Nanchang 330022)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-03-05 Published:2010-03-05

摘要: 使用PAR方法形式化推导了解决最优编码问题的Huffman算法。推导过程充分利用最优编码树的特性,在对原问题进行分划归约为子问题时,引入一个新元素来取代原来的2个或多个元素,使用一套接近数学语言的抽象记号表示集合、二叉树等,推导过程简洁且能生成正确的算法。该Huffman算法能在PAR平台上通过自动生成系统转换成可执行语言程序,并正常运行。

关键词: PAR方法, 形式化推导, 最优编码, Huffman算法

Abstract: Using PAR method, this paper derives formally the Huffman algorithm program for solving optimal encoding problem. It takes full advantage of the properties of optimal encoding tree. As partitioning the source problem into sub-problem, it uses a new element to replace two or more old elements. It provides a suit of abstract notations to represent set, binary tree, which is close to mathematical language. The derivation process is concise and can produce correct algorithm. The Huffman algorithm can transform into executive program and run normally using the automatic generation system in PAR platform.

Key words: PAR method, formal derivation, optimal encoding, Huffman algorithm

中图分类号: