霍夫曼编码(Huffman Coding)

霍夫曼编码(Huffman Coding)是一种编码方法,霍夫曼编码是可变字长编码(VLC)的一种。

霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

霍夫曼编码的具体步骤如下:

1)将信源符号的概率按减小的顺序排队。

2)把两个最小的概率相加,并继续这一步骤,始终将较高的概率分支放在右边,直到最后变成概率1。

3)画出由概率1处到每个信源符号的路径,顺序记下沿路径的0和1,所得就是该符号的霍夫曼码字。   

4)将每对组合的左边一个指定为0,右边一个指定为1(或相反)。

例:现有一个由5个不同符号组成的30个符号的字符串:

BABACAC ADADABB CBABEBE DDABEEEBB

1首先计算出每个字符出现的次数(概率):

霍夫曼编码(Huffman Coding)

2把出现次数(概率)最小的两个相加,并作为左右子树,重复此过程,直到概率值为1

霍夫曼编码(Huffman Coding)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zypzfj.html