丨字符串匹配基礎(chǔ)上如何借助哈希算法實(shí)現(xiàn)高效

我會(huì)講兩種多模式串匹配算法，也就是在一個(gè)串中同時(shí)查找多個(gè)串，它們分別是Trie樹(shù)和AC今天講的兩個(gè)算法中，RK算法是BF算法的改進(jìn)，它巧妙借助了我們前面講過(guò)的哈希算法，讓匹配的效率有了很大的提升。那RK是如何借助哈希算法來(lái)實(shí)現(xiàn)高效字符串匹配BFBF算法的BF是te 的縮寫(xiě)，中文叫作匹配算法，也叫樸素匹配算法。從可以，這法的串匹式“然也比較、好但相應(yīng)的性能也不高。在開(kāi)始講解這個(gè)算法之前，我先定義兩個(gè)概念，方便我后面講解。它們分別是主串串。這倆概念很好理解，我舉個(gè)例子你就懂了。比方說(shuō)，我們?cè)谧址瓵查找字B，那字符串A是主串，字符串B是模式串。我們把主串的長(zhǎng)度記作n，模式串的長(zhǎng)度記作m。因?yàn)槲覀兪窃谥鞔胁檎夷Ｊ酱?，所以作為最?jiǎn)單、最的字符串匹配算法，BF算法的思想可以用一句話來(lái)概括，那就是，我們?cè)谥鞔?，檢查起始位置分別是0、1、2…n-m且長(zhǎng)度為m的n-m+1個(gè)子串，看有從上面的算法思想和例子，我們可以看出，在情況下，比如主串是“aaaaa…（省略號(hào)表示有很多重復(fù)的字符a），模式串是“aaaaab”。我們每次都m個(gè)字符，要比對(duì)n-m+1次，所以，這種算法的情況時(shí)間復(fù)雜度是O(n*m)。盡管理論上，BF法的時(shí)間復(fù)雜度很高，是O(n*m)，但在實(shí)際的開(kāi)發(fā)中，它卻是一個(gè)比要把m個(gè)字符都比對(duì)一下。所以，盡管理論上的情況時(shí)間復(fù)雜度是O(n*m)，但是，有bug也容易和修復(fù)。在工程中，在滿(mǎn)足性能要求的前提下，簡(jiǎn)單是首選。這也是我們常說(shuō)的KISS（KeepitSimpleandStupid）設(shè)計(jì)原則。所以，在實(shí)際的軟件開(kāi)發(fā)中，絕大部分情況下，樸素的字符串匹配算法就夠用RKRK算法的全稱(chēng)叫Rabin-Karp算法，是由它的兩位發(fā)明者Rabin和Karp的名字來(lái)命名的。這個(gè)算法理解起來(lái)也不是很難。我個(gè)人覺(jué)得，它其實(shí)就是剛剛講的BF算法的升級(jí)版我在講BF算法的時(shí)候講過(guò)，如果模式串長(zhǎng)度為m，主串長(zhǎng)度為n，那在主串中，就會(huì)有n-m+1個(gè)長(zhǎng)度為m的子串，我們只需要地對(duì)比這n-m+1個(gè)子串與模式串，就可以但是，每次檢查主串與子串是否匹配，需要依次比對(duì)每個(gè)字符，所以BF算法的時(shí)間復(fù)雜度就比較高，是O(n*m)。我們對(duì)樸素的字符串匹配算法稍加改造，引入哈希算法，時(shí)間復(fù)雜RKn-m+1希的問(wèn)題，后面我們會(huì)講到）個(gè)數(shù)字，數(shù)字之間比較是否相等是非?？焖俚模阅Ｊ酱妥哟容^的效率就提高了。不過(guò)，通過(guò)哈希算法計(jì)算子串的哈希值的時(shí)候，我們需要遍歷子串中的每個(gè)字符。盡管模式串與子串比較的效率提高了，但是，算法整體的效率并沒(méi)有提高。有沒(méi)有方法可以提高哈希算法計(jì)算子串哈希值的效率呢？這就需要哈希算法設(shè)計(jì)的非常有技巧了。我們假設(shè)要匹配的字符串的字符集中只包含K字符，我們可以用一個(gè)K進(jìn)制數(shù)來(lái)表示一個(gè)子串，這個(gè)K進(jìn)制數(shù)轉(zhuǎn)化成十進(jìn)制數(shù)串的哈希值。表述起來(lái)有點(diǎn)抽象，我舉了一個(gè)例子，看完你應(yīng)該就能懂比如要處理的字符串只包含a～z這26個(gè)小寫(xiě)字母，那我們就用二十六進(jìn)制來(lái)表示一個(gè)字符串。我們把a(bǔ)～z這26個(gè)字符映射到0～25這26個(gè)數(shù)字，a就表示0，b就表示1，以此類(lèi)推，z表示25。個(gè)包含a到z這26個(gè)字符的字符串，計(jì)算哈希的時(shí)候，我們只需要把進(jìn)位從10改成26包含a～z這26個(gè)小寫(xiě)字符，我們用二十六進(jìn)制來(lái)表示一個(gè)字符串，對(duì)應(yīng)的哈希值就是二從這里例子中，我們很容易就能得出這樣的規(guī)律：相鄰兩個(gè)子串s[-]和s[ii表示子串在主串中的起始位置，子串的長(zhǎng)度都為m的哈希值計(jì)算有交集，也就是說(shuō)，我們可以使用s[-]的哈希值很快的計(jì)算出s[i]希值果用表示，就這個(gè)樣子：不過(guò)，這里有一個(gè)小細(xì)節(jié)需要注意，那就是m-)^0、1、^(m-)個(gè)為m的數(shù)組中，中的方就對(duì)應(yīng)數(shù)組的下標(biāo)。當(dāng)我們需要計(jì)算6的x的時(shí)候，就可以從數(shù)組的下標(biāo)為x我們開(kāi)頭的時(shí)候提過(guò)，RK算法的效率要比BF算法高，現(xiàn)在，我們就來(lái)分析一下，RK算法RK部分，我們前面也分析了，可以通過(guò)設(shè)計(jì)特殊的哈希算法，只需要掃描一遍主串就能計(jì)算出所有子串的哈希值了，所以這部分的時(shí)間復(fù)雜度是O(n)。模式串哈希值與每個(gè)子串哈希值之間的比較的時(shí)間復(fù)雜度是O(1)，總共需要比較n-m+1個(gè)子串的哈希值，所以，這部分的時(shí)間復(fù)雜度也是O(n)。所以，RK法整體的時(shí)間復(fù)雜度就是O(n)。這里還有一個(gè)問(wèn)題就是，模式串很長(zhǎng)，相應(yīng)的主串中的子串也會(huì)很長(zhǎng)，通過(guò)上面的哈希算法計(jì)算得到的哈希值就可能很大，如果超過(guò)了計(jì)算機(jī)中整型數(shù)據(jù)可以表示的范圍，那該如何解剛剛我們?cè)O(shè)計(jì)的哈希算法是沒(méi)有散列的，也就是說(shuō)，一個(gè)字符串與一個(gè)二十六進(jìn)制數(shù)一一對(duì)應(yīng)，不同的字符串的哈希值肯定不一樣。因?yàn)槲覀兪腔谶M(jìn)制來(lái)表示一個(gè)字符串的，你可以類(lèi)比成十進(jìn)制、十六進(jìn)制來(lái)思考一下。實(shí)際上，我們?yōu)榱四軐⒐Ｖ德湓谡蛿?shù)據(jù)范圍內(nèi)，可以犧牲一下，允許哈希。這個(gè)時(shí)候哈希算法該如何設(shè)計(jì)呢？哈希算法的設(shè)計(jì)方法有很多，我舉一個(gè)例子說(shuō)明一下。假設(shè)字符串中只包含z這6英文字母，那我們每個(gè)字母對(duì)應(yīng)一個(gè)數(shù)字，比如abz。我們可以把字符串中每個(gè)字母對(duì)應(yīng)的數(shù)字相加，最后得到的和作為哈希值。這種哈希算法產(chǎn)生的哈希值的數(shù)據(jù)范圍就相對(duì)要小很多了。不過(guò)，你也應(yīng)該發(fā)現(xiàn)，這種哈希算法的哈希概率也是挺高的。當(dāng)然，舉了一個(gè)最簡(jiǎn)單的設(shè)計(jì)方法，還有很多更加優(yōu)化的方法，比如將每一個(gè)字母從小到大對(duì)應(yīng)一個(gè)素?cái)?shù)，而是23…這樣的自然數(shù)，這樣的概率就會(huì)降低一些。希的時(shí)候，有可能存在這樣的情況，子串和模式串的哈希值雖然是相同的，但是兩者本身并不匹配。實(shí)際上，解決方法很簡(jiǎn)單。當(dāng)我們發(fā)現(xiàn)一個(gè)子串的哈希值跟模式串的哈希值相等的時(shí)候，我們只需要再對(duì)比一下子串和模式串本身就好了。當(dāng)然，如果子串的哈希值與模式串的哈希值不相等，那對(duì)應(yīng)的子串和模式串肯定也是不匹配的，就不需要比對(duì)子串和模式串本身了。所以，哈希算法的概率要相對(duì)控制得低一些，如果存在大量，就會(huì)導(dǎo)致RK算法的時(shí)間復(fù)雜度，效率下降。情況下，如果存在大量的，每次都要再對(duì)比子串和模式串本身，那時(shí)間復(fù)雜度就會(huì)成O(n*m)。但也不要太悲觀，一般情況下，不會(huì)很多，RK算法的效率還是比BF算法高的。解答開(kāi)篇&今天我們講了兩種字符串匹配算法，BF算法和RK算法BF算法是最簡(jiǎn)單、的字符串匹配算法，它的實(shí)現(xiàn)思路是，拿模式串與主串中是所有子串匹配，看是否有能匹配的子串。所以，時(shí)間復(fù)雜度也比較高，是O(n*m)nm串和模式串的長(zhǎng)度。不過(guò)，在實(shí)際的軟件開(kāi)發(fā)中，因?yàn)檫@種算法實(shí)現(xiàn)簡(jiǎn)單，對(duì)于處理小規(guī)模的字符串匹配很好用。RK算法是借助哈希算法對(duì)BF算法進(jìn)行改造，即對(duì)每個(gè)子串分別求哈希值，然后拿子串的哈希值與模式串的哈希值比較，減少了比較的時(shí)間。所以，理想情況下，RK算法的時(shí)間復(fù)雜度是O(n)，跟BF算法相比，效率提高了很多。不過(guò)這樣的效率取決于哈希算法的設(shè)計(jì)方法，如果存在的情況下，時(shí)間復(fù)雜度可能會(huì)。情況下，哈希算法大量，時(shí)間復(fù)雜度就為O(n*m)。我們今天講的都是一維字符串的匹配方法，實(shí)際上，這兩種算法都可以類(lèi)比到二。假設(shè)有下面這樣一個(gè)二維字符串矩陣（圖中的主串），找另一個(gè)二維字符串矩陣（圖中的模式串）呢？ 科技所有 不 售賣(mài)。頁(yè)面已增加防盜追蹤，將依法其上一 31|深度和廣度優(yōu)先搜索：如何找出社交網(wǎng)絡(luò)中的三度好友關(guān)系下一 33|字符串匹配基礎(chǔ)（中）：如何實(shí)現(xiàn)文本編輯器中的查找功能精選留言 51展 14m*ni*j，橫向在[0,m-i]，縱向在[0,n-j]取起始展 …展 8h[i]=26*(h[i-1]-26^(m-1)*h[i-1])+h[i+m-h[i]、h[i-1s[is[i-1展 7轉(zhuǎn)換為一維字符后，就可以用BF或者RK算法了。m*ni*j，按一個(gè)個(gè)矩陣來(lái)展 5二維矩陣只要如果以i'j為左上角，即可定義一個(gè)i.ji+1.jij+1i+1.j+1的子串，其本質(zhì)是和展 朱月 3展煦 “h[i]26*(h[i-1]-26^(m-1)*h[i-1]h[i+m-1];h[i]、h[i-1s[is[i-符的哈希值而不應(yīng)該是子串的哈希值吧？？PS：用您的例子套用：h0=3*26*26+1*26+2=2056；h1=26*(h0-26*26*h0)+(4*26*26+3*26+4)=-展 2h[i]=26*(h[i-1]-26^(m-1)*(s[i-1]-'a'))+(s[i+m-1]-h[i]、h[i-1s[is[i-1展 RK"dbc""bce"，那么s[i-1]='d'，s[i]='b'，與'a'相減意思是，它們的ASCII碼值的差值正好表示字母的評(píng)論中有同學(xué)不明白老師給的哈希值h[i]和h[i-1]之間的關(guān)系，應(yīng)該是s[i]和s[i-展大 2h[i]=26*(h[i-1]-26^(m-1)*(s[i-1]-'a'))+(s[i+m-1]-展