• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            glxhyt

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              15 隨筆 :: 0 文章 :: 4 評論 :: 0 Trackbacks

            字符串匹配:

            ---willamette

            在匹配串中尋找模式串是否出現(xiàn),注意和最長公共子序列相區(qū)別(LCS: Longest Common Substring)

            最簡單的Brute Force算法:

            首先將匹配串和模式串左對齊,然后從左向右一個(gè)一個(gè)進(jìn)行比較,如果不成功則模式串向右移動(dòng)一個(gè)單位。

            速度最慢。

            那么,怎么改進(jìn)呢?

            我們注意到Brute Force算法是每次移動(dòng)一個(gè)單位,一個(gè)一個(gè)單位移動(dòng)顯然太慢,是不是可以找到一些辦法,讓每次能夠讓模式串多移動(dòng)一些位置呢?

            當(dāng)然是可以的。

            我們也注意到,Brute Force是很不intelligent的,每次匹配不成功的時(shí)候,前面匹配成功的信息都被當(dāng)作廢物丟棄了,當(dāng)然,就如現(xiàn)在的變廢為寶一樣,我們也同樣可以將前面匹配成功的信息利用起來,極大地減少計(jì)算機(jī)的處理時(shí)間,節(jié)省成本。^_^

            首先介紹的就是KMP算法。

            原始論文:Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

            這個(gè)算法實(shí)在是太有名了,大學(xué)上的算法課程除了最笨的Brute Force算法,然后就介紹了KMP算法。也難怪,呵呵。誰讓Knuth D.E.這么world famous呢,不僅拿了圖靈獎(jiǎng),而且還寫出了計(jì)算機(jī)界的Bible <The Art of Computer Programming>(業(yè)內(nèi)人士一般簡稱TAOCP).稍稍提一下,有個(gè)叫H.A.Simon的家伙,不僅拿了Turing Award,順手拿了個(gè)Nobel Economics Award,做了AI的爸爸,還是Chicago Univ的Politics PhD,可謂全才。

            KMP的思想是這樣的:

            利用不匹配字符的前面那一段字符的最長前后綴來盡可能地跳過最大的距離

            比如

            模式串a(chǎn)babac這個(gè)時(shí)候我們發(fā)現(xiàn)在c處不匹配,然后我們看c前面那串字符串的最大相等前后綴,然后再來移動(dòng)

            下面的兩個(gè)都是模式串,沒有寫出來匹配串

            原始位置ababac

            移動(dòng)之后 ababac

            因?yàn)楹缶Y是已經(jīng)匹配了的,而前綴和后綴是相等的,所以直接把前綴移動(dòng)到原來后綴處,再從原來的c處,也就是現(xiàn)在的第二個(gè)b處進(jìn)行比較。這就是KMP。

            當(dāng)然,有市場就有競爭,字符串匹配這么大一個(gè)市場,不可能讓BF和KMP全部占了,于是又出現(xiàn)了幾個(gè)強(qiáng)勁的對手。

            第一個(gè)登場的是Horspool算法。

            論文:Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

            Horspool算法的思想很簡單的。不過有個(gè)創(chuàng)新之處就是模式串是從右向左進(jìn)行比較的。很好很強(qiáng)大,為后來的算法影響很大。

            匹配串:abcbcsdxzcxx

            模式串:cbcac

            這個(gè)時(shí)候我們從右向左進(jìn)行對暗號,c-c,恩對上了,第二個(gè)b-a,不對啊,我們應(yīng)該怎么辦?難道就這么放棄么。于是,模式串從不匹配的那個(gè)字符開始從右向左尋找匹配串中不匹配的字符b的位置,結(jié)果發(fā)現(xiàn)居然有,趕快對上趕快對上,別耽誤了。

            匹配串:abcbcsdxzcxx

            模式串: cbcac

            然后繼續(xù)從最右邊的字符從右向左進(jìn)行比較。這時(shí)候,我們發(fā)現(xiàn)了,d-c不匹配啊,而且模式穿里面沒有噢,沒辦法,只好移動(dòng)一個(gè)模式串長度的單位了。

            匹配串:abcbcsdxzcxx

            模式串: cbcac

            第二個(gè)上來的是Boyer-Moore算法。

            是一個(gè)很復(fù)雜的算法,當(dāng)然,雖然理論上時(shí)間復(fù)雜度和KMP差不多,但是實(shí)際上卻比KMP快數(shù)倍,可見實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)。

            原始論文:R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977

            分為兩步預(yù)處理,第一個(gè)是bad-character heuristics,也就是當(dāng)出現(xiàn)錯(cuò)誤匹配的時(shí)候,移位,基本上就是做的Horspool那一套。

            第二個(gè)就是good-suffix heuristics,當(dāng)出現(xiàn)錯(cuò)誤匹配的時(shí)候,我還要從不匹配點(diǎn)向左看啊,以前匹配的那段子字符串是不是在模式串本身中還有重復(fù)的啊,有重復(fù)的話,那么我就直接把重復(fù)的那段和匹配串中已經(jīng)匹配的那一段對齊就是了。再比較

            匹配串:abaccbabbazz

            模式串:cbadcba

            我們看到已經(jīng)匹配好了cba,但是c-d不匹配,這個(gè)時(shí)候我們發(fā)現(xiàn)既可以采用bad-character heuristics,也可以使用good-suffix heuristics(模式串:cbadcba),在這種情況下,邪不壓正。毅然投奔good。移動(dòng)得到

            匹配串:abaccbabbazz

            模式串: cbadcba

            可是,我們有時(shí)候也發(fā)現(xiàn),已經(jīng)匹配好的那一部分其實(shí)并沒有再有重復(fù)了的啊。這個(gè)時(shí)候,我們發(fā)現(xiàn)已經(jīng)匹配好的那串字符串有一部分在開頭重新出現(xiàn)了,那么,趕快,對齊吧。

            匹配串:abacccbbbazz

            模式串:cbadccb

            然后得到

            匹配串:abacccbbbazz

            模式串: cbadccb

            當(dāng)兩種Good-Suffix出現(xiàn)的時(shí)候,取移動(dòng)距離最大的那個(gè)。

            最后一個(gè)是Sunday算法,實(shí)際上比Boyer-Moore還快,呵呵。長江后浪推前浪。

            原始論文:Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

            看原始論文的題目,D.M. Sunday貌似是故意想氣氣Boyer-Moore兩位大牛似的。呵呵。不過實(shí)際上的確Sunday算法的確比BM算法要快,而且更簡單。

            Sunday的算法思想和Horspool有些相似,但是。當(dāng)出現(xiàn)不匹配的時(shí)候,卻不是去找匹配串中不匹配的字符在模式串的位置,而是直接找最右邊對齊的右一位的那個(gè)字符在模式串的位置。

            比如:

            匹配串:abcbczdxzc

            模式串:zbcac

            恩,這里我們看到b-a沒有對上,我們就看匹配串中的z在模式串的位置,然后,嘿嘿。

            匹配串:abcbczdxzc

            模式串: zbcac

            如果模式串中的沒有那個(gè)字符怎么辦呢?很簡單,跳過去唄。

            匹配串:abcbcedxzcs

            模式串:zbcac

            e不在模式串中出現(xiàn)

            那么我們就

            匹配串:abcbcedxzcs

            模式串: zbcac

             

            實(shí)際上,現(xiàn)在還有很多很多字符串匹配算法,這里只是簡單介紹了一下最常使用的五種算法,更多算法可以參考一下http://www.inf.fh-flensburg.de/lang/algorithmen/algo.htm,8過這個(gè)是德文網(wǎng)站,有的網(wǎng)頁沒有英文版的哦。

            posted on 2013-05-19 16:58 郭龍 閱讀(739) 評論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久人人爽人人澡人人高潮AV | 亚洲人成无码www久久久| 91超碰碰碰碰久久久久久综合| 久久综合久久综合久久| 伊人精品久久久久7777| 精品久久久久久无码专区不卡| 国产精品va久久久久久久| 午夜精品久久久久久影视777| 色综合久久久久无码专区| 久久久WWW成人免费精品| 亚洲欧美日韩中文久久| 久久人人爽人爽人人爽av| www久久久天天com| 人妻无码精品久久亚瑟影视| 精品久久久久久亚洲精品| 久久久久精品国产亚洲AV无码 | 无码任你躁久久久久久| 国产精品久久久久国产A级| 一级做a爰片久久毛片看看| 久久99热国产这有精品| 午夜不卡久久精品无码免费| 天堂无码久久综合东京热| 久久93精品国产91久久综合| 久久婷婷成人综合色综合| 久久伊人精品一区二区三区| 国内精品久久久久久麻豆| 久久人人爽爽爽人久久久| 久久精品人妻中文系列| 亚洲伊人久久综合中文成人网| 狠狠色综合久久久久尤物| 久久se精品一区精品二区| 久久99免费视频| 91精品国产91热久久久久福利| 狠狠干狠狠久久| 亚洲国产精品热久久| 国产—久久香蕉国产线看观看| 久久97精品久久久久久久不卡| 伊人丁香狠狠色综合久久| 精品久久久久一区二区三区| 久久精品视屏| 思思久久精品在热线热|