Huffman算法程序的形式化推导  

Formal Derivation of Huffman Algorithm Program

作　　者：王昌晶[1,2,3] 罗海梅[4] 左正康[1,2,3] 薛锦云[1,2] 

机构地区：[1]江西师范大学高性能计算技术重点实验室,南昌330022 [2]中国科学院软件研究所,北京100190 [3]中国科学院研究生院,北京100190 [4]江西师范大学物理与通讯电子学院,南昌330022

出　　处：《计算机工程》2010年第5期49-51,共3页Computer Engineering

基　　金：科技部国际合作基金资助项目(2008DFA11940);国家自然科学基金资助项目(60773054);江西省教育厅青年科学基金资助项目(GJJ09461)

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

关 键 词：PAR方法 形式化推导 最优编码 HUFFMAN算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]