string searching: inverted index

建立索引表處理字串搜尋問題

預先挑出重要單字,預先計算位置。將來進行字串比對,可以直接查表。

字元索引表

找到每個字元的所在位置。

string:
012345678910
mississippi

inverted index:
i : 1 4 7 10
m : 0
p : 8 9 
s : 2 3 5 6

建立過程正是counting sort的第一個步驟。時間複雜度O(T+A)。

字串搜尋

先查閱索引表,再實施窮舉法,時間複雜度O(TP)。

時間複雜度乍看之下沒有任何改進,但是實際上是大躍進!尤其是當各個字元的出現次數很平均、差不多相等,那麼窮舉次數就降低成1/128倍、執行時間降低成1/128倍了!

單字索引表

實務上是建立單字索引表。以大量字串資料結構儲存單字。

string/pattern變成了document/word。

documents:
d[0] : "it is what it is"
d[1] : "what is it"
d[2] : "it is a banana"

inverted index:
"a"      : (2,2)
"banana" : (2,3)
"is"     : (0,1) (0,4) (1,1) (2,1)
"it"     : (0,0) (0,3) (1,2) (2,0)
"what"   : (0,3) (1,0)

UVa 1597 ICPC 3134

move-to-front transform

move-to-front transform

一、A種字元依序排隊。(將A種字元存入具有排名功能的資料結構)
二、每當讀入一個字元,就印出字元的名次。(把名次數值轉型成ASCII字元)
三、該字元插隊到最前面。

排名資料結構採用array,每次插隊需時O(A),總時間複雜度O(NA)。

排名資料結構採用binary search tree,每次插隊需時O(logA),總時間複雜度O(NlogA)。

出現地點比較密集(不是指出現次數比較多),名次數字比較小。是個奇妙的轉換,講不出個所以然。反覆實施MFT,不知道最後會怎麼樣。

inverse move-to-front transform

一、A種字元依序排隊。(A種字元存入具有排名功能的資料結構)
二、每當讀入一個名次,就印出字元。
三、該字元插隊到最前面。

時間複雜度同前。

Burrows–Wheeler transform

Burrows–Wheeler transform

輸入是一個字串,輸出是一個字串、附帶一個索引值。

輸入字串長度為N。輸入字串循環位移,得到N個字串。N個字串實施排序,依序取得最後一個字元(也有人取第二個字元),作為輸出字串。並且記下輸入字串的排名。

            BWT
"suffixes" ----> "xuffessi"   ("suffixes" is rank 5)
                  suffixes        essuffix 0
                  uffixess        ffixessu 1
                  ffixessu        fixessuf 2
          rotate  fixessuf  sort  ixessuff 3
suffixes -------> ixessuff -----> ssuffixe 4
                  xessuffi        suffixes 5*
                  essuffix        uffixess 6
                  ssuffixe        xessuffi 7
                                         ^

後綴有著極快的排序演算法,因此改成後綴。

輸入字串重複一遍,長度變為2N。排序前N個後綴,等同於排序原本N個循環字串!唯一例外:輸入字串只有一種字元、所有字元通通相同;然而這種情況下,BWT的結果顯而易見就是原本字串,大可不必實施排序。

"suffixes"          | "suffixessuffixes"
sort cyclic strings | sort first N suffixes
--------------------| ---------------------
essuffix            | essuffixes      
ffixessu            | ffixessuffixes  
fixessuf            | fixessuffixes   
ixessuff            | ixessuffixes    
ssuffixe            | ssuffixes       
suffixes            | suffixessuffixes
uffixess            | uffixessuffixes 
xessuffi            | xessuffixes     
^^^^^^^^              ^^^^^^^^
輸入字串有兩種以上字元,就能用前N個字元決定排序結果。

運用suffix array達成BWT,時間複雜度O(N+A)。

BWT令相同字元容易黏在一起,是主要特色。知名的應用是「run-length compression」。

想要相同字元黏在一起,為什麼不直接排序輸入字串的所有字元就好了?原因很簡單,因為沒辦法還原成原本字串。

inverse Burrows–Wheeler transform

輸出字串、輸入字串的名次,還原成輸入字串。

            IBWT
"suffixes" <----- "xuffessi"   (original string is rank 5)

IBWT的本質,是將N個循環字串,從排序之後的順序,還原成排序之前的順序。我們觀察排序之後的順序。

一、最後一個字元重新排序,就是第一個字元。想一想為什麼?

 0   .......x          e......x
 1   .......u  fill    f......u
 2   .......f  1st     f......f
 3   .......f  column  i......f
 4   .......e -------> s......e
*5   .......s          s......s
 6   .......s          u......s
 7   .......i          x......i

二、第一個字元,循環左移,變成最後一個字元。依此找到對應字串。依此找到原字串每個字元的下一個字元。

二之一、僅出現一次的字元:輕鬆找到對應字串。

  e......x
  f......u
  f......f   
V i......f      get i->x
  s......e
  s......s
  u......s
  x......i V

二之二、出現兩次以上的字元:觀察第一個字元。第一個字元移除之後,字串先後次序不變。第一個字元循環位移之後,字串先後次序不變。依此找到對應字串。

  e......x
  f......u
  f......f         1      2
  i......f     get s->s , s->u
1 s......e
2 s......s 1
  u......s 2
  x......i

運用inverted index達成IBWT,時間複雜度O(N+A)。

UVa 632 741

dynamic Burrows–Wheeler transform

【待補文字】

string searching: FM-index

大雜燴。

string searching: LZ-index

仿照Ziv–Lempel compression,將字串切散成許多段。從頭掃描,遇到從未出現的前綴,就切斷。將每段字串存入trie,將每段字串頭尾顛倒存入另一棵trie,以便實施字串搜尋。

string searching: Karp–Rabin algorithm

運用數列處理字串搜尋問題

字元看作數值,字串看作數列。運用數列的知識,設計演算法。

以區間和篩選

計算P的總和。窮舉T的區間和,區間長度是P的長度。

當區間和相等,才有機會搜尋成功,才需要比對字元。

宛如初試與複試,先簡單快速篩選,再嚴格緩慢校對,省時。

以多項式篩選

區間和容易相等,容易誤判。篩選機制尚有改進空間。

數列變成多項式。為了避免除法運算,次方順序設為由大到小。

仿效x進位的觀念,令x的值大於等於字元種類,使得不同字串必是不同總和。

變成多項式,導致新問題:總和太大,導致溢位。解法是減少底數x、設定模數m。這使得不同字串可能是相同總和。

儘管仍舊不完美,但是篩選效果更好了。當多項式相等,字串差異也更大了,比對字元得以提早結束。最差時間複雜度O(TP),平均時間複雜度O(T+P)。

位元運算,速度更快。使用二進位,底數x = 2,模數unsigned int = 2³²。

以雜湊函數篩選

多項式,宛如字串雜湊函數djb2、sdbm。

string searching: SSEF algorithm

演算法

融合了雜湊函數、索引表兩種手法。

雜湊函數:給定16個字元,得到一個二進位數字(16個位元)。每個字元,視作二進位數字,取第K高位元,併成一個二進位數字,當作雜湊值。K是自訂數值。

索引表:給定16個字元的雜湊值,得到16個字元在P之中的所有位置(位置是16的倍數)。P每16個字元為一組,各組計算雜湊值,存入表格。

字串搜尋:窮舉T的各種位置。針對一種位置,每16個字元,求得雜湊值,查詢表格,檢查位置是否相符,此為初試。如果相符,才比對字元,此為複試。

平行計算:利用Intel中央處理器的擴充指令集SSE。

演算法名稱由來:利用SSE進行filtering(初步篩選)。

實務上最快的演算法(2010年的測量結果)。

《Filter Based Fast Matching of Long Patterns by Using SIMD Instructions》

《The Exact String Matching Problem: a Comprehensive Experimental Evaluation》