信息工程04020

《信息工程04020》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要哈夫曼编码(HuffmanCoding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。本文将采用三进制哈夫曼编码作为例子来诠释M进制哈夫曼编码。在三进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树，沿着根节点到叶节点从左到右依次为0、1、2，保证平均码长最小。在本文中

2、采用VisualC++6.0进行编程，此程序中具有输入字符集大小和权值大小，构造哈夫曼树，并对用户输入的字符串进行编码等功能。关键词：哈弗曼编码；信源；哈夫曼树；VisualC++6.0；-17-目录引言..................................4第一章设计原理4第二章设计过程..........................................................................................................52.1VisualC++6.0简介…………………

3、……………………………………………………52.2哈夫曼算法流程图…………………………………………………………...62.3设计内容…………………………………………………………………………………6第三章编码程序及其分析9总结..............................................................................................................................17参考文献17致谢17-17-引言哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的

4、概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算法的编码和译

5、码功能，重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。-17-哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及开发工具是

6、VisualC++6.0。第一章设计原理对于多进制哈夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=(m-1)*k+r,其中m为进制数，k为缩减的次数。设计步骤如下：[1]将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)[2]给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含

7、(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。[3]将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n－3)个符号的缩减信源S2。[4]重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第二章设计过程2.1VisualC++6.0简介VisualC++6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。VisualC++是一个功能强大的可视化软件开发工具。自199

8、3年Microsoft公司推出Visu