基于位運(yùn)算的最長(zhǎng)公共子串算法

1、基于位運(yùn)算的最長(zhǎng)公共子串算法浙江 唐文斌摘要本文來(lái)自于參考文獻(xiàn)1。本文描述了一個(gè)對(duì)于確定有限字符集的基于位運(yùn)算的最長(zhǎng)公共子串算法。該算法在普通計(jì)算機(jī)上運(yùn)行效率明顯高于常規(guī)的動(dòng)態(tài)算法。其時(shí)間復(fù)雜度為。其中w表示我們?cè)趙位的整數(shù)上進(jìn)行位操作。問(wèn)題介紹最長(zhǎng)公共子串（Longest-common-subsequence , LCS）問(wèn)題，是求兩個(gè)字符串A和B的公共子串的最大可能長(zhǎng)度。例如，字符集S=A,C,G,T，GCTAT和CGATTA的最大公共子串（以下簡(jiǎn)稱LCS）為GTT，其長(zhǎng)度為3。在這里定義一些變量: A,B分別是兩個(gè)給定的串。S為A、B串所涉及的字符集。常規(guī)動(dòng)態(tài)規(guī)劃算法設(shè)Li , j等于A

2、1.i , B1.j的LCS.則有Li,j = 1 + Li-1 , j-1 如果 (Ai = Bj) Max(Li-1 , j , Li , j-1) 其他復(fù)雜度為O(|A| * |B|)基于位運(yùn)算的動(dòng)態(tài)規(guī)劃算法根據(jù)上面的動(dòng)態(tài)規(guī)劃算法，狀態(tài)函數(shù)L具有如下性質(zhì)：Li-1,j-1 Li,j-1 , Li-1,j Li,j | Li,j-Li-1,j-1 | 1 對(duì)于L的每一行，相鄰的兩個(gè)元素的最多只相差1。這樣一來(lái)，我們就可以用一個(gè)二進(jìn)制的矩陣描述出L : ()#bits9 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 | T string B9 0 1 0 0 1 0 0 0

3、 1 0 1 1 1 1 1 1 | T 8 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 | C 7 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 | T - Row11 7 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 | A - Row10 7 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 | G 6 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 | A 5 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 | A 5 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 |

4、 T 4 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 | T 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 | C 3 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 | G 2 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 | A 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | T _. matrix MijString A: G T C T T A C A T C C G T T C G 這里，我們將串A從右往左寫，串B從下往上寫。Rowi中的1的個(gè)數(shù)總是和Rowi-1中的1的個(gè)數(shù)一樣多或者

5、恰好多一個(gè)。串A和串B的LCS即為最上面一行Row|B|中1的個(gè)數(shù)。字符比較串表這里我們定義一組稱為字符比較串的二進(jìn)制串。分別是字符集中的每一個(gè)字符與串A的比較結(jié)果(相同為1，不同為0)。A： G T C T T A C A T C C G T T C GA-string: 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0C-string: 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0G-string: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1T-string: 0 1 0 1 1 0 0 0 1 0 0 0 1 1 0 0預(yù)先計(jì)算這個(gè)字符

6、比較串表，時(shí)間復(fù)雜度為O(|S|*|A|)。對(duì)于一個(gè)確定的字符集，時(shí)間復(fù)雜度為O(|A|)。對(duì)于一個(gè)不確定的字符集，最壞情況為O(|A|*|B|)。如果字符集較小，|S|<<|B|，預(yù)處理的時(shí)間復(fù)雜度可以被忽略。矩陣M為了計(jì)算Rowi，我們需要用到字符比較串表中的Bi-string。以Row10到Row11為例，我們來(lái)研究如何計(jì)算出Rowi。下面是Row10 , 以及B10-string(T-string). 按照Row10中的1分隔：Row10:1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1T-string :0 1 0 1 1 0 0 0 1 0 0 0 1 1

7、 0 0每一段都是從Rowi-1的一個(gè)1的位開(kāi)始往右延伸，直到下一個(gè)位置是1或者串結(jié)束。如果Rowi-1的最左邊的位置上是0，那么最左邊的一段從Bi-string的最左邊的1的位置開(kāi)始延伸直到下一個(gè)1。Rowi的構(gòu)成方式很簡(jiǎn)單：就是對(duì)于每一段，都是選擇Rowi-1或者Bi-string最右邊的1所在位置為1，其他的為0。如果這一段Rowi-1和Bi-string都是0，那么Rowi這一段也為0。T-string Or Row10: 1 1 0 1 1*0 0 1 1*0 0 1* 1* 1* 1* 1*Row11:0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1*表示了進(jìn)行或操作

8、之后每一段最右邊的1附帶一提，你可以假定在每個(gè)串的最左邊（位置|A|+1）存在一個(gè)1，這樣可以方便處理最左邊一段全為0的情況。不過(guò)對(duì)于本算法并沒(méi)有這個(gè)必要。在Rowi-1中的一個(gè)1的位置，代表了A中的一個(gè)最短前綴與B1.i-1的LCS達(dá)到了該長(zhǎng)度。引進(jìn)Bi，最好的方法當(dāng)然是在前面的最短基礎(chǔ)上加入一個(gè)最短的與Bi的匹配，也就是從那個(gè)1所在的位置往左找，找到的第一個(gè)能與Bi匹配的(如果找得到的話)。設(shè) X = Rowi-1 Or Bi-string對(duì)于當(dāng)前的例子，X = Row10 Or T-string X: 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1把Rowi-1往左移1位

9、，并且設(shè)最低位為1，用X去減這個(gè)串：X: 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 - 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 - - - - - - - 1 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0這個(gè)操作所表達(dá)的意思為對(duì)于每一段，把最右邊的一個(gè)1變成0，把這個(gè)1右邊的所有0變成1，設(shè)最低位為1的目的是為了可以同樣處理最后一段。再跟X 進(jìn)行Xor(異或)操作，得到：0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1這步操作之后的結(jié)果就是，對(duì)于每一段，從最右邊的1開(kāi)始到段尾變成1，其他變成0。因?yàn)閄or為1當(dāng)且僅當(dāng)兩個(gè)

10、位上的數(shù)不同，而上一次操作我們修改過(guò)的位是從最右邊的1直到段尾。接下來(lái)就很顯然了，只要再將上面的結(jié)果與X進(jìn)行And操作即可。得到：0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1這樣就得到了Rowi , 即當(dāng)前例子中的Row11。綜上，Rowi = X And ( (X (Rowi-1 << 1) + 1) Xor X)其中X = Rowi-1 Or Bi-stringOr , And , Xor 為基本的位操作<< 表示將位串往左移動(dòng)若干位算法到此結(jié)束。計(jì)算出Row|B|之后，數(shù)一下其中有多少個(gè)1的位，便是答案了。參考實(shí)驗(yàn)結(jié)果以下是在Pentium3.0GHz , 512RAM下，對(duì)于純隨機(jī)數(shù)據(jù)的一些測(cè)試結(jié)果：|A|*|B|常規(guī)動(dòng)態(tài)規(guī)劃程序運(yùn)行時(shí)間使用位操作的動(dòng)態(tài)規(guī)劃程序運(yùn)行時(shí)間2000*20000.030s0.000s5000*50000.156s0.015s8000*80000.375s0.031s12000*120000.843s0.078s20000*200002.296s0.234s40000*400009.387s