最長公共子序列在比對工具的應用
即使如何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
功能性說明
此方法是一種典型的通過空間換時間的演算法實現，通過提高一維的空間消耗降低一維的時間消耗，對於大文本文檔（超過萬行的文本），一次性開闢出一萬乘一萬的矩陣會有內存不足的風險，要解決該類問題，只需要在處理比對過程中新增對文檔進行分割比對的處理：每千行文本為單位構建文本，即相當於拆分成多個小文件。
標星 置頂美亞柏科
一秒找到美美
