寻找序列的变化内容  

Discover difference between sequences

作　　者：张晓敏[1] 陈昊[1] 明仲[1] 

机构地区：[1]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机工程与应用》2011年第31期49-52,62,共5页Computer Engineering and Applications

基　　金：深港创新圈项目(No.ZYB200907060012A);广东省自然科学基金项目(No.10351806001000000)

摘　　要：寻找两个序列X、Y的差异内容,产生Y相对X的差异信息Z,使得X能够根据Z变化为Y。如果X、Y是同一种文件的不同版本,Z往往比Y小得多,这样存储或传送Z将比直接存储或传送Y更节约资源。提出一种基于序列结构因素的启发式算法,对两个序列进行划分,再进行相同内容的匹配。算法时间复杂度为O((n+m)log(min(n,m))),空间复杂度为O(n+m),其中n、m分别为X、Y的长度。在实际应用中该算法的执行速度是接近线性的。To discover the difference Z between two sequences,named X and Y,it changes X to Y through the difference information Z.If X and Y are two different versions of the same file,Z is much smaller than X.Therefore,it is a good idea to store or transfer Z instead of X.To solve that problem,X and Y can be both separated into several parts and the corresponding parts can be treated as sub-problems.In the same time the sub-sequences that are the same can be discovered.The algorithm＇s implementation takes O（（n＋m）log（min（n,m））） time and O（n＋m） space,in which n and m are the length of X and Y,respectively.

关 键 词：差异算法 最长公共子序列 差异 变化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]