王咏刚20xx年2月

王咏刚20xx年2月内容摘要：

) = 个二进制位进行编码 难道真的能只输出 个 0 或 个 1 吗。 算术编码的输出是：一个小数 算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0和 1之间的二进制小数。 例如算术编码对某条信息的输出为 1010001111，那么它表示小数 ，也即十进制数 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 第一步 ：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为 1/3，我们将 01区间按照概率的比例分配给三个字符，即 a从 ， b从 ， c从。 用图形表示就是： Pc = 1/3 Pb = 1/3 Pa = 1/3 算术编码 第二步 ：现在我们拿到第一个字符 b， 让我们把目光投向 b对应的区间。 这时由于多了字符 b， 三个字符的概率分布变成：Pa=1/4， Pb=2/4， Pc=1/4。 好，让我们按照新的概率分布比例划分，划分的结果可以用图形表示为： Pc = 1/4 Pb = 2/4 Pa = 1/4 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 算术编码 第三步 ：接着我们拿到字符 c， 我们现在要关注上一步中得到的 c的区间。 新添了 c以后，三个字符的概率分布变成 Pa=1/5，Pb=2/5， Pc=2/5。 我们用这个概率分布划分区间 ： Pc = 2/5 Pb = 2/5 Pa = 1/5 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 算术编码 第四步 ：现在输入下一个字符 c， 三个字符的概率分布为： Pa=1/6，Pb=2/6， Pc=3/6。 我们来划分 c的区间 ： Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 算术编码 第五步 ：输入最后一个字符 b， 因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b的区间为 ，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如 ，将它变成二进制 ，去掉前面没有太多意义的 0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程 Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb 输出 :()10 = ()2 自适应模型的阶 h(t) (t) gh(t) igh(t) 例文： the weight of ... 0阶 1阶 2阶 3阶 问题： 1. 半静态模型和自适应模型 2. 转义码的使用 3. 存储空间问题 LZ77算法 字典模型：《现代汉语词典》以及下面的例子 LZ77算法 LZ77算法的基本流程： “ 滑动的窗口 ” 从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。 输出三元符号组 (off,len,c)。 其中 off为窗口中匹配字符串相对窗口边界的偏移， len为可匹配的长度， c为下一个字符。 然后将窗口向后滑动 len+1个字符，继续步骤 1。 输出三元符号组 (0,0,c)。 其中 c为下一个字符。 然后将窗口向后滑动 len+1个字符，继续步骤 1。 LZ77算法 应用实例：窗口大小为 10个字符，刚编码过的 10个字符为 “ abcdbbccaa” ，即将编码的 10个字符为 “ abaeaaabaee”。 1. 我们首先发现，可以和待编码字符匹配的最长串为 ab(off=0,len=2), ab的下一个字符为 a， 我们输出三元组： (0,2,a) 2. 现在窗口向后滑动 3个字符，窗口中的内容为： dbbccaaaba 3. 下一个字符 e在窗口中没有匹配，我们输出三元组： (0,0,e) 4. 窗口向后滑动 1个字符，其中内容变为： bbccaaabae 5. 我们马上发现，要编码的 aaabae在窗口中存在 (off=4,len=6)， 其后的字符为 e， 我们可以输出： (4,6,e) 6. 这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。 7. 解压缩时，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c输出（如果 off和 len都为 0则只输出后继字符 c)即可还原出原始数据。 LZ77算法 三元组的编码方法（编码方式取决于数据的分布概率）： 1. 对于第一个分量 ——窗口内的偏移。