构造范式 Huffman 编码的方法大致是：
1) 统计每个要编码符号的频率。
2) 根据这些频率信息求出该符号在传统 Huffman 编码树中的深度（也就是表示该符号所需要的位数 - 编码长度）。因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度，具体方法这里就不详述了。
3) 分别统计从最大编码长度 maxlength 到 1 的每个长度对应了多少个符号。根据这一信息从 maxlength 个 0 开始以递增顺序为每个符号分配编码。例如，编码长度为 5 的符号有 4 个，长度为 3 的有 1 个，长度为 2 的有 3 个，则分配的编码依次为： 00000 00001 00010 00011 001 01 10 11
4) 编码输出压缩信息，并保存按照频率顺序排列的符号表，然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数。
现在完全可以不依赖任何树结构进行高速解压缩了。而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多。
最后要提到的是，Huffman 编码可以采用自适应模型，根据已经编码的符号频率决定下一个符号的编码。这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，使用范式 Huffman 编码是个不错的选择，但依然存在不少技术上的难题。幸好，如果愿意的话，我们可以暂时不考虑自适应模型的 Huffman 编码，因为对于自适应模型我们还有许多更好的选择，下面几章将要谈到的算术编码、字典编码等更为适合采用自适应模型，我们将在其中深入探讨自适应模型的各种实现方法。
我们在上一章中已经明白，Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右，压缩效果可想而知。
难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？是用剪刀把计算机存储器中的二进制位剪开吗？计算机真有这样的特异功能吗？慢着慢着，我们不要被表面现象所迷惑，其实，在这一问题上，我们只要换一换脑筋，从另一个角度……哎呀，还是想不通，怎么能是半个呢？好了，不用费心了，数学家们也不过是在十几年前才想到了算术编码这种神奇的方法，还是让我们虚心地研究一下他们究竟是从哪个角度找到突破口的吧。
输出：一个小数
更神奇的事情发生了，算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。
咦？怎么一会儿是表示半个二进制位，一会儿又是输出一个小数，算术编码怎么这么古怪呀？不要着急，我们借助下面一个简单的例子来阐释算术编码的基本原理。为了表示上的清晰，我们暂时使用十进制表示算法中出现的小数，这丝毫不会影响算法的可行性。
考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的信息为 bccb。
在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），没办法，我们暂时认为三者的出现概率相等，也就是都为 1/3，我们将 0 - 1 区间按照概率的比例分配给三个字符，即 a 从 0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到 1.0000。用图形表示就是：
+-- 1.0000
|
Pc = 1/3 |
|
+-- 0.6667
|
Pb = 1/3 |
|
+-- 0.3333
|
Pa = 1/3 |
|
+-- 0.0000
现在我们拿到第一个字符 b，让我们把目光投向 b 对应的区间 0.3333 - 0.6667。这时由于多了字符 b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。好，让我们按照新的概率分布比例划分 0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：
+-- 0.6667
Pc = 1/4 |
+-- 0.5834
|
|
Pb = 2/4 |
|
|
+-- 0.4167
Pa = 1/4 |
+-- 0.3333
接着我们拿到字符 c，我们现在要关注上一步中得到的 c 的区间 0.5834 - 0.6667。新添了 c 以后，三个字符的概率分布变成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我们用这个概率分布划分区间 0.5834 - 0.6667：
+-- 0.6667
|
Pc = 2/5 |
|
+-- 0.6334
|
Pb = 2/5 |
|
+-- 0.6001
Pa = 1/5 |
+-- 0.5834
现在输入下一个字符 c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。我们来划分 c 的区间 0.6334 - 0.6667：
+-- 0.6667
|
|
Pc = 3/6 |
|
|
+-- 0.6501
|
Pb = 2/6 |
|
+-- 0.6390
Pa = 1/6 |
+-- 0.6334
输入最后一个字符 b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b 的区间为 0.6390 - 0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0 和小数点，我们可以输出 1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程。
怎么样，不算很难吧？可如何解压缩呢？那就更简单了。解压缩之前我们仍然假定三个字符的概率相等，并得出上面的第一幅分布图。解压缩时我们面对的是二进制流 1010001111，我们先在前面加上 0 和小数点把它变成小数 0.1010001111，也就是十进制 0.64。这时我们发现 0.64 在分布图中落入字符 b 的区间内，我们立即输出字符 b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符 b 的区间。在新的划分中，我们发现 0.64 落入了字符 c 的区间，我们可以输出字符 c。同理，我们可以继续输出所有的字符，完成全部解压缩过程（注意，为了叙述方便，我们暂时回避了如何判断解压缩结束的问题，实际应用中，这个问题并不难解决）。
现在把教程抛开，仔细回想一下，直到你理解了算术压缩的基本原理，并产生了许多新的问题为止。
真的能接近极限吗？
现在你一定明白了一些东西，也一定有了不少新问题，没有关系，让我们一个一个解决。
首先，我们曾反复强调，算术压缩可以表示小数个二进制位，并由此可以接近无损压缩的熵极限，怎么从上面的描述中没有看出来呢？
算术编码实际上采用了化零为整的思想来表示小数个二进制位，我们确实无法精确表示单个小数位字符，但我们可以将许多字符集中起来表示，仅仅允许在最后一位有些许的误差。
结合上面的简单例子考虑，我们每输入一个符号，都对概率的分布表做一下调整，并将要输出的小数限定在某个越来越小的区间范围内。对输出区间的限定是问题的关键所在，例如，我们输入第一个字符 b 时，输出区间被限定在 0.3333 - 0.6667 之间，我们无法决定输出值得第一位是 3、4、5 还是 6，也就是说，b 的编码长度小于一个十进制位（注意我们用十进制讲解，和二进制不完全相同），那么我们暂时不决定输出信息的任何位，继续输入下面的字符。直到输入了第三个字符 c 以后，我们的输出区间被限定在 0.6334 - 0.6667 之间，我们终于知道输出小数的第一位（十进制）是 6，但仍然无法知道第二位是多少，也即前三个字符的编码长度在 1 和 2 之间。等到我们输入了所有字符之后，我们的输出区间为 0.6390 - 0.6501，我们始终没有得到关于第二位的确切信息，现在我们明白，输出所有的 4 个字符，我们只需要 1 点几个十进制位，我们唯一的选择是输出 2 个十进制位 0.64。这样，我们在误差不超过 1 个十进制位的情况下相当精确地输出了所有信息，很好地接近了熵值（需要注明的是，为了更好地和下面的课程接轨，上面的例子采用的是 0 阶自适应模型，其结果和真正的熵值还有一定的差距）。
小数有多长？
你一定已经想到，如果信息内容特别丰富，我们要输出的小数将会很长很长，我们该如何在内存中表示如此长的小数呢？
其实，没有任何必要在内存中存储要输出的整个小数。我们从上面的例子可以知道，在编码的进行中，我们会不断地得到有关要输出小数的各种信息。具体地讲，当我们将区间限定在 0.6390 - 0.6501 之间时，我们已经知道要输出的小数第一位（十进制）一定是 6，那么我们完全可以将 6 从内存中拿掉，接着在区间 0.390 - 0.501 之间继续我们的压缩进程。内存中始终不会有非常长的小数存在。使用二进制时也是一样的，我们会随着压缩的进行不断决定下一个要输出的二进制位是 0 还是 1，然后输出该位并减小内存中小数的长度。
静态模型如何实现？
我们知道上面的简单例子采用的是自适应模型，那么如何实现静态模型呢？其实很简单。对信息 bccb 我们统计出其中只有两个字符，概率分布为 Pb = 0.5，Pc = 0.5。我们在压缩过程中不必再更新此概率分布，每次对区间的划分都依照此分布即可，对上例也就是每次都平分区间。这样，我们的压缩过程可以简单表示为：
输出区间的下限 输出区间的上限
--------------------------------------------------
压缩前 0.0 1.0
输入 b 0.0 0.5
输入 c 0.25 0.5
输入 c 0.375 0.5
输入 b 0.375 0.4375
我们看出，最后的输出区间在 0.375 - 0.4375 之间，甚至连一个十进制位都没有确定，也就是说，整个信息根本用不了一个十进制位。如果我们改用二进制来表示上述过程的话，我们会发现我们可以非常接近该信息的熵值（有的读者可能已经算出来了，该信息的熵值为 4 个二进制位）。
为什么用自适应模型？
既然我们使用静态模型可以很好地接近熵值，为什么还要采用自适应模型呢？
要知道，静态模型无法适应信息的多样性，例如，我们上面得出的概率分布没法在所有待压缩信息上使用，为了能正确解压缩，我们必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。
另外还有最重要的一点，对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型得到的概率分布将有利于对信息的压缩（可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上，其总熵值更小），好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。
自适应模型的阶
我们通常用“阶”(order)这一术语区分不同的自适应模型。本章开头的例子中采用的是 0 阶自适应模型，也就是说，该例子中统计的是符号在已输入信息中的出现概率，没有考虑任何上下文信息。
如果我们将模型变成统计符号在某个特定符号后的出现概率，那么，模型就成为了 1 阶上下文自适应模型。举例来说，我们要对一篇英文文本进行编码，我们已经编码了 10000 个英文字符，刚刚编码的字符是 t，下一个要编码的字符是 h。我们在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 t，其中有 47 个 t 后面跟着字母 h。我们得出字符 h 在字符 t 后的出现频率是 47/113，我们使用这一频率对字符 h 进行编码，需要 -log2(47/113) = 1.266 位。
对比 0 阶自适应模型，如果前 10000 个字符中 h 的出现次数为 82 次，则字符 h 的概率是 82/10000，我们用此概率对 h 进行编码，需要 -log2(82/10000) = 6.930 位。考虑上下文因素的优势显而易见。
我们还可以进一步扩大这一优势，例如要编码字符 h 的前两个字符是 gt，而在已经编码的文本中 gt 后面出现 h 的概率是 80%，那么我们只需要 0.322 位就可以编码输出字符 h。此时，我们使用的模型叫做 2 阶上下文自适应模型。
最理想的情况是采用 3 阶自适应模型。此时，如果结合算术编码，对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统空间和时间至少在目前还无法让人接受，使用算术压缩的应用程序大多数采用 2 阶或 3 阶的自适应模型。
转义码的作用
使用自适应模型的算术编码算法必须考虑如何为从未出现过的上下文编码。例如，在 1 阶上下文模型中，需要统计出现概率的上下文可能有 256 * 256 = 65536 种，因为 0 - 255 的所有字符都有可能出现在 0 - 255 个字符中任何一个之后。当我们面对一个从未出现过的上下文时（比如刚编码过字符 b，要编码字符 d，而在此之前，d 从未出现在 b 的后面），该怎样确定字符的概率呢？
比较简单的办法是在压缩开始之前，为所有可能的上下文分配计数为 1 的出现次数，如果在压缩中碰到从未出现的 bd 组合，我们认为 d 出现在 b 之后的次数为 1，并可由此得到概率进行正确的编码。使用这种方法的问题是，在压缩开始之前，在某上下文中的字符已经具有了一个比较小的频率。例如对 1 阶上下文模型，压缩前，任意字符的频率都被人为地设定为 1/65536，按照这个频率，压缩开始时每个字符要用 16 位编码，只有随着压缩的进行，出现较频繁的字符在频率分布图上占据了较大的空间后，压缩效果才会逐渐好起来。对于 2 阶或 3 阶上下文模型，情况就更糟糕，我们要为几乎从不出现的大多数上下文浪费大量的空间。
我们通过引入“转义码”来解决这一问题。“转义码”是混在压缩数据流中的特殊的记号，用于通知解压缩程序下一个上下文在此之前从未出现过，需要使用低阶的上下文进行编码。
举例来讲，在 3 阶上下文模型中，我们刚编码过 ght，下一个要编码的字符是 a，而在此之前，ght 后面从未出现过字符 a，这时，压缩程序输出转义码，然后检查 2 阶的上下文表，看在此之前 ht 后面出现 a 的次数；如果 ht 后面曾经出现过 a，那么就使用 2 阶上下文表中的概率为 a 编码，否则再输出转义码，检查 1 阶上下文表；如果仍未能查到，则输出转义码，转入最低的 0 阶上下文表，看以前是否出现过字符 a；如果以前根本没有出现过 a，那么我们转到一个特殊的“转义”上下文表，该表内包含 0 - 255 所有符号，每个符号的计数都为 1，并且永远不会被更新，任何在高阶上下文中没有出现的符号都可以退到这里按照 1/256 的频率进行编码。
“转义码”的引入使我们摆脱了从未出现过的上下文的困扰，可以使模型根据输入数据的变化快速调整到最佳位置，并迅速减少对高概率符号编码所需要的位数。
存储空间问题
在算术编码高阶上下文模型的实现中，对内存的需求量是一个十分棘手的问题。因为我们必须保持对已出现的上下文的计数，而高阶上下文模型中可能出现的上下文种类又是如此之多，数据结构的设计将直接影响到算法实现的成功与否。
在 1 阶上下文模型中，使用数组来进行出现次数的统计是可行的，但对于 2 阶或 3 阶上下文模型，数组大小将依照指数规律增长，现有计算机的内存满足不了我们的要求。
比较聪明的办法是采用树结构存储所有出现过的上下文。利用高阶上下文总是建立在低阶上下文的基础上这一规律，我们将 0 阶上下文表存储在数组中，每个数组元素包含了指向相应的 1 阶上下文表的指针，1 阶上下文表中又包含了指向 2 阶上下文表的指针……由此构成整个上下文树。树中只有出现过的上下文才拥有已分配的节点，没有出现过的上下文不必占用内存空间。在每个上下文表中，也无需保存所有 256 个字符的计数，只有在该上下文后面出现过的字符才拥有计数值。由此，我们可以最大限度地减少空间消耗。
资源
关于算术压缩具体的设计和实现请参考下面给出的示例程序。
程序 Arith-N 由 League for Programming Freedom 的 Mark Nelson 提供，由王笨笨在 Visual C++ 5.0 环境下编译、调试通过。
Arith-N 包含 Visual C++ 工程 ArithN.dsp 和 ArithNExpand.dsp，分别对应了压缩和解压缩程序 an.exe 与 ane.exe。
Arith-N 是可以在命令行指定阶数的 N 阶上下文自适应算术编码通用压缩、解压缩程序，由于是用作教程示例，为清晰起见，在某些地方并没有刻意进行效率上的优化。
所有源程序包装在文件
点击浏览该文件 中。
全新的思路
我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。
我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了 Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。
说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的。
最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，对每一个独立的词语，我们在《现代汉语词典》查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法了。
你一定可以发现，静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。所以，几乎所有通用的字典模型都使用了自适应的方式，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？
啊，对了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。现在你该大致明白自适应字典模型的梗概了吧。好了，下面就让我们来深入学习字典模型的第一类实现——LZ77 算法。
滑动的窗口
LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。
参照下图，让我们熟悉一下 LZ77 算法的基本流程。
1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。
3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。
我们结合实例来说明。假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee
我们首先发现，可以和要编码字符匹配的最长串为 ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：( 0, 2, a )
现在窗口向后滑动 3 个字符，窗口中的内容为：dbbccaaaba
下一个字符 e 在窗口中没有匹配，我们输出三元组：( 0, 0, e )
窗口向后滑动 1 个字符，其中内容变为：bbccaaabae
我们马上发现，要编码的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字符为 e，我们可以输出：( 4, 6, e )
这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。
解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符 c )即可还原出原始数据。
当然，真正实现 LZ77 算法时还有许多复杂的问题需要解决，下面我们就来对可能碰到的问题逐一加以探讨。
编码方法
我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口大小（例如 4096 字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定的位数来表示它。
编码 off 需要的位数 bitnum = upper_bound( log2( MAX_WND_SIZE ))
由此，如果窗口大小为 4096，用 12 位就可以对偏移编码。如果窗口大小为 2048，用 11 位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有达到 MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动态计算所需要的位数，这样可以略微节省一点空间。
对于第二个分量——字符串长度，我们必须考虑到，它在大多数时候不会太大，少数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。在前面我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我在这里介绍其中两种应用非常广泛的编码。
第一种叫 Golomb 编码。假设对正整数 x 进行 Golomb 编码，选择参数 m，令
b = 2m
q = INT((x - 1)/b)
r = x - qb - 1
则 x 可以被编码为两部分，第一部分是由 q 个 1 加 1 个 0 组成，第二部分为 m 位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的 Golomb 编码表列出：
值 x m = 0 m = 1 m = 2 m = 3
-------------------------------------------------------------
1 0 0 0 0 00 0 000
2 10 0 1 0 01 0 001
3 110 10 0 0 10 0 010
4 1110 10 1 0 11 0 011
5 11110 110 0 10 00 0 100
6 111110 110 1 10 01 0 101
7 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
从表中我们可以看出，Golomb 编码不但符合前缀编码的规律，而且可以用较少的位表示较小的 x 值，而用较长的位表示较大的 x 值。这样，如果 x 的取值倾向于比较小的数值时，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规律不同，我们可以选取不同的 m 值以达到最好的压缩效果。
对我们上面讨论的三元组 len 值，我们可以采用 Golomb 方式编码。上面的讨论中 len 可能取 0，我们只需用 len + 1 的 Golomb 编码即可。至于参数 m 的选择，一般经验是取 3 或 4 即可。
可以考虑的另一种变长前缀编码叫做 γ 编码。它也分作前后两个部分，假设对 x 编码，令 q = int( log2x )，则编码的前一部分是 q 个 1 加一个 0，后一部分是 q 位长的二进制数，其值等于 x - 2q 。γ编码表如下：
值 x γ编码
---------------------
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
其实，如果对 off 值考虑其倾向于窗口后部的规律，我们也可以采用变长的编码方法。但这种方式对窗口较小的情况改善并不明显，有时压缩效果还不如固定长编码。
对三元组的最后一个分量——字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。
根据上面的叙述，相信你一定也能写出高效的编码和解码程序了。
另一种输出方式
LZ77 的原始算法采用三元组输出每一个匹配串及其后续字符，即使没有匹配，我们仍然需要输出一个 len = 0 的三元组来表示单个字符。试验表明，这种方式对于某些特殊情况（例如同一字符不断重复的情形）有着较好的适应能力。但对于一般数据，我们还可以设计出另外一种更为有效的输出方式：将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。
我们将每一个输出分成匹配串和单个字符两种类型，并首先输出一个二进制位对其加以区分。例如，输出 0 表示下面是一个匹配串，输出 1 表示下面是一个单个字符。
之后，如果要输出的是单个字符，我们直接输出该字符的字节值，这要用 8 个二进制位。也就是说，我们输出一个单个的字符共需要 9 个二进制位。
如果要输出的是匹配串，我们按照前面的方法依次输出 off 和 len。对 off，我们可以输出定长编码，也可以输出变长前缀码，对 len 我们输出变长前缀码。有时候我们可以对匹配长度加以限制，例如，我们可以限制最少匹配 3 个字符。因为，对于 2 个字符的匹配串，我们使用匹配串的方式输出并不一定比我们直接输出 2 个单个字符（需要 18 位）节省空间（是否节省取决于我们采用何种编码输出 off 和 len）。
这种输出方式的优点是输出单个字符的时候比较节省空间。另外，因为不强求每次都外带一个后续字符，可以适应一些较长匹配的情况。
如何查找匹配串
在滑动窗口中查找最长的匹配串，大概是 LZ77 算法中的核心问题。容易知道，LZ77 算法中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后，都要进行下一个匹配串的查找，如果查找算法的时间效率在 O(n2) 或者更高，总的算法时间效率就将达到 O(n3)，这是我们无法容忍的。正常的顺序匹配算法显然无法满足我们的要求。事实上，我们有以下几种可选的方案。
1、限制可匹配字符串的最大长度（例如 20 个字节），将窗口中每一个 20 字节长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字符串的查找，其效率是很高的。树中每一个节点大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。树中共有 MAX_WND_SIZE - 19 个节点，假如窗口大小为 4096 字节，树的大小大约是 130k 字节。空间消耗也不算多。这种方法对匹配串长度的限制虽然影响了压缩程序对一些特殊数据（又很长的匹配串）的压缩效果，但就平均性能而言，压缩效果还是不错的。
2、将窗口中每个长度为 3 （视情况也可取 2 或 4）的字符串建立索引，先在此索引中匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符串。因为长度为 3 的字符串可以有 2563 种情况，我们不可能用静态数组存储该索引结构。使用 Hash 表是一个明智的选择。我们可以仅用 MAX_WND_SIZE - 1 的数组存储每个索引点，Hash 函数的参数当然是字符串本身的 3 个字符值了，Hash 函数算法及 Hash 之后的散列函数很容易设计。每个索引点之后是该字符串出现的所有位置，我们可以使用单链表来存储每一个位置。值得注意的是，对一些特殊情况比如 aaaaaa...之类的连续字串，字符串 aaa 有很多连续出现位置，但我们无需对其中的每一个位置都进行匹配，只要对最左边和最右边的位置操作就可以了。解决的办法是在链表节点中纪录相同字符连续出现的长度，对连续的出现位置不再建立新的节点。这种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺点是查找耗时多于第一种方法。
3、使用字符树( trie )来对窗口内的字符串建立索引，因为字符的取值范围是 0 - 255，字符树本身的层次不可能太多，3 - 4 层之下就应该换用其他的数据结构例如 Hash 表等。这种方法可以作为第二种方法的改进算法出现，可以提高查找速度，但空间的消耗较多。
如果对窗口中的数据进行索引，就必然带来一个索引位置表示的问题，即我们在索引结构中该往偏移项中存储什么数据：首先，窗口是不断向后滑动的，我们每次将窗口向后滑动一个位置，索引结构就要作相应的更新，我们必须删除那些已经移动出窗口的数据，并增加新的索引信息。其次，窗口不断向后滑动的事实使我们无法用相对窗口左边界的偏移来表示索引位置，因为随着窗口的滑动，每个被索引的字符串相对窗口左边界的位置都在改变，我们无法承担更新所有索引位置的时间消耗。
解决这一问题的办法是，使用一种可以环形滚动的偏移系统来建立索引，而输出匹配字符串时再将环形偏移还原为相对窗口左边界的真正偏移。让我们用图形来说明，窗口刚刚达到最大时，环形偏移和原始偏移系统相同：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 0 1 2 3 4 ...... Max
窗口向后滑动一个字节后，滑出窗口左端的环形偏移 0 被补到了窗口右端：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 1 2 3 4 5 ...... Max 0
窗口再滑动 3 个子节后，偏移系统的情况是：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 4 5 6 7 8...... Max 0 1 2 3
依此类推。
我们在索引结构中保存环形偏移，但在查找到匹配字符串后，输出的匹配位置 off 必须是原始偏移（相对窗口左边），这样才可以保证解码程序的顺利执行。我们用下面的代码将环形偏移还原为原始偏移：
// 由环形 off 得到真正的off(相对于窗口左边)
// 其中 nLeftOff 为当前与窗口左边对应的环形偏移值
int GetRealOff(int off)
{
if (off >= nLeftOff)
return off - nLeftOff;
else
return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}
这样，解码程序无需考虑环形偏移系统就可以顺利高速解码了。
资源
结合上面的讨论，典型的 LZ77 算法应当不难实现，我们本章给出的源码是一个较为特殊的实现。
示例程序 lz77.exe 使用对匹配串和单个字符分类输出的模型，输出匹配串时，off 采用定长编码，len 采用γ编码。索引结构采用 2 字节长字符串的索引，使用 256 * 256 大小的静态数组存储索引点，每个索引点指向一个位置链表。链表节点考虑了对 aaaaa... 之类的重复串的优化。
示例程序的独特之处在于使用了 64k 大小的固定长度窗口，窗口不做滑动（因此不需要环形偏移系统，也节省了删除索引点的时间）。压缩函数每次只对最多 64k 长的数据进行压缩，主函数将原始文件分成 64k 大小的块逐个压缩存储。使用这种方法首先可以增大匹配的概率，字符串可以在 64k 空间内任意寻找最大匹配串，以此提高压缩效率。其次，这种方法有利于实现解压缩的同步。也就是说，利用这种方法分块压缩的数据，很容易从原始文件中间的任何一个位置开始解压缩，这尤其适用于全文检索系统中全文信息的保存和随机读取。
结合上述示例程序，王笨笨开发了可压缩多个文件并可同步（随机）解压缩的文件级接口，但此接口并非自由代码(free code)。如果需要可以和王笨笨联系。
示例程序 lz77 的所有源文件被包装在文件
点击浏览该文件 中，由王笨笨编写，在 Visual C++ 5.0 环境下编译通过。其使用方法是：
压缩： lz77 c 源文件名 压缩文件名
解压缩： lz77 d 压缩文件名 源文件名
LZ78 的算法描述：
for (;;)
{
current_match = 1;
current_length = 0;
memset(test_string, '\0', MAX_STRING);
for (;;)
{
test_string[current_length ++] = getc(input);
new_match = find_match(test_string);
if (new_match) == -1)
break;
current_match = new_match;
}
output_code(current_match);
output_char(test_string[current_letgth - 1];
add_string_to_dictionary(test_string);
}
LZ78 示例：
输入正文： "DAD DADA DADDY DADO..."
输出短语 输出字符 编码后的串
0 'D' "D"
0 'A' "A"
1 ' ' "D"
1 'A' "DA"
4 ' ' "DA "
4 'D' "DAD"
1 'Y' "DY"
0 ' ' " "
6 'O' "DADO"
此时字典的情况：
0 ""
1 "D"
2 "A"
3 "D "
4 "DA"
5 "DA "
6 "DAD"
7 "DY"
8 " "
9 "DADO"
(待续)
加好友 
发短信
Post By：2005/4/30 2:48:00
