分享
 
 
 

一个高效的二进制数据补丁算法

王朝other·作者佚名  2007-01-22
窄屏简体版  字體: |||超大  

一个高效的二进制数据补丁算法(原创)

作者: 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%左右! 速度也快出很多!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有