String Matching

運用位移來處理字串匹配問題

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

String Matching

中譯「字串匹配」。兩個字串T和P,找出T當中是否有一段字串正好是P,並且找出位置。

註:字串匹配當中,我們通常將兩字串的象徵符號取做T和P,T意指text,P意指pattern。可以想作是從長篇文字T之中搜索小段文字P。

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 Matching: 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}

longest proper prefix-suffix(border)

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

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

failure function(prefix function)(border function)

窮舉法的過程當中,當前比對成功的字串片段,是P的前綴。因為我們無法預測是P的哪幾個前綴,所以我們可以預先計算P的每一個前綴的「次長的相同前綴後綴」,以備不時之需!

failure function是一個字串函數:輸入字串的其中一個前綴,則輸出該前綴的「次長的相同前綴後綴」。

012345
abzabc

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

計算failure function,一般是利用Dynamic Programming。分割問題的方式,是P[0...i]拿掉尾端字元P[i],利用已知的「次長的相同前綴後綴」,得到P[0...i]的「次長的相同前綴後綴」。

【待補圖片】

稱作failure function,是因為比對失敗時,就會使用它。稱作prefix function,是因為此函數的定義域是prefix。稱作border function,是因為此函數的值域是border。

字串匹配

字串匹配的過程,跟failure function的計算過程十分相像。

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

也來個流程圖的版本。

甲、移動「V」。
  (下一步為乙。)
乙、比對兩字元。
  (若相同,下一步為甲或戊。若不同,下一步為丙。)
丙、從目前比對成功的字串片段,找到「次長的相同前綴後綴」。
  (下一步為丁。)
丁、向右挪動P,左端僅露出一截「次長的相同前綴後綴」。
  (下一步是乙。)
戊、整個P匹配成功。
  (下幾步是丙、丁、甲。)
  (當字串結尾附有'\0',則下一步是甲。)

時間複雜度:multipop stack的均攤分析

在講解時間複雜度之前,先討論一個基礎問題。

有一個stack,一開始是空的。它有三種操作。

1. push(x)      - worst time O(1)
2. pop()        - worst time O(1)
3. multipop(k)  - 連續pop出k個元素,如果stack是空的就馬上停止。
                  worst time O(min(k,s)),當stack恰有s個元素的時候。

請問這個stack進行N次操作的時間複雜度為多少?
我們不知道每次的操作是哪一種。可能是三種其中一種。

甲、普通的分析:

乍看之下,花費最多時間的就是multipop,於是我們就以multipop的觀點來計算時間複雜度。

一次multipop的時間複雜度是O(min(n,k)),n是stack當下的元素個數,k是欲pop的元素個數;由於n和k最大可到N,所以寫成O(N)。

multipop最多有N次,N次的multipop是O(N²),因此時間複雜度就是O(N²)。

乙、均攤分析:

N次操作,stack從頭到尾最多只能放入N個元素,也就是N次push。

也就是說,stack從頭到尾最多只能彈出N個元素。無論是pop、multipop,最多只能彈出N個元素。

由放入的元素、彈出的元素的總數量,來計算時間複雜度;這兩個數量相加最多就是N,因此時間複雜度就是O(N)。

時間複雜度

接著回到Morris-Pratt Algorithm。分為兩部分討論。

甲、進行字串匹配的過程:

以字元兩兩比對的總次數,作為時間複雜度。

當下比對成功的字串片段S,想成是stack的元素。一開始S長度是零;如果比對到相同字元,S就會增加一字元,想成是push;如果比對到不同字元,大幅挪動P之後,S就只剩下「次長的相同前綴後綴」,一瞬間變短很多,想成是multipop。(實際上,一瞬間變短很多只需要O(1),時間複雜度遠比multipop來的小。)

最多有T個字元放入S、彈出S,所以字元兩兩比對的總次數不超過2T次。

換個方式說。對於T的某一個字元來說,與其他字元進行比對的次數,小於等於「當下比對成功的字串片段」的長度。「當下比對成功的字串片段」是動態改變的,如同stack一樣增減,所以字元兩兩比對的總次數不超過2T次。

乙、計算P的failure function的過程:

原理與甲相同,字元兩兩比對的總次數不超過2P次。

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

UVa 455 10298 11475

Morris-Pratt Automaton

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

化作自動機之後,字串匹配的過程就變得更簡單了,甚至可以設計成電子迴路。

轉化的原理,是針對每個狀態,都找出經由failure function能到達的狀態們,然後建立轉移邊,連到那些狀態們的下一個狀態。

【待補程式碼】

ICPC 4842

String Matching: 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在計算failure function的時候,就額外加了一個判斷:找到abca的相同前綴後綴f(abca) = a之後,如果f(abca)的下一個字元恰巧仍是abca的下一個字元,那麼就令f(abca) = f(a),也就是再多找一次a的相同前綴後綴。如此一來,P只要移一次就行了。

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

延遲時間

當T是一個stream I/O、讀入字元只能一個一個來的情況下,每讀入一個字元最多會有1+logφP次字元比較。換句話說,每讀入一個字元,直到需要讀取下一個字元前,期間最多會停滯O(logφP)的時間。

【待補證明】

Multi-Pattern String Matching: Aho-Corasick Algorithm

suffix link

【註:原始論文是failure function與output function】

Morris-Pratt Algorithm的加強版,同時匹配數個P。預先把所有P建立成一棵trie,每個節點添上failure function,之後就可以拿trie與T進行字串匹配了。

Morris-Pratt Algorithm是找到「當下比對成功的字串片段」的後綴(不含本身),是P的哪一個前綴。盡可能長。

Aho-Corasick Algorithm是找到「當下比對成功的字串片段」的後綴(不含本身),是哪一個P的哪一個前綴。盡可能長。

因此,failure function其實就是尋找trie上每個節點的後綴(不含本身),盡可能長。直覺的稱呼是suffix link。

dictionary suffix link

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

當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(P1 + ... + Pn) = O(∑(Pi)) = O(P)。

字串匹配的時間複雜度是O(T + K),K是每個P在T中的出現次數的總和。K最小為0,K最大為O(T ⋅ n)。

【註:原始論文中,字串匹配的時間複雜度是O(T + P + K)。當數個T做字串匹配,將慢許多。】

UVa 10679 ICPC 4670

使用n次Morris-Pratt Algorithm

同時匹配數個P,也可以用n次Morris-Pratt Algorithm,總時間複雜度就是O((T+P1) + ... + (T+Pn)) = O(T ⋅ n + P),慢許多。

使用Suffix Tree

同時匹配數個P,也可以替T建立一棵Suffix Tree,看看樹上有沒有各個P。時間複雜度與Aho-Corasick Algorithm相同。

T固定,適合用Suffix Tree;P固定,適合用Aho-Corasick Algorithm。

Aho-Corasick Automaton

此演算法可以化作自動機,轉化的時間複雜度為O(NA),N為Trie的節點數目,A為字元總類數目。與Morris-Pratt Automaton的建構原理一模一樣。

dictionary suffix link無法融入到自動機裡面,必須額外記錄。

UVa 11468 ICPC 3124 5103

延伸閱讀:Wild Card String Matching

當P中含有萬用字元「?」的時候,可以將P拆成一段一段不含萬用字元的部份,然後使用Multi-Pattern String Matching求出各小段在T中的出現位置,然後位移對齊一下(根據各小段在P中的位置),看看P的所有小段是否同時出現,即代表是否有匹配。時間複雜度是O(T+P)。

UVa 475 12785

2D String Matching: Baker-Bird Algorithm

演算法

當T與P是二維長方形的時候。時間複雜度是O(T+P)。

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

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

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

附帶一提,如果是使用Aho-Corasick Algorithm,因為P中不會有父子關係,所以不必建dictionary suffix link,省下很多功夫。

UVa 11019 Timus 1486

String Matching: Gusfield's Algorithm(Z Algorithm)

z function

定義一個函數z(),z(i)是指由s[i]開始的字串,與s[0]開始的字串可以匹配到多長。也就是說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,就得問原作者了。後面將提到如何運用z function作字串匹配,現在先講解如何計算z function。

計算z(),是從左往右算。z(0)是特例,z(0)是整個字串的長度,所以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+z(j)-1這個數值會從0開始不斷增加。每當字元比對成功時,j+z(j)-1就會跟著增加,下次比對的時候就會從j+z(j)繼續比對。j+z(j)-1這個數值的增加次數與比對次數一樣多,最多會從0增加到S,所以時間複雜度是O(S)。

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

字串匹配

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

實作時,不必真的銜接T與P。先計算P的z function,再以此計算T的z function就可以了。時間複雜度為O(T+P)。

Gusfield's Algorithm點明了字串匹配的精髓:兩個字串的「共同前綴」。Morris-Pratt Algorithm則是Gusfield's Algorithm的另外一面,兩者關係互補。

Gusfield's Algorithm  :一個字串的每個後綴之中,與字串開頭相同的最長前綴。
Morris-Pratt Algorithm:一個字串的每個前綴之中,與字串開頭相同的次長後綴。
一、T與P的最長共同前綴(Longest Common Prefix)
 適用情況:T為定值,P為變動值。
 單一字串匹配:Gusfield's Algorithm。(P為定值,T為變動值。)
 單一、多重字串匹配:Suffix Array + Binary Search、Suffix Trie、Suffix Tree。
 特色:LCP Array。

二、P本身的次長相同前綴後綴(Longest Proper Prefix-Suffix)(Border)
 適用情況:P為定值,T為變動值。
 單一字串匹配:Morris-Pratt Algorithm。
 多重字串匹配:Aho-Corasick Algorithm。
 特色:可以轉換成自動機。

UVa 11022 ICPC 4759

String Matching: 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的每個後綴,找到本身以外,最後出現的地方。

若沒重複出現,則找到「次長的相同前綴後綴」。即是failure function,定義域變成後綴罷了。

計算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次。

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

Multi-Pattern String Matching: Wu-Manber Algorithm

大意

硬是拿Boyer-Moore Algorithm來做多重字串比對,工程味道濃厚的演算法。

向右挪動P,只有bad-character shift一種挪動選項。

比對單位由一個字元,改為B個字元。個人推敲其用意如下:

一、B取logA∑(Pi),能降低理論上的時間複雜度。

二、過去在Big5編碼中(現今多採UTF-8編碼),一個中文字是兩個位元組。B取2,就能以中文字為比對單位。

三、中文是以字組詞。B加大,就能以詞、詞組為比對單位。

【註:此演算法的比對單位是B個字元,然而挪動單位仍是一個字元。因此二與三是空談。】

實作時,B個字元用hash function合而為一數。

演算法

一、只看每個P的左端m個字元,暫時忽略右端其餘字元。
  P長度最短者,取作m。
二、預先建立SHIFT table、HASH table、PREFIX table。
三、實施Boyer-Moore 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個字元。