概述

游程编码有两种变形，分别是“图编码”和“模式替换算法”。图编码是一种非常简单的算法，它不像游程编码那样必须要求输入字符串中必须含有很多重复的元素，比如“aaaaaa”。这些情况在自然语言中很少出现，但是被称之为“图”的字符串几乎会出现在所有自然语言中。日常英语中就有些图，例如“the”，“and”，“ing”（例如在“waiting”中），“aa”，“tt”，“ee”这些双字母。事实上我们可以通过添加字符串两边的空格来扩展这些图。这样我们可以不编码“the”，而编码“ the ”，就可以编码5个字符了（3个字符，2个空格），从而获得更好的压缩率。另一方面，在日常英语中有很多包含双字母的字符串，而这些情况在游程编码中并不能有效地被压缩，这样导致压缩效率非常低。有时候会有更加糟糕的情况出现，压缩后的长度比原来的长度还要长。我们看一些例子：

我们谈一谈怎么编码这个包含了四对双字母的字符串“successfully accomplished”。很不幸，如果用游程编码的话，压缩这四对双字母至少需要八个字符，这意味着对压缩数据来说没有任何帮助。

这里有个问题，如果原本的输入字符串中含有数字的话，比如“2”，那么我们必须指定一个字符（比如“@”）用来描述我们编码替换开始的位置。那么如果输入的字符串为“2 successfully accomplished tasks”，压缩之后就变为“2 su@2ce@2sfu@2ly a@2complished tasks”，这时候输出的字符串比输入的字符串还要长！

如果输入的字符串中包含转义字符，我们必须找到另一个，然后问题就来了：若不进行全局查找，我们就很难找到另外一个出现在输入字符串中的转义字符。

游程编码在压缩纯文本的时候并不是一个好的解决方案，因为长的重复情况（“aaaaa”）出现频率太小了。当然，在失真压缩的时候是一个特例。很明显，当你要求解压出来的文本需要是完全一致的时候，失真压缩文本并没有很大用处。但是有时候失真压缩可能有用，比如在我们要去除空格的情况中。字符串“successfully           accomplished”表达的意思和“successfully accomplished”确实完全相同。在这种情况下，我们能够很简单地去除那些空格。我们可以像这样用一个标记去代替一长串的空格：“successfully@6 accomplished”，这样可以使输入字符串完全没有损失，但是我们也有另一种选择，可以直接把那些空格直接扔掉。这个选择取决于我们的目的是什么，只有当我们很确定删除换行标记符和制表标记符能够完全保证表达出相同的意思时，才能下决定扔掉那些空格。但是话又说回来，现实中出现这种问题的情况也是少数，所以对纯文本压缩选择图压缩方法比游程编码更好。

问题

在理解了图编码的基本规则之后，让我们看一些例子。在上面的例子中，最好的替代双字母的方法是，用“#”符号替代“cc”，用“@”替代“ss”，用“%”替代“ll”。这样的话输入字符串就可以表示为“su#e@fu%y a#omplished”，这样就可以比输入字符串短了。但是如果输入字符串中包含“# @ %”这些符号怎么办呢？而且我们也不能确定的说在输入字符串中有足够多的双字母让我们有理由去替换它们。一个更好的方式是模式替换。

游程编码对普通文本压缩并不是一个好的方法，因为长重复很少在自然语言中出现。

模式替换

模式替换算法是图编码的一种变形。我在上面说过，在日常英语中“ the ”这种单词会经常出现。我们现在可以把它替换为类似于“$%”这样的字符。如果输入字符串是“I send the message”，那么压缩之后变成了“I send$%message”。但是这种方法也有一些缺陷。

第一个问题是我们需要知道了解将要被压缩的这门语言，而且我们要定义出来哪些模式是经常被使用的。如果一条信息用我们完全不懂的语言写的。比如下面的拉丁文：

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras venenatis, sapien eget suscipit placerat, justo quam blandit mauris, quis tempor ante sapien sodales augue. Praesent ut mauris quam. Phasellus scelerisque, ante quis consequat tristique, metus turpis consectetur leo, vitae facilisis sapien mi eu sapien. Praesent vitae ligula elit, et faucibus augue. Sed rhoncus sodales dolor ut gravida. In quis augue ac nulla auctor mattis sed sed libero. Donec eget purus eget enim tempor porta vitae eget diam. Mauris aliquet malesuada ipsum, non pulvinar urna vestibulum ac. Donec feugiat velit vitae nunc cursus imperdiet. Donec accumsan faucibus dictum. Phasellus sed mauris sapien. Maecenas mi metus, tincidunt sed rhoncus nec, sodales non sapien.

很明显，如果我们不懂拉丁文，那么定义出来一个常用模式会十分困难。所以如果我们事先知道一些单词或者字母的话，会让我们更方便运用模式替换。

第二个问题是关于解压缩。我们需要构造一个用来解压缩的字典。如果我们能够找到比三个字母长的模式会非常好。但是如果找不到，那么压缩率会比较低。而不幸的是，这种长的（3个字符以及3个以上的）模式在自然语言中很少出现。

在压缩纯文本的情况下，图编码和模式替换都要优于游程编码。而且，模式替换在压缩编程语言的情况下十分高效。

应用

一个很有趣的问题是，怎么使用图编码和模式替换算法压缩纯文本，特别是当我们不太了解被压缩文本使用的语言时。答案其实就在问题中，我们可以不压缩自然语言，转而压缩编程语言。因为编程语言限制了一个有限的小单词和符号集合。它几乎对任何编程语言都适用。比如PHP，“function”，“while”，“for”，“break”，“switch”，“foreach”都是经常用的，或者在HTML中，有很多常用的标签。也许最好的例子是CSS，在CSS中只有属性值能够变化。CSS文件中也经常有很多为了提高可读性的换行符，制表符以及空格。

这里就有一个问题，很明显压缩之后的文件对程序员和计算机来说都完全不能发挥作用了，那么为什么我们要压缩这些文件呢。确实是这样，但是如果我们要把不同版本的文件存入数据库作为备份呢。想象一下你正在为一个网站托管公司工作，每天要存储大量托管网站的备份文件。即使只是一个小的网站托管网站上面只有少量的托管网站，那备份文件也是一个惊人的数量。用一个简易压缩工具压缩那些文件显然不是一个好主意。我们每天都必须要备份整个网站，但是我们知道每天网站的版本更新的地方非常少。版本控制系统是一个解决方案，但是你必须去存储那些纯文本文件。

也许一个好方法是运用相对编码：用模式替换去压缩这些文本，而且只记录变化更新的部分——类似于版本控制。

运用上面的方法我们能够节省很多磁盘空间，而且我们能够很方便进行压缩和解压缩。另外一个好处是你可以类似于版本控制把所有的更改保存到原始的文件中，而这个文件也可以被压缩。

实现

这个算法的实现也是基于PHP，希望能够描述这个压缩算法的主要思想，在这个例子中我试图利用上面的压缩方法压缩一个CSS文件。虽然这个例子非常简单，但是我们仍然能看到很多有趣的地方。首先你只需要一个压缩和解压缩的字典。在实际中这个压缩过程和解压缩过程是相同的，所以你不需要去写两个不同的函数。在这里用了一个原生的PHP函数“str_replace”[1]，因为这个算法的目的不是介绍实现模式替换的技术细节，而是描述模式替换的思想。所以我们假定编程语言有操作字符串的特定函数。