计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (31): 49-52.
• 研究、探讨 • 上一篇 下一篇
张晓敏，陈 昊，明 仲
收稿日期:
修回日期:
出版日期:
发布日期:
ZHANG Xiaomin，CHEN Hao，MING Zhong
Received:
Revised:
Online:
Published:
摘要： 寻找两个序列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的长度。在实际应用中该算法的执行速度是接近线性的。
关键词: 差异算法, 最长公共子序列, 差异, 变化
Abstract: 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.
Key words: differencing algorithm, Longest Common Subsequence（LCS）, difference, change
张晓敏，陈 昊，明 仲. 寻找序列的变化内容[J]. 计算机工程与应用, 2011, 47(31): 49-52.
ZHANG Xiaomin，CHEN Hao，MING Zhong. Discover difference between sequences[J]. Computer Engineering and Applications, 2011, 47(31): 49-52.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/
http://cea.ceaj.org/CN/Y2011/V47/I31/49
