|
|||||
|
|
| Huffman算法程序的形式化推导 | |
| 引用本文： | 王昌晶,罗海梅,左正康,薛锦云. Huffman算法程序的形式化推导[J]. 计算机工程, 2010, 36(5): 49-51 |
| 作者姓名： | 王昌晶 罗海梅 左正康 薛锦云 |
| 作者单位： | 1. 江西师范大学高性能计算技术重点实验室,南昌,330022;中国科学院软件研究所,北京,100190;中国科学院研究生院,北京,100190 2. 江西师范大学物理与通讯电子学院,南昌,330022 3. 江西师范大学高性能计算技术重点实验室,南昌,330022;中国科学院软件研究所,北京,100190 |
| 基金项目： | 科技部国际合作基金资助项目(2008DFA11940);;国家自然科学基金资助项目(60773054);;江西省教育厅青年科学基金资助项目(GJJ09461) |
| 摘 要： | 使用PAR方法形式化推导了解决最优编码问题的Huffman算法。推导过程充分利用最优编码树的特性，在对原问题进行分划归约为子问题时，引入一个新元素来取代原来的2个或多个元素，使用一套接近数学语言的抽象记号表示集合、二叉树等，推导过程简洁且能生成正确的算法。该Huffman算法能在PAR平台上通过自动生成系统转换成可执行语言程序，并正常运行。 |
| 关 键 词： | PAR方法 形式化推导 最优编码 Huffman算法 |
| 修稿时间： | |
Formal Derivation of Huffman Algorithm Program |
|
| 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 | |
| Authors: | WANG Chang-jing LUO Hai-mei ZUO Zheng-kang XUE Jin-yun |
| Affiliation: | 1.Key Laboratory for High-Performance Computing Technology/a>;Jiangxi Normal University/a>;Nanchang 330022/a>;2.Institute of Software/a>;Chinese Academy of Sciences/a>;Beijing 100190/a>;3.Graduate University of Chinese Academy of Sciences/a>;4.Institute of Physics and Communication Electronics/a>;Nanchang 330022 |
| 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. |
| Keywords: | PAR method formal derivation optimal encoding Huffman algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程》浏览原始摘要信息 | |
| 点击此处可从《计算机工程》下载免费的PDF全文 | |