string searching

運用後綴處理字串搜尋問題

兩步驟:枚舉T的所有後綴、搜尋開頭恰為P的後綴。

T: mississippi
P: issi

all suffixes of T:
   mississippi, ississippi, ssissippi, ...
   
string searching:
   0             1            2
   mississippi   ississippi   ssissippi   ...
   issi          issi         issi

儲存大量後綴的資料結構

以大量字串的資料結構,儲存並排序T的全部後綴,就更容易搜尋後綴。例如array、binary tree、trie、automaton。

後綴們有許多重複字元。精簡重複字元、減少空間大小、改善排序速度。

                  build    string searching
----------------- -------- ---------------
suffix array      O(T+A)   O(PlogT)
 + lcp array      O(T+A)   O(P+logT)
suffix trie       O(T²)    O(P)
suffix tree       O(T)     O(P)
suffix automata   O(TA)    O(P)

演算法選擇

適用情況:P為定值,T為變動值。
單一字串搜尋:Morris–Pratt algorithm、Boyer–Moore algorithm。
多重字串搜尋:Aho–Corasick algorithm。

適用情況:T為定值,P為變動值。
單一、多重字串搜尋:suffix array、suffix trie、suffix tree。

大量suffix資料結構: suffix array

suffix array

「後綴陣列」。一個字串的全部後綴,統統放入陣列。排序所有後綴,以利之後搜尋。

一個索引值表示一個後綴,空間複雜度O(T)。

string:
   mississippi

all suffixes:
   mississippi, ississippi, ssissippi, sissippi, issippi,
   ssippi, sippi, ippi, ppi, pi, i

suffix array:
   +---+------+---------+------------+-------------+-     -+
   | i | ippi | issippi | ississippi | mississippi |  ...  |
   +---+------+---------+------------+-------------+-     -+

suffix array:
   +---------+--------+--------+--------+-     -+
   | [10,10] | [7,10] | [4,10] | [1,10] |  ...  |
   +---------+--------+--------+--------+-     -+

suffix array:
   +----+---+---+---+---+---+---+---+---+---+---+
   | 10 | 7 | 4 | 1 | 0 | 9 | 8 | 6 | 3 | 5 | 2 |
   +----+---+---+---+---+---+---+---+---+---+---+

suffix array:
     | sa | suffix
  ---+----+------------
   0 | 10 | i
   1 |  7 | ippi
   2 |  4 | issippi
   3 |  1 | ississippi
   4 |  0 | mississippi
   5 |  9 | pi
   6 |  8 | ppi
   7 |  6 | sippi
   8 |  3 | sissippi
   9 |  5 | ssippi
  10 |  2 | ssissippi

suffix array:
   +------------------------+
   | 10 7 4 1 0 9 8 6 3 5 2 |
   +------------------------+
      i i i i m p p s s s s
        p s s i i p i i s s
        p s s s   i p s i i 
        i i i s     p s p s
          p s i     i i p s
          p s s       p i i
          i i s       p   p
            p i       i   p
            p p           i
            i p
              i

演算法(quicksort)

以快速排序法排序所有後綴。每個後綴的長度都不同,名次必不同,毋須特地使用stable sort。

兩個後綴比大小需時O(T),兩兩比較次數是O(TlogT),時間複雜度O(T²logT)。

演算法(radix sort)

字元種類有限、範圍有限,適用radix sort。時間複雜度O((T+A) ⋅ T)。A是字元種類數目。

演算法(prefix-doubling algorithm)

radix sort和prefix-doubling algorithm有些相似。

radix sort:各回合拿倒數第一個、倒數第二個、倒數第三個、……字元實施排序,總共T回合。每回合採用counting sort。

prefix-doubling algorithm:各回合拿前一個、前二個、前四個、前八個、……字元實施排序,總共logT回合。每回合可以採用quicksort或counting sort。

運用上回合的排序結果,先比前半段、再比後半段,不必逐個字元比較。用一個字元的排序結果,拼成兩個字元的排序結果;用兩個字元的排序結果,拼成四個字元的排序結果;以此類推。

每回合採用quicksort,時間複雜度O(logT ⋅ TlogT) = O(Tlog²T)。

每回合採用counting sort,時間複雜度降為O(logT ⋅ (T+A))。A是字元種類數目。

演算法(DC3)

全部後綴分成三類,分別處理。

一、全部後綴根據「所在位置」分成兩堆:
  所在位置除以三,餘零者為S0,餘一或二者為S12。
二、用radix sort排序S12,僅排序前三個字元。
  平手時,才繼續排序下三個字元。
  途中可以隨時利用已經排序好的部份。
三、利用排序完畢的S12,來排序S0。
四、合併S12與S0。

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

演算法(SA-IS)

全部後綴分成三類,分別處理。

一、全部後綴以「所在位置」與「字典順序」分成兩堆:
 甲、右方後綴字典順序更小為S、右方後綴字典順序更大為L。
 乙、連續的S的左邊第一個為LMS。
二、用radix sort排序LMS。
  途中可以隨時利用已經排序好的部份。
三、利用排序完畢的LMS,來排序完整的後綴陣列。

時間複雜度O(T+A)。實務上最快的演算法。

字串搜尋

已排序陣列,使用binary search。時間複雜度O(PlogT)。

大量字串搜尋

將所有T連成一串,以'\0'隔開,然後建立後綴陣列。每個P分別做二元搜尋。

想讓排序結果正確,隔開字元的字典順序必須小於T的每個字元。大家習慣用'\0'。

UVa 10526 10580

大量suffix資料結構: longest common prefix array

longest common prefix

一堆字串的「最長共同前綴」只有一個,有可能是空字串。

演算法很簡單:字串們一齊從頭開始比對字元。

s1: aabbccc
s2: aabbbccc
s3: aabaccc

s1 s2 s3 的 LCP 就是 aab。

兩個後綴的LCP

string:
   abbbababba

suffixes:
   s0: abbbababba
   s1: bbbababba
   s2: bbababba
       ......
   s8: ba
   s9: a

LCP(s1, s2) = bb
LCP(s0, s9) = a

兩個後綴的LCP,
就是排序全部後綴之後,兩個後綴之間的所有後綴的LCP。

     0 1 2 3 4 5 6 7 8 9
   +---------------------+
sa | 9 4 6 0 8 3 5 7 2 1 |
   +---------------------+
     a a a a b b b b b b
       b b b a a a b b b
       a b b   b b a a b
       b a b   a b   b a
       b   a   b a   a b
       a   b   b     b a
           a   a     b b
           b         a b
           b           a
           a

LCP(7th, 9th) = LCP(7th, 8th, 9th) = LCP(s7, s2, s1) = bb
LCP(4th, 8th) = LCP(4th, ..., 8th) = LCP(s8, s3, s5, s7, s2) = b

開頭相近的後綴,排在一起;開頭不相近的後綴,被開頭相近的後綴隔開。

排序全部後綴之後,兩個後綴之間的所有後綴的LCP,
就是兩兩相鄰後綴的LCP們的LCP。

LCP(7th, 9th) = LCP( LCP(7th, 8th), LCP(8th, 9th) ) = bb
LCP(4th, 8th) = LCP( LCP(4th, 5th), ..., LCP(7th, 8th) ) = b

以相鄰後綴的LCP,推導出任意後綴的LCP。

兩兩相鄰後綴的LCP,表達成數值:
longest common prefix array

直接記錄LCP字串,浪費大量記憶體空間,因而改為記錄LCP長度。輔以原字串、後綴陣列,便可得到LCP字串。

排序全部後綴之後,每一個後綴與前一個後綴的LCP長度,儲存於陣列,得到LCP array。

       0 1 2 3 4 5 6 7 8 9
     +---------------------+
  sa | 9 4 6 0 8 3 5 7 2 1 |
     +---------------------+
lcpa | 0 1 2 3 0 2 3 1 3 2 |
     +---------------------+
       a a a a b b b b b b
         b b b a a a b b b
         a b b   b b a a b
         b a b   a b   b a
         b   a   b a   a b
         a   b   b     b a
             a   a     b b
             b         a b
             b           a
             a

LCP_length(7th, 9th) = min(lcpa[7+1], ..., lcpa[9]) = 2
LCP_length(4th, 8th) = min(lcpa[4+1], ..., lcpa[8]) = 1

兩個後綴的LCP,藉由LCP array,變成了查詢區間最小值。請參考「偽線段樹」。

UVa 12338

演算法

依序計算兩兩相鄰後綴的LCP,依序填寫LCP array。時間複雜度O(T²)。

演算法

運用小技巧,建立LCP array僅需時O(T)。

一個字串的後綴,開頭去掉一個字元,仍是後綴。

兩個相鄰後綴,開頭各去掉一個字元,得到兩個新後綴。雖然不見得相鄰,但是大小關係依然相同。LCP則少了一個開頭字元。

           2 3       7   9
      ---------------------
           a a       b   b
           b b       b   b
           b b       a   b
           a b           a
             a           b
             b           a
             a           b
             b           b
             b           a
             a

abba < abbbababba            => bba < bbbababba
LCP(abba, abbbababba)        =  a + LCP(bba, bbbababba)
LCP_length(abba, abbbababba) =  1 + LCP_length(bba, bbbababba)

兩個新後綴的LCP長度,小於等於第二個新後綴、與其前方相鄰後綴的LCP長度。

LCP_length(2th, 3th) - 1 = LCP_length(7th, 9th) ≤ LCP_length(7th, 8th)
LCP_length(3-1th, 3th) - 1 ≤ LCP_length(8-1th, 8th)

從最長的後綴(原字串)開始,逐次去掉開頭字元,跳著填寫LCP array。

3th: abbbababba     9th: bbbababba      8th: bbababba
LCP(3-1th, 3th) --> LCP(9-1th, 9th) --> LCP(8-1th, 8th) --> ...

每次LCP減少一個開頭字元之後,新後綴與其相鄰後綴的LCP只會一樣長、更長。不必每次從頭開始比對字元。

一、依序掃描原字串的每個後綴。每次都會少掉一個開頭字元:
 甲、求得該後綴在後綴陣列裡的位置。
 乙、再找出上一個相鄰後綴。
 丙、逐一比對字元,求出LCP長度,儲存於LCP array。
 丁、下次就可以從LCP長度減一開始比對字元。小心不能減至負值。

字串搜尋

一、T的suffix array。O(T+A)。
二、T的LCP array。O(T)。
三、LCP array的偽線段樹。建立O(T)、搜尋O(logT)。
  用來快速求得LCP(i,j)。
四、二元搜尋。

令二元搜尋的三個指標是L M R。二元搜尋的過程是:逐字比對P與M,判斷P < M或者P > M,讓M' = L或者M' = R。時間複雜度O(PlogT)。

M與L R經常有共同前綴。P與M比大小,可以從LCP(L,R)開始比對,節省一點時間。然而時間複雜度仍是O(PlogT)。

P與L R經常有共同前綴。P與M比大小之前,可以預先計算LCP(M,L)、LCP(M,R),如果小於LCP(P,L)、LCP(P,R),就毋需比對。看誰長得像,直接得到M'。時間複雜度降為O(P+logT)。

預先建立LCP array與「偽線段樹」,從LCP array查詢區間最小值,得以迅速求得LCP。

一、P與M的共同前綴,往後不必再比對,O(P)。二、查詢區間最小值,區間逐次減半,O(logT + logT/2 + logT/4 + ... ) = O(logT)。三、總時間複雜度O(P+logT)。

【待補程式碼】

ICPC 4657

大量suffix資料結構: suffix trie

普通的建立方法

把一個字串的所有後綴,統統塞入一棵trie。

時間複雜度O(T²),空間複雜度O(T²A)。

運用suffix link的建立方法

先前介紹Aho–Corasick algorithm曾經提過suffix link:每個節點各自牽一條線到次長後綴所在節點。

運用suffix link,就能online建立suffix trie,而且不必重覆遍歷已經建立的節點。每加入一個字元,就從最深的節點開始走訪suffix link、建立新節點。

加入所有字元之後,記得標出每個後綴所在節點。

時間複雜度仍是O(T²),空間複雜度仍是O(T²A)。

字串搜尋

從T找到一個P:從樹根開始走訪suffix trie,看看有沒有P。時間複雜度O(P)。

從T找到全部P:建立suffix trie的時候,每個節點都必須額外記錄有哪些後綴經過。

大量suffix資料結構: suffix tree

suffix tree

「後綴樹」是suffix trie的改良版本:

一、字串結尾添加一個從未出現的字元(例如'\0'),再來建立suffix trie。如此一來,後綴結尾總是出現在樹葉,不會出現在內部節點,就不必特別記錄後綴所在節點。

二、去除沒有分叉的節點,一串樹枝合併成一根樹枝。

三、樹枝上的子字串,改為兩個索引值、或者兩個指標。

後綴樹共T+1個樹葉。字元皆相同,節點最多,共2T+1個節點;字元皆不同,節點最少,共T+2個節點。空間複雜度O(TA)。

演算法(Ukkonen's algorithm)

運用suffix link,是online演算法,時間複雜度O(T+A)。

樹葉終身是樹葉。每次加入一個字元、要建立新節點時,不必回到最深的節點,可以從當前的節點繼續。

演算法(Farach's algorithm)

時間複雜度O(T)。時間複雜度不含字元數量,但是不實用,參考看看就好。

字串搜尋

從T找到一個P:從樹根開始走訪後綴樹,看看有沒有P。時間複雜度O(P)。

從T找到全部P:從後綴樹找到P之後,遍歷子樹。P在T當中的出現次數,就是子樹的葉子數量。P在T當中的出現位置,就是 [ T長度 - 葉子深度 , T長度 - 葉子深度 + 當前節點深度 ]。

後綴樹是二元樹,內部節點數量等於葉子數量減一。因此子樹最多2K-1個節點,K是出現次數。時間複雜度O(P+K)。

大量suffix資料結構: suffix tray

suffix tray

suffix tree和suffix array一併使用。

大量suffix資料結構: suffix automaton

suffix automaton

「後綴自動機」。把後綴通通塞入一個自動機。