证明：通过(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 对这一层所有的后继点使用裁剪操作，移除匹配表中无用的匹配点。 适合大数据分析MLCS算法的设计与实现(6):http://www.youerw.com/jisuanji/lunwen_123957.html