论文开题：Huffman编码算法及其应用

大学本科毕业论文(设计)开题报告
学院：信息科学与工程学院 专业班级：09通信工程A班

课题名称 Huffman编码算法及其应用

1、本课题的的研究目的和意义：
在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码(Huffman Coding)是一种信源编码方式，该方法完全依据字符出现概率来构造平均长度最短的码字。 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。通过本题目，训练了我们对于信源编码技术的理解及相应编程解决问题的能力
2、 文献综述（国内外研究情况及其发展）
……（新文秘网https://www.wm114.cn省略575字，正式会员可完整阅读）……　
立 Huffman树。
(3)将 Huffman树的信息写入输出文件(压缩后文件),以备解压缩时使用。
(4)进行第二 遍扫描, 将 原文件所有 字符转化为Huffman编码,并以 ASCII字符形式保存到输出文件。
(5)在输出文件上做标记以标识压缩文件, 完成对原文件的压缩。
2、动态哈夫曼编码的算法思想：
（1）初始化编码树，即建立一棵只有一个空叶结点的哈夫曼树，该结点的符号为NYT（尚未传送），权值始终为0；
（2）每读进一个字符，首先检查该字符是否已经在编码树中，如果是，就以静态哈夫曼编码中相同的方式对其进行编码，然更新编码树；如果不是，先对空叶结点进行编码，再生成一棵子树，其右分支结点为刚读入的字符，其左分支结点为一个新的空叶结点，然后用这棵子树代替原来的空叶结点；
（3）将前i 个字符的哈夫曼树调整成一棵i+1 个字符的哈夫曼树，首先，以叶结点ai 为初始的当前结点，重复地将当前结点与具有同样权值的编号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止；其次，将根到叶结点ai 路径上的所有结点的权值加1，该树就变成了前i+1 个字符的哈夫曼树，并且该二叉树仍是最优二叉树。
静态 Huffman 编码的缺点在于在压缩时, 将会降低压缩速度同时, 为保存Huffman 树以供解压时用, 也将浪费一部分存储空间经验证明, 由于静态建树, 其压缩率也有所下降。而动态 Huffman 编码不必为解压而保存 Huffman 树的有关信息, 从而提高了数据压缩率。但是, 由于解压时采用与压缩时相同方法建树, 增加了解压时间,从而降低了还原速度。而静态 Huffman编码由于对Huffman树进行保存, 还原时不必重新建树,节省了还原时间。
huffman编码通过堆排序算法可以达到一定的改善作用，堆排序算法（HEAPSORT）由1991 年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特•弗洛伊德(Robert W．Floyd)和威廉姆(J．Williams)在1964年共同发明。堆排序可通过树形结构保存部分比较结果，可减少比较次数，从而缩短了压缩时间。Huffman编码在现实生活中经常得到应用，例如文本的压缩，现有多种对文本文件进行无损压缩的算法 ,其中哈夫曼算法依据字符出现的频率,将频率高的字符用短编码,频率低的用较长编码,不统计重复字符或重复子串编码 ,现考虑对文本文件先用哈夫曼编码算法压缩,然后再利用统计重复字符或重复子串编码的算法进行第二次压缩 ,以达到最佳的压缩效率 。
3、本课题的主要研究内容（提纲）和成果形式：
使用huffman对t*t文本进行加密，采用自适应性编码的原理，其中以C语言为基础实现代码，代码全部在Visual C++环境下调试通过。
4、拟解决的关键问题：
1）、理解huffman编码的相关工作原理。
2）、掌握huffman两种主要的编码方法：静态hu ……（未完，全文共3197字，当前仅显示1615字，请阅读下面提示信息。收藏《论文开题：Huffman编码算法及其应用》）