下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 整院租賃合同模板
- 護(hù)士課件題目大全
- 農(nóng)藥設(shè)備轉(zhuǎn)讓合同模板
- 銷售員工合同模板版
- 金融借款標(biāo)準(zhǔn)合同模板
- 建材裝修公司合同模板
- 租賃合同模板帶公告
- 轉(zhuǎn)讓分租合同模板
- 買賣廢鋼合同模板
- 淮安美協(xié)第三屆理事會(huì)工作報(bào)告 - 江蘇省淮安市美術(shù)家協(xié)會(huì)歡迎您 ...
- 漆包線檢驗(yàn)方法介紹
- 淺談如何培養(yǎng)特優(yōu)生
- 斷絕母子關(guān)系協(xié)議書(shū)(共1頁(yè))
- XXX汽車零部件開(kāi)發(fā)推進(jìn)計(jì)劃表
- 社區(qū)委員的辭職報(bào)告 社區(qū)兩委辭職報(bào)告
- 新蘇教版數(shù)學(xué)小學(xué)六年級(jí)上冊(cè)單元試題全冊(cè)
- 簡(jiǎn)歷常用icon圖標(biāo)Word簡(jiǎn)歷模板
- 理工學(xué)院大一新生動(dòng)員大會(huì)PPT課件
- 機(jī)械設(shè)備工程工程量清單計(jì)價(jià)PPT課件
- 漆黑的魅影5.0二周目圖文攻略
評(píng)論
0/150
提交評(píng)論