哈夫曼编码基本原理是什么 哈夫曼编码计算公式
哈夫曼编码的工作原理,性能,应用,哈夫曼编码的原理,Huffman编码的基本原理是什么?哈夫曼编码的原理,哈夫曼编码是什么?什么赫夫曼编码,我想知道下它的原理?
本文导航
哈夫曼编码的简单实例
哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称"熵编码法"),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。这种方法是由David.A.Huffman发展起来的。例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去 25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。
参考资料:http://baike.baidu.com/lemma-php/dispose/view.php/95311.htm
哈夫曼编码怎么求
霍夫曼编码的基本思想:输入一个待编码的串,首先统计串中各字符出现的次数,称之为频次,假设统计频次的数组为count[ ],则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子,建立他们的父节点,循环这个操作2*n-1-n(n是不同的字符数)次,这样就把霍夫曼树建好了。建树的过程需要注意,首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点,他们的孩子节点的标号初始化为-1,父节点初始化为他本身的标号。接下来是编码,每次从霍夫曼树的叶子节点出发,依次向上找,假设当前的节点标号是i,那么他的父节点必然是myHuffmantree[i].parent,如果i是myHuffmantree[i].parent的左节点,则该节点的路径为0,如果是右节点,则该节点的路径为1。当向上找到一个节点,他的父节点标号就是他本身,就停止(说明该节点已经是根节点)。还有一个需要注意的地方:在查找当前权值最小的两个节点时,那些父节点不是他本身的节点不能考虑进去,因为这些节点已经被处理过了
软件编码原理学习
构造最优二叉树就是其原理。最优二叉树:假设有n个权值{w1,w2,...,wn},试构造一颗又n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称作最优二叉树,也叫赫夫曼树。具体请看数据结构相关书籍。希望这个解释对你有用,祝你学习进步~!
哈夫曼编码计算公式
设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。首先,将符号按照概率由大到小排队,如图所示。编码时,从最小概率的两个符号开始,可选其中一个支 路为0,另一支路为1。这里,我们选上支路为0,下支路为1。再将已编码的两支路的概率合并,并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图(a)和(b)可以看出,两者虽平均码长相等,但同一符号可以有不同的码长,即编码方法并不唯一,其原因是两支路概率合并后重新排队时,可能出现几个支路概率相等,造成排队方法不唯一。一般,若将新合并后的支路排到等概率的最上支路,将有利于缩短码长方差,且编出的码更接近于等长码。这里图(a)的编码比(b)好。赫夫曼码的码字(各符号的代码是异前置码字,即任一码字不会是另一码宇的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。实际应用中,除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外,主要问题是解决小符号集合的统计匹配,例如黑(1)、白(0)传真信源的统计匹配,采用0和1不同长度游程组成扩大的符号集合信源。游程,指相同码元的长度(如二进码中连续的一串0或一串1的长度或个数)。按照CCITT标准,需要统计2×1728种游程(长度),这样,实现时的存储量太大。事实上长游程的概率很小,故CCITT还规定:若l表示游程长度,则l=64q+r。其中q称主码,r为基码。编码时,不小于64的游程长度由主码和基码组成。而当l为64的整数倍时,只用主码的代码,已不存在基码的代码。长游程的主码和基码均用赫夫曼规则进行编码,这称为修正赫夫曼码,其结果有表可查。该方法已广泛应用于文件传真机中。
哈夫曼编码的具体实例
哈夫曼编码是在哈夫曼树的基础上进行的,其编码步骤为:
(1)利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树,并在叶子结点上注明对应的字符。
(2)在树中从根结点到叶子结点都有一条路径,对路径上的各分支约定指向左子树根的分支表示“0”码,指向右子树的分支表示“1”码。
(2)取从根到每个叶子上的“0”或“1”的序列作为各个叶子结点(字符)的编码。
怎样判断哪些是哈夫曼编码
1、是一种利用二叉树实现的编码原理
霍夫曼(Huffman)编码原理
霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码。属于无损压缩编码。
霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。
步骤进行:
l)将信号源的符号按照出现概率递减的顺序排列。
2)将两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率。
3)重复进行步骤1和2直到概率相加的结果等于1为止。
4)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。
5)记录下概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码。
例:
设信号源为
s={s1,
s2,
s3,
s4,
s5}
对应的概率为p={0.25,0.22,0.20,
0.18,0.15}。
根据字符出现的概率来构造平均长度最短的异字头码字。
霍未曼编码通常采用两次扫描的办法,第一次扫描得到统计结果,第二次扫描进行编码。
霍夫曼编码具有一些明显的特点:
1)
编出来的码都是异字头码,保证了码的唯一可译性。
2)
由于编码长度可变。因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时。
3)
编码长度不统一,硬件实现有难度。
4)
对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低。
5)
由于"0"与"1"的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能
2、都差不多,个人感觉c++更好学