一个高效的二进制数据补丁算法(原创)
作者: HouSisong@263.net 2006.04.11
补丁算法在很多地方都很有用,可以用来制作发布软件的升级包、不同版本源代码的增量备份、数据的增量储存等等;这里介绍一种原创的高效的二进制数据补丁算法。
对于文本文件,按行来处理可能是一种直观的方案:求出新数据和老数据相比增加的行、删除的行、修改的行等等;但这种算法对于一般的二进制数据不太适用,本文给出的是一个以二进制数据为对象的解决办法(当然它也能够很好的处理文本文件);
补丁算法简单来说就是求出两个数据块不一致的地方;这些不一致描述起来可能包括(有重叠):保留的数据、增加的数据、删除的数据、修改的数据、移动的数据等。本算法只使用保留的数据和增加的数据来表示这种不一致(注意,这种表示是完备的!)。 设原来的数据块为OldData,新的数据块为NewData,两个数据之间应该有很多相同的数据段(否则就直接拷贝,不用打补丁了);现在要求求出一个数据差PatchData,它能够在只有OldData和PatchData的情况下重新生成NewData;
算法的前提和假设:假设两个数据块为OldData大小M字节,NewData大小N字节;OldData和NewData有很多相同的数据段;如果我们构造一个 N(宽)*M(高) 大小的只包含false和true的布尔值矩阵E,令矩阵中i,j处的的元素值E[i,j],E[i,j]=(NewData[i]==OldData[j]); (注意:矩阵E不一定要实际生成,因为它的元素值很容易得到); (这时E的(0,0)点在左上角,(N-1,M-1)点在右下角;)
矩阵E中相邻的连续的true值将组成很多的直线段;对于这些直线段推理可以得知: 横线“-”是没有任何意义的(说明OldData中有一段数据由单个字符组成),竖线“|”对于最后的压缩效果意义不大(说明NewData中有一段数据由单个字符组成),右斜线'/'说明有一段NewData和一段OldData数据正好顺序颠倒(一般的应用中假设它很少见而不考虑);那么算法现在的任务就是要在矩阵E中找到多条由true组成的连续左斜线'\',并且这些左斜线长度大于一个常数(我得到的经验值为7,更短的直线段意义不大);在这些左斜线中找出对“覆盖”NewData最佳的一种直线组合;那么补丁数据PatchData将由这些直线数据和NewData中没有被覆盖到的数据所组成; 理论上这将得到最好的补丁数据!
找出满足要求的左斜线的算法:建立OldData的后缀数组OldDataStr,然后用NewData来匹配,从而找出所有的匹配(即左斜线); (尝试过使用后缀树,算法复杂度线性O(N),速度会快一点,但内存消耗太大了;其实N*log2(N)的算法也不慢:)
算法伪代码:
int NodeSize=1;//增大NodeSize的值可以减小内存需求,加快速度,但得到的PatchData会稍大一点
OldDataStr=new (*Byte)[M/NodeSize];
for (i=0 to (OldDataSize/NodeSize)-1) OldDataStr[i]=&OldData[i*NodeSize];
QuickSortAsString(OldDataStr);//排序后缀数组;排序方法是把元素OldDataStr[i]看作是从OldDataStr[i]开始到&OldData[M]结束的数据字符串(注意可以有0),按字符串大小排序;(这里是最耗时的操作,可以做一些排序优化)
it=&NewData[0];//将it看作从it开始到&NewData[N]结束的数据字符串;
while (it<&NewData[N])
{
itfinded=FindInOldDataStr(it);//在OldDataStr表中查找it字符串的插入位置;C++中可以利用LowerBound
itfinded=BestEqualLength(itfinded)//在itfinded字典位置附近得到最接近it的位置;也就是最长的相同字符串前缀(其他长度的舍弃)
if (EqualLength(itfinded,it)>AConstLength)// AConstLength=7,它体现分段代价
AddOldLine(it,itfinded)//找到了NewData中的一段数据可以用OldData中的数据代替
++it;
}
处理左斜线:令找到的所有左斜线为集合L,现在的任务是找到一条穿过这些直线的最佳路径;(先对L进行排序)如果其中一条线a完全覆盖另一条线b,则从L中删除b;如果a,b两个线段在一条直线上,并且间隔很小,则他们是可以优化的(优化方法是:把它们联接成一条直线段,中间的间隔部分对应的NewData数据同样需要放到PatchData中),对于不容易优化的独立直线,并且比较短(经验值18),可以从L中删除;对于没有重叠的线段,直接选为路径直线段,对于有重叠的线段,需要计算通过它们的各种组合所产生的大小代价(带权值的路径搜索);简单处理的话也可以一次只处理少量重叠的线段,毕竟重叠出现的不多;
生成补丁数据PatchData:将路径直线段数据保存到PacthData中,将没有被直线段覆盖的NewData数据拷贝到PatchData中;
考虑中的改进:为exe文件作优化,利用exe文件的特点(就是大量偏移地址),先做一些处理,然后再使用上面的算法。
数据还原算法: 输入PatchData和OldData,输出NewData。 按PatchData的直线段描述从OldData中拷贝数据到新的NewData数据区中,然后拷贝PachData中保存的NewData数据到现在的NewData数据区中,完成。
( 我使用过VPatch,它是一个开放源代码的补丁工具,二进制压缩,很好用,在inno安装工具中也有使用,压缩效果还不错;地址:http://www.tibed.net/vpatch/
我的算法产生的补丁数据(一些游戏程序)和VPatch产生的补丁数据在压缩后比较,压缩率比VPatch高40%左右! 速度也快出很多!
)