最长公共子序列在比对工具的应用

即使如何1

在实际工作中，我们常常要对输出的文本和数据进行比对：以取证大师为例，取证大师导出的取证结果数据量很容易达到上万条。这类数据特点除了数量级大外，其实数据结构很相近。即使我们以无以伦比的细致和专心去比对，也难以发现文本间的所有差异。为了提高比对效率和重复利用性，我们发现了一种解决方案，下面一起来了解一下吧。

1

应用场景

对于该比对工具而言，是以LCS方法为核心，针对不同类型的文档比对进行拓展。除无法解析的加密文档外，其余的文件都能通过该方法实现比对操作，例如：部分含有特殊标准的数据文件、代码文件、普通文本文件及表格等。

1、 数据比对：在信息化飞速发展的现状下，大量数据作为信息化的输出，与我们有着密不可分的关系，数据比对也就自然而然的成为我们工作过程中的一个重要环节，一个高效的数据比对工具就显得尤为重要；

2、 代码文件比对：产品的快速更新迭代造就了时代的快速发展，对于研发人员而言，代码的更新迭代最为频繁；在开发过程中，借助比对工具下，前后文件差异点一目了然，为研发人员节约宝贵的时间，为产品迭代奠定基础。

1

方法介绍

最长公共子序列（Longest Common Subsequence，以下简称LCS），该方法的定义为一个序列Subsequence，如果它属于两个或两个以上已知序列的子序列，并且是所有符合条件的子序列中最长的一个，则我们称这个序列为已知序列的最长公共子序列，在文本比对中，可通过该方法在多个比对文本中筛选出所有公共特征块。传统的文本比较方法中除了每两两特征块进行比较外，还需要对筛选出来的特征块进行一次遍历，得到最长的序列，时间复杂度为n^3，该方法效率低下；因此需要通过LCS方法进行优化，在特征块两两比较的过程中，借助特定的算法，就能够输出公共特征块，在遍历结束时，输出的所有特征块序列便是最长公共子序列，时间复杂度降为n^2；

LCS优点在于当要进行比对的文本越大，节省的时间越高；其基本原理为通过多种规则得到文本每一行的特征值，将两个文本得到的特征值串通过以下方式比对：

1、比较特征值矩阵

2、根据数据填充规则进行数据的填充

3、比对结果的输出

1

方法实现

以下，将具体介绍LCS的填充规则和输出规则：

1.填充规则：从右往左，从下往上

（1）当行特征值与列特征值不相等，则比较右边方格与下边方格值的大小，哪个值大就取哪个值；

实现逻辑：c[i][j] = Math.max(c[i+1][j], c[i][j+1]);

（2）当行特征值与列特征值相等，右下方格的数值加一；

实现逻辑：c[i][j] = c[i+1][j+1] + 1;

2.输出规则：从左往右，从上往下

（1）当行特征值与列特征值不相等，将相邻的右边与下边两个数值进行大小比较，若右边数值大于等于下边数值，则数值输出路径转到右边；若右边数值小于下边数值，则数值输出路径转到下面（右边与下边谁大，路径就转到哪边）；

（2）当行特征值与列特征值相等，输出该特征值，并且路径跳转到右下角方格；

if(s1.charAt(i) == s2.charAt(j)){

}

填充与输出序列如图1所示，输出结果为CBZK:

图1 填充与输出

代码实现如图2所示：

图2 代码实现

1

实际效果

图3 文本比对

图4 效果显示

该方法有效的提升了比对效率，从n^3降到n^2，极大的提高了时间的利用率。

1

功能性说明

此方法是一种典型的通过空间换时间的算法实现，通过提高一维的空间消耗降低一维的时间消耗，对于大文本文档（超过万行的文本），一次性开辟出一万乘一万的矩阵会有内存不足的风险，要解决该类问题，只需要在处理比对过程中新增对文档进行分割比对的处理：每千行文本为单位构建文本，即相当于拆分成多个小文件。

标星+置顶美亚柏科

一秒找到美美