最近做了一个差量更新工具， 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后，根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是，为了尽可能的减少网络传输，patch文件需要尽可能的小，并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑，我重新设计了一个二进制patch格式，整个patch文件中有两种Action（分别是COPY， INSERT)，大致数据结构如下：

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据（这代表这段数据在文件a中找不到)。

之所以不需要新文件的位置，是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时，我遇到了一个问题.

即，如何快速找到，同时存在于文件a和文件b中的最长子串。算法导论上的LCS（公共子序列）算法并不是很适合我，因为COPY只是去借数据，并不在乎这块数据在哪个位置。

最终发现，有序后缀数组更符合我的需求，空间复杂度极底，并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3，我搞了将近2周才总算搞明白。

整个算法一共就分4步，原始数据在buf中，长度为N，（这里仅粗略描述)：

1. 将(i % 3 != 0， i >= 0 and i < N)的值取出来放到一个数组SA12中.

2. 对S12进行排序, S12中的每个值n都代表一个三元组（buf[n],buf[n+1],buf[n+2]），排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

3. 如果任意两个三元组都不相等，说明仅凭前三个字母就可以对后缀确定顺序，则直接执行步骤4。否则，对s12中的数据递归执行DC3。

4. 根据s12来生成数组SA12，然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序，与SA12进行有序合并，成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的，如快排，二分查找，甚至红黑树那么直观。他神奇到，我完全不知道这是在做什么，后缀数组已经排完序了。

在看这个算法时，在第2步我有几个很大的疑惑。

一是有个很神奇的操作，在生成s12的时，如果n % 3 ==1, 要把rank值放左边，n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的（没有空洞x, buf[x]会比buf数组中所有值都要小)，就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字，2行不行。

搞明白之后发现，整个算法的核心思想就是"收敛", 运用递归的思想不断的收敛，直到比如结果为止。举个例子：

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】]，

将n%3==1的放左边，n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x，而buf[x]一定比buf[0~n]中的值都要小，所以就不用插入分隔符了，后面会看到分隔符的作用。

从上面列表可以看出’1,2,3′ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序（不满足步骤3)，因为要接着递归执行，先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到，之所以要把i%3==1的放左边，i%3==2放右边，其实是为再次递归DC3做准备。第二次递归DC3，实质上是取所有后缀的前9个前缀来进行排序，如果还有相同的，则再次递归采用前27个前缀进行排序，直到排出顺序为止。

为了利用上次递归的结果，上面数组会被转化成转换之后（【3】【3】【2】【1】【5】【5】，【4】）再递归传入DC3。

而之所以要插分隔符，其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2，3，4’参与排序，毕间7，8，9，10已经是从位置7开始后缀子串的全部内容了，如果2，3，4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字，其实跟步骤4是有关系的。

在步骤4进行有序合并时，i%3==1时，会将3元组扩展成4元组，i%3==2时，将3元组扩展成5元组，之后再比较。

当i%3==1时，如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了，所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较，由于s12[1]中的值各不相同，因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3′, ‘2,3,4,5’，可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组，‘0,1,2,3,4′,’2,3,4,5,6’，这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里，为什么不用2就很明显了，因为在最后一步合并时2不满足重用上一步结果的要求。

总的来说这是一个很神奇的算法，有动态规划的影子，各个步骤又配合的天衣无缝。