摘要: 使用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
中图分类号:
王昌晶;罗海梅;左正康;薛锦云;. Huffman算法程序的形式化推导[J]. 计算机工程, 2010, 36(5): 49-51.
WANG Chang-jing; LUO Hai-mei; ZUO Zheng-kang; XUE Jin-yun;. Formal Derivation of Huffman Algorithm Program[J]. Computer Engineering, 2010, 36(5): 49-51.