香农凡诺算法举例

❶ vlc版是什么意思

VLC（variable-length coding），变长编码，即编码时每个符号的码字长度不一样。例如经典的霍夫曼编码（Huffman Coding）、香农-凡诺算法等。

❷ 无损数据压缩的无损压缩编码技术

最早阐述和实现这种编码的是Shannon（1948年）和Fano（1949年），因此被称为香农-范诺（Shannon-Fano）算法。
这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如，A、B、C、D和E，如表1所示。然后使用递归方法分成两个部分，每一部分具有近似相同的次数。按照这种方法进行编码得到的总位数为91。压缩比约为1.3 : 1。
表1 Shannon-Fano算法举例表 符号 出现的次数（Pi) log2（1/P) 分配的代码 需要的位数 A 15 (0.375） 1.4150 00 30 B 7 (0.175） 2.5145 01 14 C 7 (0.175） 2.5145 10 14 D 6 (0.150） 2.7369 110 18 E 5 (0.125） 3.0000 111 15 词典编码（dictionary encoding）的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。
第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。
第二类算法的想法是企图从输入的数据中创建一个“短语词典（dictionary of the phrases）”，这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。

❸ 算数编码和香农编码的区别

摘要 您好，香农(Shannon)编码是一种常见的可变字长编码，与哈夫曼编码相似，当信源符号出现的概率正好为2的负幂次方时，采用香农-范诺编码同样能够达到100%的编码效率。

❹ 香农范诺编码原理

霍夫曼
（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding
tree）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
以下这个简单例子说明了这一过程。
1)．字母A,B,C,D,E已被编码，相应的出现概率如下：
p(A)=0.16,
p(B)=0.51,
p(C)=0.09,
p(D)=0.13,
p(E)=0.11
2)．C和E概率最小，被排在第一棵
二叉树
中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的
哈夫曼编码
可能由相同的数据产生。
3)．各节点相应的概率如下：
p(A)=0.16,
p(B)=0.51,
p(CE)=0.20,
p(D)=0.13
D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。
如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。
4)．剩下节点的概率如下：
p(AD)=0.29,
p(B)=0.51,
p(CE)=0.20
AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。
5)．剩下两个节点相应的概率如下：
p(ADCE)=0.49,
p(B)=0.51
它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。
6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：
w(A)=001,
w(B)=1,
w(C)=011,
w(D)=000,
w(E)=010
图03-02-2
霍夫曼编码例
霍夫曼编码器的编码过程可用例子演示和解释。
下面是另一个霍夫曼编码例子。假定要编码的文本是：
"EXAMPLE
OF
HUFFMAN
CODE"
首先，计算文本中符号出现的概率（表03-02-2）。
表03-02-2
符号在文本中出现的概率
符号
概率
E
2/25
X
1/25
A
2/25
M
2/25
P
1/25
L
1/25
O
2/25
F
2/25
H
1/25
U
1/25
C
1/25
D
1/25
I
1/25
N
2/25
G
1/25
空格
3/25
最后得到图03-02-3所示的编码树。
图03-02-3
霍夫曼编码树
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive
Huffman
code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended
Huffman
code）允许编码符号组而不是单个符号。
同
香农-范诺编码
一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含
同步码
，在编码之后的码串中都不需要另外添加标记符号，即在
译码
时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error
propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。

❺ 霍夫曼编码算法在何时效率最高何时效率最低

霍夫曼(Huffman)编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。
霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短;而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
霍夫曼计算法步骤进行：
l)将信号源的符号按照出现概率递减的顺序排列。
2)将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。
3)重复进行步骤1和2直到概率相加的结果等于1为止。
4)在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
5)记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
霍夫曼计算法举例：

霍夫曼优点：
霍夫曼码的码长虽然是可变的，但却自带同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
霍夫曼编码方法的编码效率比香农-范诺编码效率高一些
霍夫曼缺点：
① 霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。
② 霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。硬件实现有难度。
③ 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
④ 压缩与还原相当费时。
⑤ 对不同信号源的编码效率不同