证明:通过(3-3),能够找出(i,j)的所有直接后继匹配点 (。根据方法(3-1),TX(k,i)是字符序列X中的之后关于CH(k)最近的匹配字符位置,TY(k,j)也是同样意思。这就意味着匹配点(包括了(i,j)所有的直接后继匹配点。通过重复上述操作,能得到(i,j)的所有后继点。

很明显,(是字符序列X,Y的初始匹配点。通过定理2,可知从初始匹配点出发,能够得到所有匹配点和他们对应的层次。

3。1。2 裁剪操作

在产生后继匹配点的过程中,需要用裁剪操作出去不能产生LCS的匹配点,从而能减少搜索的空间和提高效率。

裁剪操作1:如果在相同一层,有两个匹配点(i,j)和(k,l)满足(k,l)>(i,j),移除(k,l)并不影响算法的正确性。

基本原理:移除(k,l)的理由如下。假设两个匹配点(i,j)和(k,l)是通过上一层匹配点生成的。让LCS通过,这里代表。同样的,让LCS通过,这里代表。假如,(k,l)>(i,j),根据定理2,(k,l)一定在(i,j)之后产生。存在对应(k,l),假如和都是根据(k,l)产生的最长公共子序列,,q-s=r-(m+1),q=r+s-(m+1),s>m+1,则q>r。因此并不在LCS中,可以删去。

剪裁操作可以移除所有的无用的匹配点。在每一层的匹配点产生后,算法会检查所有同一层的新产生的匹配点,比如(i,j)和(k,l)满足(k,l)>(i,j),则可移除(k,l)。

在例子1中(4,6)和(5,7)都是(2,5)的后继匹配点,因为他们在同一层,而且(4,6)>(5,7),可以移除(5,7)。在例子1中的匹配点(1,2),它的后继点为(4,6),(3,3),(2,5),(5,2),他们可通过TX的第一列和TY的第二列获得。因为(3,3)<(4,6),(4,6)可根据剪裁操作1被移除。在它的下一层,(3,3),(2,5)和(5,2)的后继点是(4,6),(5,4),(5,7)和(6,6)。因为(6,6)是(5,4)的后继点,(5,7)是(4,6)的后继点,因此,可移除(6,6)和(5,7)。

剪裁操作2:如果在同一层,有两个匹配点分别为,满足,不影响算法的正确性,可移除。

基本原理:可以被移除的原因如下。的后继点,字符序列和的最长公共子序列的长度是r。的后继点。因为i1<i2,如果一个LCS包括一个匹配点(i2,j)后的子串,它的子串能够被添加在(i1,j)后面。因为(i1,j)和(i2,j)在同一层,必然存在一个LCS包括(i1,j)。换句话说,对于很多包含了(i1,j)的LCS,必然有一个包含了(i1,j)。(i2,j)不影响算法的正确性,可剪除。通过扩展裁剪操作2,能够得到一下的裁剪操作。

裁剪操作3:如果有多个匹配点,可以裁剪。

3。1。3 FAST_LCS的框架和复杂度分析

基于通过后继表产生匹配点的后继点操作和剪裁操作,提出了以一种名为“FAST_LCS”快速的并发算法。该算法包含两个阶段:搜索所有的匹配字符和回溯得到LCS。第一个阶段

从初始匹配字符序列出发,继而通过后继表查询后继匹配点。在这个阶段中,可以通过裁剪技术丢弃那些无法得到最佳解决方案的匹配点,从而能减少搜索空间和加快搜索效率。

FAST_LCS算法的框架如下所示。步骤1,2,3组成了第一个阶段,步骤4组成了第2个阶段。文献综述

步骤1。 建立TX表和TY表

步骤2。 找到所有初始匹配点:,并将这些匹配点以的结构存于“匹配点”表中。

步骤3。 重复一下的操作直到“匹配点”表中没有active状态的记录。

步骤3。1 对于所有active状态的匹配点并发操作。

步骤3。1。2 对于直接后继匹配点中的每个元素都创建一个新的记录,并插入匹配表中。

步骤3。1。3 改变的状态为inactive。

步骤3。2 对这一层所有的后继点使用裁剪操作,移除匹配表中无用的匹配点。

上一篇:java+mysql云平台的移动考试系统设计
下一篇:射频识别技术的公司会议签到系统后台子系统设计

基于PageRank算法的网络数据分析

大电流LED驱动器LTC3454【506字】

Windows操作系统最新补丁大全【3058字】

ERP技术发展的现状趋势及...

网页恶意代码的十一大危...

大网络环境下的数据挖掘用户的行为挖掘

C#+sqlserver大学体育馆预订管理系统设计

我国风险投资的发展现状问题及对策分析

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

互联网教育”变革路径研究进展【7972字】

老年2型糖尿病患者运动疗...

新課改下小學语文洧效阅...

安康汉江网讯

ASP.net+sqlserver企业设备管理系统设计与开发

张洁小说《无字》中的女性意识

网络语言“XX体”研究