huffman编码在不同场景中的应用研究

《huffman编码在不同场景中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Huffman編粧不［那環中的应研究2018-02-0921:25:13科技传播2018年3期陈泓夫摘要文章主要针对不冋场景的信源进行•概率统计，并进行Huffman编K。通过编码分析得到了不同信源Huffman编码的区别，并将编码长度与香农极限进行了比较。发现在信源长度较长时，实际Huffman编码长度接近于香农极限，而在信源较短时，则与香农极限差别较大。关键词信源编码；Huffman编码；香农极限屮图分类号TP3文献标识码A文章编号1674-6708（2018）204-0148-02信源编码是将人类讨以感知的机械信号转化为计算机或者数字逻辑电路讨以感知

2、的电信号，数学上表示为“01”申，是通信领域的一个重耍环节。除进行信息转化，信源编码要消除信息冗余，从而提高传输效率，所以信源编码又叫信源压缩编码。香农于1948年在《通讯的数学原理》一文中指出了无失真信源编码理论「1］，证明了对信源进行个失真熵编码的可能性。在《通讯的数学原理》中，香农提出/“信息熵”的概念，解决f对信息的量化度量问题，香农极限为"⑷=-!＞（*）⑽咖），其中代表符号巧的概率。Huffman编码［2］是一种高效的信源编码，被证明可以逼近香农极限。Hur「man编码是一种前缀码，常见码川短码字表示，不常见码川长码字表示，从而使得平均编码长度

3、达到最小。所以Huffman编码依赖T符号出现的概率。通常情况下，信源的概率娃一个很难获取的参数，需要通过统计的办法近似获得。文章主要分为以下儿个方面：1）统计丫特定场景信源的符号特征，得到丫其频率；2）把得到的频率作为概率，对该场景的信源进行了Huffman编码，并与香农极限进行了比较；3）针对不同场S的Huffman编码结果进行了分析。本文的剩余章节安排如下：第1章介绍Huffman编码的基本原理；第2草介绍一个特定场景下的Huffman编码；第3章介绍不同场岽的Huffman编码研究分析；第4章对本文进行总结。1基本原理文章主耍介绍Huffman编码

4、的基本原理。Huffman编码基于Huffman树的构造，构造过程如下:1）统计字符序列的每种字符的频率，并力每种字符建立一个节点，节点权重为其频率；2）初始化最小优先队列中，把上述的结点全部插入到队列屮；3)取出优先队列的前两种符号节点，并从优先队列中删除；4)新建一个父节点，并把上述两个节点作为其左右孩子节点，父节点的权值为左右节点之和；5)如果此时优先队列为空，则退出并返回父节点的指针。否则把父节点插入到优先队列屮，重复步骤3)。完成构造Huffman树之后，将每个父节点的左子节点编码为1(0)，右子节点编码为0(1)，每个字符正好是Huffman树

5、的叶子节点，从根节点做深度优先搜索即讨得到并将路径上节点的编码拼在一起即为该字符的Huffman编码。在本文屮，用上下子节点來代替左右子节点。下面用一实例来介绍Huffman编码的过程。若符号，W2，ZZ:｝，以4，恥对应概率Pl=0.4，P2=0.1,P3=P4=0-2,p5=OJo则Huffman树构造如图1所示:初始化敁小概率优先队列中，p」和p5最小，从而捋先将u2和us删掉，汴新逑父t:的概字为P（/l）=P2+P5=<>.2,并将11插入到烺小概率优先队列中。遭复匕述过程直到所有的节点都被删除。然后从根Vf点访问所奋叶子节点.并将路径编码汇聚即

6、可得到叶子节点（即字符）的Huffman编码。从而得至1jI:述吹:例的Huffman编码如卜、…：0u_.:1111u3：110u;:10u5:1110由上述实例可知，Huffman编码是一种前缀码。该实例的编码长度为L=0.4X1+0、4X4+0.2X3+0.2X2+0.1X4=2.2，其香农极限长度为f”,，=_h》,log2Pi=2.i22o在此场贺卜"，HutI'liuin编码氏度lh常接近香农极限。2特定场景下的Huffman编码文章摘取了BBC—篇新闻稿，对其Huffman编码怙况进行了研究分析。首先我们统计了该新闻稿的字符频率情况（共125

7、24个字符），如表1所示。将上标的字符频率作力字符概率，构建得到的Huffman树如图2所示。«1u0Ji,x2Z31图2由上面Huffman树可以得到Huffman编码如表2所示。计算得到平均编码长度为i4.2149，I而将该频率作为概率使用计算得到的香农极限为=所以该编码非常接近香农i极限。3不同场景下的Huffman编码分析更换一个场眾的信源做统计，将统计得到的频率作为概率使用，并进行Huffman编码，发现当统计字符个数较多时（如超过10000个字符），各个字符的统计频率趋于稳定，Huffman编码长度非常接近香農极限长度，所以，Huffman编码

8、足一种熵编码。4结论文章主要介绍了Huffman编码在实际信源场景