武明超 崔曉兵 姚欣 邵詠慧

摘? ?要：針對多條序列最長公共子序列的多解問題，為了能夠求出若干條字符串序列，對它們共有的最大相似序列，在計算中按照相似度和長度進行打分，并且對輸出的子序列進行排序，以便能夠輸出相似序列的位置并且達到最優(yōu)的相似度。根據(jù)最優(yōu)相似度確定字符串之間匹配的公共長度和重復率，用比重復率作為判別相似度的一個指標，在一個已知的字符串，通過和其他字符的比較，利用此種思想，可以找出插入在字符串中的空格位置，并能使相似度達到最優(yōu)化。通過構(gòu)建代數(shù)結(jié)構(gòu)“格”，利用遞歸求解當前格與當前序列的公共格。再通過動態(tài)規(guī)劃求出最長公共子序列的長度數(shù)組和狀態(tài)數(shù)組，矩陣搜索求出所有有效的跳躍點，能有效避免重復搜索，大大提高時間效率。

關(guān)鍵詞：最長公共子序列;近似算法;貪心算法

隨著科學技術(shù)的進步，人們利用序列的相似性比較研究各個方向。例如，生物學中的親子鑒定、醫(yī)學中的診斷病基因確定疾病。隨著科學的進步，字符串之間的相似問題也成為研究的重點，同時，提出了許多類似于上述的序列相似度算法。根據(jù)不同的特征，相似度的計算方法也不盡相同，主要有方面相似算法、統(tǒng)計關(guān)聯(lián)算法、相似語義算法等。有人提出結(jié)合3種算法的優(yōu)缺點，建立多層規(guī)劃模型。其中，相似字面主要包括距離編輯和類似的字或者詞語的計算方法。因此，此研究在各個方面都得到了廣泛的應(yīng)用。例如同分異構(gòu)的數(shù)據(jù)檢索、圖譜分析以及基因分析等。多條序列的最長公共子序列可以代表多條序列的公共信息，其在諸多領(lǐng)域里有著重要的應(yīng)用，針對求解多條序列的最長公共子序列式的非確定性多項式（Nondeterministic Polynominal，NP）（Non-deterministic Polynomial，NP）難問題，本質(zhì)為多解問題。一些近似算法雖然時間復雜度較低，但只能求出單一解，對于有多解的序列集合，求得的結(jié)果信息量損失較大。針對求解多條序列的最長公共子序列式的多解問題，本文利用一個新的近似算法來解決最長公共子序列問題。算法引入了稱為“格”的代數(shù)結(jié)構(gòu)，利用動態(tài)規(guī)劃求出兩序列的公共格，并通過遞歸求得當前格與當前序列的公共格。求得公共格中的路徑保存了多條公共子序列，使最終求出的最長公共子序列也為多個。根據(jù)最長公共子序列的特點，利用動態(tài)規(guī)劃法求出最長公共子序列的長度數(shù)組和狀態(tài)數(shù)組，并通過矩陣搜索求出所有有效的跳躍點，構(gòu)造求解所有最長公共子序列的算法并通過程序給予實現(xiàn)。能有效避免重復搜索，時間效率大大提高，特別適用于基因工程中的基因片段分析，并通過實驗驗證了算法的可靠性[1]。

1? ? 算法介紹

廣義后綴樹（Generalized Suffix Tree，GST）算法思想是利用長度為m的串P，利用某個函數(shù)通過計算得到每個對應(yīng)的序列值。并且把每個長度為1的字符串按照一定的長度進行劃分，便可以得到一定長度的子串，然后對每個子字符串利用同樣的函數(shù)計算便可以得到一個序列值。只有那些和模式串有相同序列值的子字符串才有可能和模式串匹配。如果文本子字符串中的序列值和模式串的序列值都不相同的話，那么該字符串一定不能匹配模式串。在RKRGST算法中指定一個長度，這個長度也可被稱為搜索長度，利用這個長度可以對兩個字符串同時進行劃分，使用同一個序列，兩數(shù)分別計算出每個劃分的序列值，并且存儲起來，然后通過比較字符串這些序列值，凡是序列值相同的就認為這兩個長度是子字符串匹配，然后對這兩個子串后面的字符串進行貪婪匹配，如果后面的字符依舊相同，則繼續(xù)匹配，直到兩者不能匹配為止，同時，記錄這個匹配長度和分別在字符串中開始匹配的位置與字符中開始匹配的位置，首先，將這些信息儲存起來;然后，繼續(xù)去匹配其他長度的子串，通過對每對能夠匹配的子串都進行貪婪匹配，最后，再記錄匹配的長度、開始位置等信息。如果有兩次找到的匹配的最大長度是相同的，那么就將新找到的匹配信息記錄到前一個和其匹配長度相同的后面，從而可以形成一個匹配鏈表[2]。

2? ? 改進后的格算法

本文研究了一個計算最長公共子序列[1]的算法，稱為格方法。該方法利用了代數(shù)結(jié)構(gòu)[2]，盡可能多地保存動態(tài)規(guī)劃[3]信息，與傳統(tǒng)算法相比，此算法在集中的序列數(shù)量與精確度方面都有一定提升。如果節(jié)點數(shù)增加，會導致公共格中的路徑數(shù)量也會增加，進而為找到更長的公共子序列[4]提供了可能性。就算小靈通定位系統(tǒng)（Location Service Center，LSC）的長度沒有變化，由計算得出的信息也使最終求出的數(shù)量增加[3]。

在很多領(lǐng)域內(nèi)，求解最長公共子序列都有著重要的應(yīng)用。在求信息序列的最大子序列時，首先，提取序列的公共信息，通過進一步檢索與分類。獲取各個基因序列間的匹配度。由于格結(jié)構(gòu)自身的特點，使得求出的公共子序列也有很多個。本文通過相關(guān)理論分析和實驗驗證了算法的正確性和可靠性[4]。

3? ? 算法實現(xiàn)

3.1? 數(shù)據(jù)結(jié)構(gòu)選取

本文采用的數(shù)據(jù)結(jié)構(gòu)為數(shù)組。二維數(shù)組C[i][j]用于判斷最優(yōu)解的構(gòu)造順序以及計算最優(yōu)解的長度。二維數(shù)組B[i][j]用于記錄最優(yōu)解的構(gòu)造順序，在打印最優(yōu)解時作一個索引。X[i]，Y[j]用于存儲輸入的兩個子序列[5]。

3.2? LCS值輸出函數(shù)

函數(shù)名為Print_LCS。實現(xiàn)方法為自底向上判斷記錄符號，并輸出符合條件的X[i]或Y[j]，通過遞歸比較方便，就是通過比較兩個字符串的首個字符是否一樣，如過相同就將其添加。然后剔除首字符，剩下的子字符串繼續(xù)進行遞歸匹配。如果兩個字符串的首字符不同，則通過3種對齊策略分別計算可能的最長公共字串，然后取其最長的一個與當前已知的最長公共字串進行比較。如果比當前已知的最長公共字串長，就用計算值代替當前值。

通過對字符串的反復遞歸，對“?！钡牟僮鹘?jīng)常發(fā)生訪問沖突的錯誤，故只能用少量的數(shù)據(jù)處理，并且當數(shù)據(jù)存放到文件中時，子函數(shù)和主函數(shù)對同一文件的操作有覆蓋和不顯示的問題，因此，創(chuàng)建了兩個文本文件用于對實驗結(jié)果的存放。

本次設(shè)計通過動態(tài)算法解決最長公共子序列問題，對于求兩個序列的一個最長公共子序列，LCSlength算法時間復雜性為0（alen*blen） ，能夠得到比較理想的效果。但從另一方面看，這種算法在對C[i-1][j]與C[i][j-1]值的比較中忽略了相等時的情況，即當兩個序列的最長公共子序列不一致時，不可能通過此算法求出所有的最優(yōu)公共序列。

LCS算法首先規(guī)定一個或者多個字符串，然后刪除多個字符或者保留全部字符，但要保證操作后不改變其他字符間的相對位置，然后計算可得到最優(yōu)的公共序列。采用遞推法來計算出公共長度。首先，給定任意兩個字符串，不難得出，任意兩個字符串的距離必然不超過它們的總長度。即使這個結(jié)論對結(jié)果沒有太大幫助，但通過這至少可以知道，任意兩個字符串的距離必然是有限的。需要集中考慮，如何能把這個問題進行轉(zhuǎn)化，通過求解規(guī)模較小的同樣的子問題來解決。

本文針對最大公共子序列進行研究，最大公共子序列在各領(lǐng)域也有著廣泛的應(yīng)用，但是在解決公共子字符串的問題上還存在不足之處，即時間復雜度長、空間復雜度高。即使降低了時間復雜度，在空間復雜度相對來說還較高，并且編程難以實現(xiàn)。本文研究的算法結(jié)合兩者的優(yōu)點，既在限制線性時間復雜度的同時，也降低了空間復雜度，而且便于編程實現(xiàn)。

4? ? 結(jié)語

文中首先定義了一個指標，這個指標用來衡量字符串之間的相似度，此指標是根據(jù)字符串之間的重復率設(shè)定的，根據(jù)不同的對象，此指標不盡相同，具有很好的魯棒性。利用此思想，能夠高效找出字符串中插入的空格位置，同時，能使二者之間的相似度達到最優(yōu)。

本次研究通過對字符串的反復遞歸，對“?！钡牟僮鹘?jīng)常發(fā)生訪問沖突的錯誤，故只能才用少量的數(shù)據(jù)處理，并且當數(shù)據(jù)存放到文件中時，子函數(shù)和主函數(shù)對同一文件的操作有覆蓋和不顯示的問題，因此，創(chuàng)建了兩個文本文件用于對實驗結(jié)果的存放。本文給出了算法的相關(guān)理論并通過實驗驗證了算法的可靠性。能有效避免重復搜索，時間效率大大提高，特別適用于基因工程中的基因片段分析，為信息檢索、基因序列匹配等提供了一定的參考價值。

[參考文獻]

[1]孫燾，朱曉明.基于格代數(shù)的最長公共子序列近似求解[J].計算機科學，2017（2）：270-274.

[2]朱曉明.序列的公共特征提取算法研究[D].大連：大連理工大學，2016.

[3]肖侃，譚長庚，丁玲.基于中文分詞的文本相似度動態(tài)規(guī)劃算法[J].現(xiàn)代電子技術(shù)，2011（8）：72-74，78.

[4]張毅超，車玫，馬駿.求最長公共子串問題的算法分析[J].計算機仿真，2007（12）：97-100，116.

[5]鄭翠玲.最長公共子序列算法的分析與實現(xiàn)[J].武夷學院學報，2010（2）：44-48.

Research on a common sequence with optimal similarity

Wu Mingchao1， Cui Xiaobing1， Yao Xin2， Shao Yonghui1

（1.School of Computer and Information Engineering， Henan Normal University， Xinxiang 453000， China;

2.Chengdu University， Chengdu 610000， China）

Abstract：For the multi-solution problem of the longest common subsequence of multiple sequences， in order to be able to find several sequences of strings， the largest similar sequence they share is scored according to the similarity and length in the calculation， and the output is sub- The sequences are sorted so that the positions of similar sequences and the similarity of high matches can be output. Then use two strings to slide the number of matches between the comparison and the overlap rate of the two strings when sliding， thus defining the measure of similarity， by determining that one string is less than the other. An algorithm is designed to determine the position of the inserted space in the matrix of the string matching and to maximize the similarity index. Then， by constructing an algebraic structure “grid”， the common lattice of the current lattice and the current sequence is solved by recursion can effectively avoid repeated searches， greatly improving time efficiency.

Key words：longest common subsequence; approximate algorithm; greedy algorithm