什么赫夫曼编码,我想知道下它的原理

什么赫夫曼编码,我想知道下它的原理~

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++更好学

赫夫曼编码
赫夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：
(1) 初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。
(2) 把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。
(3) 重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。
(4) 从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。
(5) 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。
(6) 按照仙农理论，这幅图像的熵为
H(S)=(15/39)×log2(39/15) + (7/39)×log2(39/7) + … + (5/39)×log2(39/5)
=2.1859
压缩比1.37:1。

表4-03 赫夫曼编码举例

符号 出现的次数(pi) log2(1/pi) 分配的代码 需要的位数
A 15(0.3846) 1.38 0 15
B 7(0.1795) 2.48 100 21
C 6(0.1538) 2.70 101 18
D 6(0.1538) 2.70 110 18
E 5(0.1282) 2.96 111 15

图4-02 赫夫曼编码方法
赫夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
采用赫夫曼编码时有两个问题值得注意：①赫夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②赫夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，赫夫曼码还是得到广泛应用。
与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，赫夫曼编码方法的编码效率比仙农-范诺编码效率高一些。请读者自行验证。

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++更好学

VC=Visual C++

---

坊子区15185113410： 什么赫夫曼编码,我想知道下它的原理 - ？
台奔乳酸： 赫夫曼编码赫夫曼(Huffman)在1952年提出了另一种编码方法,即从下到上的编码方法.现仍以一个具体的例子说明它的编码步骤:(1) 初始化,根据符号概率的大小按由大到小顺序对符号进行排序,如表4-03和图4-02所示.(2) 把概率...

坊子区15185113410： 哈夫曼编码原理 - ？
台奔乳酸： 原发布者:a2420092945 Huffman树及其应用一、最优二叉树(霍夫曼树)预备知识:若干术语路d径:由一结点到另一结点间的分支所构成a→e的路径长度=2beacfg路径长度:路径上的分支数目树长度=10树的路径长度:从树根到每一结点的...

坊子区15185113410： huffman编码算法 - ？
台奔乳酸： 哈夫曼是一种编码手段.也就是说保证将来的编码是最小长度的,最终生成最小的哈夫曼编码树,又称哈夫曼最小树.它的原理是将一段文本中出现的字符按出现的频率决定其编码.然后按其最终的编码生成一段明文.知道了这个原理,编码...

坊子区15185113410： 什么是赫夫曼树?？
台奔乳酸： 1、是一种利用二叉树实现的编码原理 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出...

坊子区15185113410： 什么是变字长最佳编码原理 - ？
台奔乳酸： 哈夫曼编码(Huffman Coding),又称霍夫曼编码最佳编码定理:在变字长码中,对于出现概率大的信息符号编以短字长的码;对于出现概率小的信息符号编以长字长的码,如果码字长度严格按照符号概率的大小的相反顺序排列,则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度.Huffman编码步骤:概率统计,得到n个不同概率的信号;将n个信源信息符号的n个概率,按概率大小排序;将最后两个小概率相加,概率个数减为n-1;将n-1个概率重新排序;再将最后两个小概率相加,概率个数减为n-2;如此反复n-2次,得到只剩两个概率序列;以二进制码元(0,1)赋值,构成Huffman码字.

坊子区15185113410： 什么是哈夫曼编码? - ？
台奔乳酸： 哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种. Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作...

坊子区15185113410： 哈夫曼编码是一种可变长,信源中某符号发生概率越低,其码长越 - --怎么? - ？
台奔乳酸： 哈夫曼编码的原理是:一个符号发生频率越高,其码长越短,反之则越长.很好理解:要使总长最短,出现越多次的符号的编码就要越短.打个不恰当的比方,现在用的最多的几个汉字“个”“的”“们”“什”“么”什么的笔画不是都很少吗?这就是文字演变的规律,也就是哈夫曼编码的原理.

坊子区15185113410： Huffman编码 - ？
台奔乳酸： 先分析个字符的权值:a=3,b=7,c=2,d=3,e=5生成一棵霍夫曼树,得到各字符的编码:a=110,b=0,c=1111,d=1110,e=10平均码长为46/15

坊子区15185113410： 哈夫曼编码的编码方法怎样? ？
台奔乳酸： 哈夫曼编码是一种编码方式,是可变字长编码(VLC)的一种.以哈夫曼树-即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“...

坊子区15185113410： 什么是哈夫曼算法 - ？
台奔乳酸： 题目的阐述: 以n进制编码方式对一个英文字串中的字符进行编码,每个不同的字符其编码不同.使得由新的编码替代原串后总码长最小,且输入0,1,2,...,n-1构成的数字串后,依照该编码方式可以正确的对译出唯一的英文原串. 如: n=3 英文原...