(2-2)

对于矩阵L能够被扩展为N个字符序列，对于每一个位置L[i1,i2,。。。,iN],它的值通过直接前置位置定义。

一旦矩阵L被计算，能够从最后一个点[n1,n2]回溯至起始点[0,0]，得到MLCS,|MLCS|是MLCS的长度。|MLCS|的值等于矩阵L中的最大值。图2-1中展示了一个例子，对于两个字符序列a1=GATTACA，a2=GTAATCTAAC。

图2-1 矩阵L

图2-1中被圈出的是支配点。

通过动态规划算法，可以直接计算出矩阵L中的所有匹配点。对于d个长度为n的字符序列，算法的时间空间复杂度为。很多方法提出优化动态规划算法的时空复杂度，但不幸的是，这些方法大多只能试用于2个字符序列的情况。由于动态规划算法具有很高的时空复杂度，人们已提出了多种的LCS和 MLCS的改进算法。

2。2。2 基于支配点的算法

假设L是在有限字符集Σ中的对应矩阵，矩阵L中的一个点p被表示为p=[p1,p2,。。。,pd]，其中pi是对应的字符序列ai上p的位置，在矩阵L中位置p处的值是L[p]。如果a1[p1]=a2[p2]=。。。=ad[pd]，那么一个点p=[p1,p2,。。。,pd]在矩阵中被称为一个匹配点。比如，在图2-1当中的矩阵，点[0，0]和[1，2]是两个匹配点，分别表示字符G和A。如果匹配点满足如下条件：L[p]=k,不存在其他匹配点q，，满足q支配p。则匹配点p可被称为一个k层支配点。所有的k层支配点的集合被称为，所有支配点集合被称为D。

在图2-1当中，所有相同的被圈出，这些被圈出的为支配点，他们是整个轮廓中的关键点。

图2-2支配点矩阵

基于支配点方法背后主要的思想是用这些支配点代替矩阵L所有的点。特别的，基于支配点的方法首先计算第一层的支配点。在反复迭代的步骤当中，第k+1层的支配点集合是从第k层支配点计算得到，。因此，从一个轮廓到另一个轮廓，所有的支配点可以被得到。

图2-2说明了两个字符序列a1，a2使用支配点方法的过程，在图2-2当中，相同一层的支配点被圈出来，第一层的支配点[，1]首先在第一个步骤当中就被圈出来，在第二个步骤当中根据第一个匹配点集合{[1,1]}计算得出第二层的匹配点集合[2,3],[3,2]。在图中的箭头方向就是从第k层指向第k+1层，。

基于支配点的方法成功的应用在两个字符序列的情况下，有些算法也提出了一些适用于3个或更多字符序列的方法。其中有一个算法A被设计用来解决有3个字符序列的MLCS算法，比传统的使用动态规划的算法要快。可是A通过枚举每一个维度的相同位置的值。最后他的复杂度随着字符序列的增加快速增加。而其他算法Hakata和Imai的算法，用于多个字符序列。而最新的算法FAST_LCS使用成对比较的方法来计算支配点。论文网

由于传统的动态规划算法就有非常高的时间空间复杂度，需要降低其时空复杂度。在使用动态规划的过程中需要计算每一层的匹配点，而每一层的匹配点会指数增长，且大多数匹配点是无效的，对最后的结果并没有影响，匹配点的计算的算法的主要计算点，因此需要对这些匹配点集合进行最小化处理，去除冗余匹配点，减少计算量。而在支配点算法中，并不计算每一层匹配点所有的值，只计算每一层的支配点，删除被支配点，支配点数远远小于匹配点数，因此，该算法能大大降低计算量，和动态规划算法相比，具有非常大的时空优势。

2。2。3 并行算法

LCS/MLCS应用的普及与深入，以及字符串集规模及其串长的不断增大，为了提高算法的效率并进一步求解LCS/MLCS问题，人们开始研究并行的LCS/MLCS算法。串行的算法只运行在一个处理机上，而并行算法可运行在多个处理机上，同时处理计算任务，可大大提高计算的效率。在LCS/MLCS算法中,每个支配点寻求下一层支配点的过程中可同时进行，因此每一层支配点计算下一层支配点的过程中是一种线性复杂度，能大大降低算法整体复杂度，包括在每一层的最小化计算的过程中也可使用并行计算，提高效率。 适合大数据分析MLCS算法的设计与实现(3):http://www.youerw.com/jisuanji/lunwen_123957.html