簡單又快速的字串搜尋演算法

在一篇很長的文章或是一大串文字中找出自己想看到的段落是我們時常會需要做的事情,但是要如何有效率地讓電腦尋找文字中的文字是一件需要思考的事情,甚至有許多針對這個議題所提出的研究論文。字串搜尋演算法的好壞,在複雜的文件內容下,對搜尋時間的影響是非常深遠的。字串搜尋除了能夠正確搜尋一段文字內的特定字串外,還可以用來搜尋龐大的任意資料,因為任何的資料都可以藉由數位編碼轉成只有數字的字串,如一段原始的聲音,一段原始的影片,甚至是一段生物基因。

字串搜尋演算法─暴力法

最直覺簡單搜尋文字的方法,就是將原文內的所有文字全都看過一次,並在過程中逐一比對文字的字母符號是否就是要找的文字。這樣的作法被稱為是「暴力法」,採用地毯式的搜索,雖然很直覺,但是會重複搜尋到好幾次同樣的地方。舉例來說:

我們現在要搜尋以上這段文字內所有的「EXAMPLE」字串,該如何進行呢?

首先先看到這段文字的第一個字母「H」,再看看我們要搜尋的「EXAMPLE」字串的第一個字母。嗯……「H」和「E」不同,所以這裡並不是「EXAMPLE」字串。

接著在來看這段文字的第二個字母「E」,再看看我們要搜尋的「EXAMPLE」字串的第一個字母。嗯……「E」和「E」相同,這有可能就是我們要找的字!但還不能大意,接著再來看看下一個字母。

這段文字的第三個字母是「R」,再看看我們要搜尋的「EXAMPLE」字串的第一個字母。嗯……「R」和「X」不同,所以這裡並不是「EXAMPLE」字串。

經過兩次的碰壁,我們的字串比對過程終於往前邁進了一點點了。接著重新看文字中的第三個字母「R」和「EXAMPLE」字串的第一個字母「E」是不是相同。嗯,不相同,再往前看。

依此類推,尋找字串的過程如下:

如此一來,找到最後,可以知道「EXAMPLE」字串開始於文字中索引第17, 50, 84, 91的位置。

暴力字串搜尋演算法的Java程式碼範例如下(參考即可,不建議使用):

若要做反向搜尋,過程如下:

如此一來,找到最後,可以知道「EXAMPLE」字串開始於文字中索引第91, 84, 50, 17的位置。
反向暴力字串搜尋演算法的Java程式範例如下(參考即可,不建議使用):

字串搜尋演算法Boyer-Moore-MagicLen

為了避免混淆,這邊把要在文字內搜尋的字串稱為「樣本(pattern)」,而要搜尋樣本的文字稱為「原文(source)」。

Boyer-Moore-MagicLen是筆者結合Boyer-Moore-HorspoolQuick Search Algorithm得出的演算法,這兩種都是Boyer-Moore演算法的簡化作法。

Boyer-Moore演算法是從字串尾端開始往前進行字元比對,再搭配「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift)的方式,將字串想辦法一次位移最多個字元的距離(若同時能進行好後綴位移壞字元位移,則選擇能夠位移最多的方式),直接對齊下一次可能會找到完全符合樣本的原文字元位置,來加速字串搜尋

什麼是「好後綴」和「壞字元」呢?如果要用口語描述的話,「好後綴」為目前位置之樣本和原文相符的字串後綴;「壞字元」為目前位置之樣本和原文從後面判斷第一個出現的不相符字元,就是好後綴開頭的前一個字元。

好後綴位移」和「壞字元位移」的位移方式可以預先在尚未知道原文的時候,單靠樣本來建立。建立好樣本的「好後綴位移表」和「壞字元位移表」之後,無論遇到怎麼樣的原文,都可以使用這個樣本和預先處理過的表格對原文進行非常快速的字串搜尋

這邊一直在講位移、位移,到底是在位移什麼呢?這個部份將在接下來的Boyer-Moore-MagicLen來介紹。

由於「好後綴位移表」要建立出來並不容易,需要額外的初始化負擔。因此Boyer-Moore-HorspoolQuick Search Algorithm將「好後綴位移」拿掉,僅需要建立出「壞字元位移表」。而Boyer-Moore-MagicLen是整合Boyer-Moore-HorspoolQuick Search Algorithm之後的演算法,在多數情況下會比Boyer-Moore-Horspool或是Quick Search Algorithm都還要更快。

Boyer-Moore-MagicLen的原理拆解

直接舉個例子來逐步說明Boyer-Moore-MagicLen演算法:

我們現在要搜尋以上這段文字內所有的「EXAMPLE」字串,該如何進行呢?

一開始的時候,要搜尋的樣本於原文中索引0的位置。

接著依尋Boyer-Moore演算法的方式,從樣本尾端開始判斷目前位置之樣本和原文是否符合。在這裡「EXAMPLE」的尾端「E」,所對應的原文字元是「S」,並不相同,而這個「S」即為「壞字元」。

由於知道這個位置的原文並不符合樣本,因此要將樣本位移,去判斷其他位置的原文。在取最大位移量的原則下來看,我們先來看看樣本尾端位置的下一個原文字元是什麼。沒錯,就是「S」字元之後的空格字元「 」。

但是空個字元在樣本內並不存在,因此我們可以知道樣本的開頭要至少位移到超過這個空格字元,才有可能在位移後的位置中,於原文找到完全符合的字串。因此我們將樣本向右位移等同自身長度加一的距離,這樣的位移方式稱為「尾端後字元位移」。

位移後的樣本與原文,位置關係如下:

接著同樣再依尋Boyer-Moore演算法的方式,從樣本尾端開始判斷目前位置之樣本和原文是否符合。在這裡「EXAMPLE」的尾端「E」,所對應的原文字元是「L」,並不相同,而這個「L」即為「壞字元」。

由於再度知道這個位置的原文並不符合樣本,因此要將樣本位移,去判斷其他位置的原文。又是在取最大位移量的原則下來看,我們找到樣本尾端位置的下一個原文字元是「E」。

字元「E」存在於樣本中,從尾端往前數的話,是在倒數第一個位置,因此樣本只需往右移動一格,就可以讓樣本的字元「E」以及原文的字元「E」互相對齊。在這裡先不要輕舉妄動,為了真正達成最大位移量的原則,可以再來看看壞字元「L」於樣本中的位置。

字元「L」存在於樣本中,從尾端往前數的話,是在倒數第二個位置,因此樣本只需往右移動一格,就可以讓樣本的字元「L」以及原文的字元「L」互相對齊。剛好與字元「E」的位移距離不謀而合,所以也沒得好選了。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元也是「E」;再繼續看到「EXAMPLE」的尾端第二個字元「L」,所對應的原文字元也是「L」;看到第三個字元「P」,所對應的原文字元也是「P」;看到第四個字元「M」,所對應的原文字元也是「M」。再來看到「EXAMPLE」的尾端第五個字元「A」,所對應的原文字元是「I」,兩者並不相同,此時壞字元為「I」,並出現了長度是4的好後綴「MPLE」。

在取最大位移量的原則下來看,我們找到樣本尾端位置的下一個原文字元是空格字元「 」。與先前在尾端的下一個位置的字元出現空格字元的理由一樣,我們將樣本向右位移等同自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

重做上面的步驟從樣本尾端開始檢查字元,發現這個位置正好符合我們要找的樣本。那如果要繼續搜尋下去的話該怎麼做呢?在這時候因為壞字元並不存在,所以完全不用考慮壞字元了,只需找到樣本尾端位置的下一個原文字元。我們找到「,」,發現「,」並未出現在樣本中,理由和先前的空格字元一樣,直接將樣本向右位移等同自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元是「 」,所以要再次移動樣本自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元是「 」,所以依然要再次移動樣本自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元是「L」,兩者並不相同,壞字元為「L」。

我們找到樣本尾端位置的下一個原文字元是「E」,樣本需要向右位移1格來對齊。而壞字元「L」,樣本也需要向右位移1格來對齊。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元也是「E」;再繼續看到「EXAMPLE」的尾端第二個字元「L」,所對應的原文字元也是「L」;看到第三個字元「P」,所對應的原文字元也是「P」。再來看到「EXAMPLE」的尾端第四個字元「M」,所對應的原文字元是「I」,兩者並不相同,此時壞字元為「I」,並出現了長度是3的好後綴「PLE」。

在取最大位移量的原則下來看,我們找到樣本尾端位置的下一個原文字元是空格字元「 」。與先前在尾端的下一個位置的字元出現空格字元的理由一樣,我們將樣本向右位移等同自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

重做上面的步驟從樣本尾端開始檢查字元,發現這個位置也正好符合我們要找的樣本。直接找到樣本尾端位置的下一個原文字元「S」,發現「S」並未出現在樣本中,理由和先前的空格字元一樣,直接將樣本向右位移等同自身長度加一的距離。

位移後的樣本與原文,位置關係如下:

在這裡「EXAMPLE」的尾端「E」,所對應的原文字元也是「E」;再繼續看到「EXAMPLE」的尾端第二個字元「L」,所對應的原文字元也是「L」。但看到第三個字元「P」時,所對應的原文字元是「X」,兩者並不相同,因此此時壞字元為「X」,並且有長度為2的好後綴「LE」。

在取最大位移量的原則下來看,我們找到樣本尾端位置的下一個原文字元是字元「E」。我們需要將樣本向右位移1才能讓樣本的字元「E」以及原文的字元「E」互相對齊。

與此同時,壞字元「X」則需要讓樣本向右位移3格,才可以讓樣本的字元「X」以及原文的字元「X」互相對齊。

在取最大位移量的原則下,我們當然要選擇向右位移3格。

至於為什麼可以這樣子移動,是因為壞字元必定出現在樣本尾端後一個字元之前,若只選擇移動比較少距離來對齊樣本尾端後的一個字元,原文中的壞字元必定和樣本對應位置的字元不同,因為位移量尚未達到壞字元對齊的需求。我們不需要做這個早就可以透過推論知道結果的位移動作,因此直接選擇使用最大的位移量即可。

位移後的樣本與原文,位置關係如下:

按照上面描述的方式位移,可以將整個過程紀錄如下:

有沒有發現,使用這樣的方式來搜尋字串,判斷字元是否相等的次數比暴力法還要少太多了!計算時間當然也會有突飛猛進的成長。

Boyer-Moore-MagicLen的位移表

了解Boyer-Moore-MagicLen的運作原理後,接著來談談怎麼樣才能快速進行「壞字元位移」或是「尾端後字元位移」?

其實不論是「壞字元位移」或是「尾端後字元位移」,都是要想辦法讓樣本在位移之後能夠對齊目標字元。因此這樣的位移是基於字元從樣本尾端往前尋找出現第一次的位置,我們只要找出所有字元在樣本內從尾端看到前端第一次出現的位置即可。

由於要存放「所有字元」的位置資訊,我們的表格長度將會等同於字元的數量。

Java程式語言中,基本資料型態char所使用的空間大小為2個位元組,因此它擁有表示65536種不同字元的能力。想要在Java程式語言中建立位移表,可以建立出一個長度為65536的整數陣列。

然後初始化這個整數陣列所有的元素值,筆者將預設值定為樣本的長度,也就是樣本每次最大的位移量減一。至於為什麼這裡要「位移量減一」,實際上跟程式的邏輯設計有關,重要的是,這個值必須是這個陣列裡的最大值。

接著開始找出樣本內的每個字元,從樣本尾端開始第一次出現的位置。以樣本「EXAMPLE」來說,可以建出下表:

shiftMap['E'] = 0;
shiftMap['X'] = 1;
shiftMap['A'] = 2;
shiftMap['M'] = 3;
shiftMap['P'] = 4;
shiftMap['L'] = 5;
shiftMap[other] = 7;

這個樣本「EXAMPLE」剛好是一個特殊的例外,它尾端的「E」在前面也有出現過,因此在這裡要進行一個特殊處理。先舉個例子:

在這個例子中,壞字元為「E」,但此時樣本的尾端就是「E」,該如何利用上面建立好的表來順利讓樣本從尾端開始除了尾端第一個出現的「E」和原文的「E」能夠對齊呢?難道只能使用「尾端後字元位移」讓樣本向右位移1格嗎?好沒效率呀!明明這個例子一看就能直覺反應,樣本可以使用「壞字元位移」向右位移5格來對齊壞字元的……

筆者這邊的解決方案是,將樣本尾端定義為特殊字元(special character),然後紀錄這個特殊字元從尾端前(不包含尾端)第一次出現的位置。在樣本「EXAMPLE」中,特殊字元為「E」,特殊字元的位置為「6」。

透過位移表和特殊字元,可以輕易地計算出「壞字元位移量」和「尾端後字元位移量」,筆者的計算方式如下:

若是壞字元是特殊字元,則:

壞字元位移量 = 特殊字元的位置 - 好後綴的長度

隨便拿剛才特殊字元的例子來算,壞字元位移量為6-1=5。

若是壞字元不是特殊字元,則:

壞字元位移量 = 於位移表取得壞字元的位置 - 好後綴的長度

尾端後字元位移量的算法更簡單:

壞字元位移量 = 於位移表取得壞字元的位置 + 1

Boyer-Moore-MagicLen的程式實作

Boyer-Moore-MagicLen的程式實作之反向搜尋

搜尋過程如下:

程式實作:

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章