概率论在霍夫曼编码中的应用研究_信息与计算科学 .doc

摘要:数据编码技术在计算机数字通信中一直占据着重要的地位。而在数字通信过程中，往往存在问题：信息传递的速度和所传递信息的可靠性这对不可调和的矛盾，所传递的数据编码的长度和数据译码容易产生的二义性等。以上问题，使得数据编码技术的优劣在很大程度上影响着通信的质量。数据的编码，依据数据结构。树型结构是一种应用非常广泛的结构，除利用树型结构组织各种目录外，在许多的算法中常常利用数型结构作为中间结构，以求解问题，确定对策等。在树型结构中，以二叉树的应用最为普遍，在构造加权路径的二叉查找树中，加权后路径长度最小的并不一定是具有最小深度的二叉查找树，而是权数越大的叶子离根节点越近的二叉树。这种具有最小叶节点加权路径长度的二叉查找树就是霍夫曼树。本文考虑了霍夫曼树的算法进行了分析和改进，并且给出了改进后的算法，从而提高了霍夫曼树算法的时间复杂度。所得结果改进、推广了原有的一些结论。同时，我们给出了一个霍夫曼树在通信数据编码中的应用。

关键词 霍夫曼编码；运行时间；应用

目录

摘要

Abstract

1 绪论-1

1.1 问题产生的背景以及相关知识-1

1.2本文解决主要问题-3

1.3本文的主要工作-3

2 信源与信源熵-5

2.1信源-5

2.2离散单符号信源-5

2.3 离散多符号信源-5

2.4信道-7

3霍夫曼编码及其改进-8

3.1霍夫曼编码-8

3.2 霍夫曼树-8

3.3传统的霍夫曼树算法描述-8

3.4传统程序-9

3.5算法分析-12

3.6改进的霍夫曼树算法-12

3.7改进的程序-13

4霍夫曼树在通信数据编码中的应用-17

4.1数据编码的技术要求-17

4.2霍夫曼树在信息编码中应用-17

4.3结束语-25

致谢-26

参考文献-27