String Searching

運用移位來處理字串搜尋問題

http://www-igm.univ-mlv.fr/~lecroq/string/index.html

String Searching(String Matching)

「字串搜尋」、「字串匹配」。長字串T、短字串P,從T當中找到P的位置。

字串搜尋當中,我們習慣將兩字串的象徵符號取做T和P。T代表Text,P代表Pattern。

T: ababcabc
P: abc

ababcabc    ababcabc
  |||            |||
  abc            abc

T中有兩個地方出現P。

最直覺的演算法就是窮舉法:挪動P,對準T的各個位置;逐一比對字元、判斷是否相等。時間複雜度O(TP)。

T: ababcabc
P: abc

0.         1.         2.         3.         4.         5.
ababcabc   ababcabc   ababcabc   ababcabc   ababcabc   ababcabc
|||         |||         |||         |||         |||         |||
abc         abc         abc         abc         abc         abc
(X)         (X)         (O)         (X)         (X)         (O)

String Searching: Morris–Pratt Algorithm

© 2010 tkcn. All rights reserved.

想法

1.
T: aabzabzabcz
P: abzabc

2.
窮舉法,從左往右逐步挪動P。

  aabzabzabcz   aabzabzabcz   aabzabzabcz
  ||||||         ||||||         ||||||      ......
  abzabc         abzabc         abzabc
      (X)           (X)           (X)

2.
仔細看窮舉法,是從左往右一一比對字元,一旦發現字元不同,就馬上往右挪動P。

  V              V            V              V        
  aabzabzabcz   aabzabzabcz  aabzabzabcz   aabzabzabcz
  |             |X            |             ||        
  abzabc        abzabc        abzabc        abzabc    

     V             V               V             V    
  aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
   |||          ||||          |||||         |||||X    
   abzabc       abzabc        abzabc        abzabc    

    V             V              V              V     
  aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
    X             X              |             ||       ......
    abzabc        abzabc         abzabc        abzabc 

3.
往右挪動P之前,當下比對成功的字串片段,abzab,其實可以好好利用!

         V
   aabzabzabcz    -abzab-----
    |||||X         |||||
    abzabc         abzab-

4.
觀察窮舉法的步驟順序,繼續往右挪動P,挪動一個位置、挪動兩個位置、……。

  -abzab-----   -abzab-----   -abzab-----
    ||||           |||            ||     
    abzab-         abzab-         abzab- 

   -abzab-----   -abzab-----
        |                   
        abzab-         abzab-

5.
換個觀點觀察上述行為。
挪動一個位置:看看abzab的後四個字元,是不是前四個字元。
挪動兩個位置:看看abzab的後三個字元,是不是前三個字元。
   ⋮         ⋮          ⋮

6.
如果我們預先知道abzab的「次長的相同前綴後綴」是ab,
就可以一口氣大幅挪動P,略過許多步驟:

        V                 V
  aabzabzabcz        aabzabzabcz
   |||||X      --->      ||
   abzabc                abzabc

7.
從「V」處繼續向右一一比對字元。
每當比對失敗、遇到相異字元,
就故技重施,從當前比對成功的字串片段,取其「次長的相同前綴後綴」,大幅挪動P。

Prefix-Suffix【尚無正式名稱】

前綴等於後綴,稱作「相同前綴後綴」。一個字串通常有許多個「相同前綴後綴」。

         prefix-suffix
abc     --------------> {Ø, abc}
abcaa   --------------> {Ø, a, abcaa}
abcabc  --------------> {Ø, abc, abcabc}
ababa   --------------> {Ø, a, aba, ababa}
aaaaa   --------------> {Ø, a, aa, aaa, aaaa, aaaaa}
abaabaa --------------> {Ø, a, abaa, abaabaa}
abzab   --------------> {Ø, ab, abzab}

Border(Longest Proper Prefix-Suffix)

一個字串的「最長的相同前綴後綴」就是原字串,「最短的相同前綴後綴」就是空字串,「次長的相同前綴後綴」就是第二長的相同前綴後綴。「次長的相同前綴後綴」簡稱「邊框」。

         border
abc     -------> Ø
abcaa   -------> a
abcabc  -------> abc
ababa   -------> aba
aaaaa   -------> aaaa
abaabaa -------> abaa
abzab   -------> ab

Border Table(Prefix Function)(Failure Function)

窮舉法的過程當中,當前比對成功的字串片段,是P的前綴。

因為我們無法預測是P的哪幾個前綴,所以我們可以預先計算P的每個前綴的邊框,預先建立「邊框表格」,以備不時之需!

   012345
P: abzabc

prefix | border | border table   | implementation
-------|--------|----------------|----------------
Ø      | Ø      | f(Ø)      = Ø  | 
a      | Ø      | f(a)      = Ø  | border[0] = -1
ab     | Ø      | f(ab)     = Ø  | border[1] = -1
abz    | Ø      | f(abz)    = Ø  | border[2] = -1
abza   | a      | f(abza)   = a  | border[3] =  0
abzab  | ab     | f(abzab)  = ab | border[4] =  1
abzabc | Ø      | f(abzabc) = Ø  | border[5] = -1

Border Table的演算法是Dynamic Programming。利用已知邊框,求得當前邊框。分割問題的方式是p[0...i]拿掉尾端字元p[i]。

【註:取名Border Table,由於函數輸出是Border。取名Prefix Function,由於函數輸入是Prefix。取名Failure Function,由於比對失敗就會使用它。】

演算法

一、預先計算P的每種前綴的「次長的相同前綴後綴」。
二、從左往右,依序比對字元。
 回、當比對成功、遇到相同字元:
   繼續比對下個字元。
 回、當比對失敗、遇到相異字元:
   從比對成功的字串片段,取其「次長的相同前綴後綴」,大幅挪動P。
 回、當全部比對成功、搜尋到P:
   就從比對成功的P,取其「次長的相同前綴後綴」,大幅挪動P。

時間複雜度

一、Border Table:字元兩兩比對次數最多2P次。

當比對成功,邊框長度增長;當比對失敗,邊框長度減短。總共增長P次、最多減短P次。邊框長度最多變動2P次。邊框長度變動次數即是字元兩兩比對次數。

二、字串搜尋:字元兩兩比對次數最多2T次。

原理同上。「邊框長度」改成「比對成功的字串片段長度」。

總時間複雜度O(T+P)。

UVa 455 10298 11475

Morris–Pratt Automaton

此演算法可以化作自動機,轉化的時間複雜度是O(PA),A為字元種類數目。

針對每個狀態,找出經由Border Table能到達的狀態們;建立轉移邊,連到那些狀態們的下一個狀態。

化作自動機之後,字串搜尋變得非常簡單,容易製作成電路。

ICPC 4842

Multiple String Searching: Aho–Corasick Algorithm

Multiple String Searching(Multi-pattern String Matching)

「多重字串搜尋」。一口氣搜尋P₁ ... Pₙ。

最直覺的演算法就是n次Morris–Pratt Algorithm,時間複雜度O((T+P₁) + ... + (T+Pₙ)) = O(Tn+P)。

以下介紹更快的演算法,時間複雜度O(T+P+K)。

Prefix Tree與Suffix Link

Morris–Pratt Algorithm的進化版本。

所有P併成一棵Trie。在所有P之中尋找「次長的相同前綴後綴」。「預先計算每個前綴的Border」變成了「預先計算每個節點的Suffix Link」。

Dictionary Suffix Link

【註:原始論文無此概念。】

字串搜尋,當搜尋到某個P,必須檢查其餘P是否也相符。

一、若P不含父子字串:不需要檢查。

二、若P包含父子字串(一個字串是另一個字串的子字串):每個節點必須額外行走Suffix Link,以找到所有相符的P。

額外添上Dictionary Suffix Link,以迅速找到所有相符的P。

           suffix link:相同前綴後綴、不含自身、盡可能長。
dictionary suffix link:相同前綴後綴、不含自身、盡可能長、必須是某個P。

演算法

一、所有P建立一棵trie。
二、添上suffix link、dictionary suffix link。
三、拿T做字串搜尋:
 回、比對成功、遇到相同字元:走trie edge。
 回、比對失敗、遇到相異字元:走suffix link。
 回、找到所有相符的P:走dictionary suffix link。
  (若P不含父子字串,則不需走。)
  (只想找到任意一個相符的P,則不需走。)

時間複雜度

一、建立Trie:O(P₁ + ... + Pₙ) = O(P)。

二、字串搜尋:O(T+K)。K是出現次數,最小是0,最大是O(Tn)。

總時間複雜度O(T+P+K)。

UVa 10679 ICPC 4670

Aho–Corasick Automaton

此演算法可以化作自動機,轉化的時間複雜度是O(NA),N為Trie的節點數目,A為字元總類數目。轉化原理如同Morris–Pratt Automaton。

Dictionary Suffix Link無法融入到自動機裡面,必須額外記錄。

UVa 11468 ICPC 3124 5103

Wildcard Searching: Pinter's Algorithm

Wildcard Searching(Wildcard Pattern Matching)

「萬用字元搜尋」。P含有萬用字元。

演算法

將P拆成一段一段不含萬用字元的字串,然後使用Multiple String Searching求出各小段在T中的出現位置,看看P的所有小段是否同時出現、是否位置不重疊。時間複雜度O(T+P+K)。

UVa 475 12785

2D String Searching: Baker–Bird Algorithm

2D String Searching(2D Pattern Matching)

「二維字串搜尋」。T與P是二維長方形。

演算法

時間複雜度O(T+P)。

1.
把T橫切成一條一條,
把P橫切成一條一條,
然後每一條T都執行Multiple String Searching,例如Aho–Corasick Algorithm。
如果第a條P,從T[i][j]開始出現,那麼就進行記錄:M[i][j] = a。
M是一個跟T一樣大的陣列。

2.
把M直切成一條一條,
每一條M都執行String Searching,例如Morris–Pratt Algorithm。
看看是否出現1234567...n這個字串(P總共n條)。

X.
當P有某兩條相同時,則要小心處理,把這兩條的編號設為相同。

附帶一提,如果使用Aho–Corasick Algorithm,因為P不含父子字串,所以不必建Dictionary Suffix Link,省下很多功夫。

UVa 11019

String Searching: Knuth–Morris–Pratt Algorithm

演算法

          v
T: aaaabcacab
P:    abcabcacab
          ^

Morris–Pratt Algorithm當中,當比對到上圖之處,c != b,所以需要向右挪動P。找到abca的「次長的相同前綴後綴」,也就是a。然後向右挪動P,最後左端凸出一段a,如下圖所示。

          v
T: aaaabcacab
P:       abcabcacab
          ^

接下來就繼續比對字元。在這裡c != b,所以又要挪動P了。

Knuth則是多想了一步:連續挪動P,能不能預先偵測呢?Knuth發現,找到abca的「次長的相同前綴後綴」a之後,看看a的下一個字元(是b),是否仍是abca的下一個字元(也是b)。如果兩個字元一樣,那就表示P鐵定會連續挪動兩次,兩次比較都是c != b。

既然鐵定會挪動兩次,那乾脆直接移到定位不就好了?於是Knuth在計算Border Table的時候,就額外加了一個判斷:找到abca的相同前綴後綴f(abca) = a之後,如果f(abca)的下一個字元恰巧仍是abca的下一個字元,那麼就令f(abca) = f(a),也就是再多找一次a的相同前綴後綴。如此一來,P只要移一次就行了。

由於f()是遞迴定義,所以連續挪動三次、四次、五次的情況,經過遞迴計算,最後都會變成一次移到定位。

Border Table變慢、字串搜尋變快。時間複雜度仍是O(T+P)。

String Searching: Boyer–Moore Algorithm

演算法

http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

每次向右挪動P,有著good-suffix shift與bad-character shift兩種挪動選項,選擇向右挪動較多者。

每次挪動P之後,從P的右端、往P的左端比對字元。

good-suffix shift

P的每個後綴,找到本身以外,最後出現的地方。

若沒重複出現,則找到「次長的相同前綴後綴」。即是Border Table,函數輸入變成後綴罷了。

計算good-suffix shift表格的時間複雜度是O(P)。

bad-character shift

P的每個字元,找到最後出現的地方。

注意到bad-character shift可能向左挪動。

計算bad-character shift表格的時間複雜度是O(P+A)。A為字元種類數目。

時間複雜度

字串搜尋,最差時間複雜度O(TP),此時T與P的全部字元皆相同;最佳時間複雜度O(T/P),此時T與P沒有共同的字元。

當T與P並非週期性字串,字元兩兩比對次數最多3T次。

號稱實務上最快的演算法。

可以直接使用STL的boyer_moore_searcher()。

String Searching: Horspool's Algorithm

演算法

http://www-igm.univ-mlv.fr/~lecroq/string/node18.html

只使用bad-character shift。容易實作。

可以直接使用STL的boyer_moore_horspool_searcher()。

Multiple String Searching: Wu–Manber Algorithm

想法

硬是拿Horspool's Algorithm來做多重字串搜尋。

比對單位改為B個字元,用hash function併為一數。

演算法

一、只看每個P的左端m個字元,暫時忽略右端其餘字元。
  P長度最短者,取作m。
二、預先建立SHIFT table、HASH table、PREFIX table。
三、實施Horspool Algorithm,
  比對單位改為B個字元,挪動單位仍是一個字元。
  直接從SHIFT table取值,判斷比對成功、比對失敗。
 回、B個字元比對失敗:
  甲、SHIFT table,根據其值,向右挪動P。
 回、B個字元比對成功:
  甲、P的後綴在T中:
    HASH table,得到後綴是這B個字元的所有P。
  乙、P的前綴在T中:
    PREFIX table,得到這些P的前綴、B個字元,判斷是否也在T出現。
    T的當前比對位置往左數m個字元,就能進行判斷了。
  丙、P的其餘片段在T中(只有這裡是看P的全部字元):
    逐個字元比對,方向隨便。若找到整個P,就輸出。
  丁、向右挪動P、一個字元。

SHIFT table

輸入B個字元,找到整個P之中最後出現的地方。

時間複雜度O(PB),空間複雜度O(Aᴮ),A是字元種類數目。

HASH table

輸入後綴、B個字元,得到符合條件的所有P。

時間複雜度、空間複雜度同SHIFT table。

PREFIX table

輸入其中一個P,得到前綴、B個字元。

時間複雜度O(nB),空間複雜度O(n),n是P的個數。

時間複雜度

字串搜尋,最差時間複雜度O(BTP),此時T與P的全部字元皆相同。最佳時間複雜度O(BT/m),此時T與P沒有共同的連續B個字元。

String Searching: Gusfield's Algorithm

Common Prefix

多個字串的相同前綴,稱作「共同前綴」。通常有許多個。

               common prefix
{abc, abcde}  --------------> {Ø, a, ab, abc}
{abc, ab, a}  --------------> {Ø, a}
{abc, bc, de} --------------> {Ø}

Longest Common Prefix

多個字串的「最長共同前綴」。

                    lcp
{abc, abcde}  --------------> abc
{abc, ab, a}  --------------> a
{abc, bc, de} --------------> Ø

Prefix Table(Z Function)

s[0]開始的字串、s[i]開始的字串,兩者的最長共同前綴,儲存至「前綴表格」的z(i)。s[0 ... z(i)-1] = s[i ... i+z(i)-1]。

  | 0 1 2 3 4 5 6 7
--+-----------------
s | a b a a b a a b
z | 8 0 1 5 0 1 2 0

z(0):abaabaab,長度8。
z(1):Ø,長度0。
z(2):a,長度1。
z(3):abaab,長度5。

z(0)是整個字串的長度。由z(1)開始算。

計算z(i),是運用已經算好的z(j),j < i。也就是指已經算好的某一段s[0 ... z(j)-1] = s[j ... j+z(j)-1]。首先找出哪一段s[j ... j+z(j)-1]覆蓋了s[i],而且j+z(j)-1越右邊越好。

一、如果沒有任何一段s[j ... j+z(j)-1]覆蓋了s[i],表示已經算好的部份都派不上用場。從s[i]與s[0]開始比對,逐字比下去。

二、如果有一段s[j ... j+z(j)-1]覆蓋了s[i],表示s[i]也會出現在s[0 ... z(j)-1]之中,把i映射到對應的位置i'。緊接著再來一次,運用z(i'),也就是指s[0 ... z(i')-1] = s[i' ... i'+z(i')-1],如此又把i'映射到字串開頭了。

二之一、如果s[i ... i+z(i')-1]短少於s[j ... j+z(j)-1]的右端,那就可以直接算出z(i)的答案,就是z(i')。

二之二、如果s[i ... i+z(i')-1]剛好貼齊s[j ... j+z(j)-1]的右端,那就必須檢查不確定的部分,直接從s[j+z(j)]與s[j+z(j)-i]繼續比對,逐字比下去。

二之三、如果s[i ... i+z(i')-1]凸出了s[j ... j+z(j)-1]的右端,則與上一種情形相同。

j便是原著中的L,j+z(j)-1便是原著中的R。

演算法

製做P + $ + T,也就是說,P接到T開頭,中間用一個從未出現的字元隔開。然後算z(),看看哪些z(i)剛好是P的長度。

實作時,不必真的銜接T與P。先計算P的z(),再以此計算P + $ + T的z()。

時間複雜度

字元兩兩比對次數最多2(P+1+T)次。時間複雜度O(T+P)。

當比對成功,共同前綴長度增長;當比對失敗,長度減短。總共增長(P+1+T)次、最多減短(P+1+T)次。長度最多變動2(P+1+T)次。共同前綴長度變動次數即是字元兩兩比對次數。

Gusfield's Algorithm vs. Morris–Pratt Algorithm

Gusfield's Algorithm:
最長共同前綴(Longest Common Prefix)的表格(Prefix Table)
演算法是兩個步驟prefix(P,P)和prefix(T,P)

Morris–Pratt Algorithm:
次長相同前綴後綴(Longest Proper Prefix-Suffix)的表格(Border Table)
演算法是兩個步驟border(P,P)和border(T,P)

UVa 11022 ICPC 4759

String Searching: Two Way Algorithm

演算法

https://www-igm.univ-mlv.fr/~lecroq/string/node26.html

Cache-efficient Algorithm。存取記憶體相當花費時間,節省記憶體以節省時間。不建立表格,額外記憶體空間是O(1)。

當表格沒有優勢,也就是說,當T與P不會重複出現子字串,那麼此演算法是實務上最快的演算法。

可以直接使用glibc的strstr()。水很深,此處不展開。