Question

建立索引表处理字串匹配问题

预先挑出重要单字，预先计算位置。将来进行字串比对，可以直接查表。

字元索引表

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

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 倍、执行速度增加 128 倍了！

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)。

String Matching: FM-Index

http://pizzachili.di.unipi.it/indexes.html

http://alexbowe.com/fm-index/

大杂烩。

String Matching: LZ-Index

http://pizzachili.di.unipi.it/indexes/LZ-index/

仿照 Ziv-Lempel Compression，将字串切散成许多段。从头扫描，遇到从未出现的前缀，就切断。将每段字串存入 Trie，将每段字串头尾颠倒存入另一棵 Trie，以便实施字串匹配。

String Matching: Karp-Rabin Algorithm

运用数列处理字串匹配问题

字元看作数值，字串看作数列。运用数列的知识，设计演算法。

以区间和筛选

计算 P 的总和。穷举 T 的区间和，区间长度是 P 的长度。

当区间和相等，才有机会匹配成功，才需要比对字元。

宛如初试与複试，先简单快速筛选，再严格缓慢校对，省时。