摘要訊息 : 人類信息傳遞的基石.

0. 前言

可以說, 字串在人類世界中佔有非常重要的位置. 特別是當今的時代, 我們肉眼看到的能夠形成文字或者標記的東西, 都可以看作是字串. 從本質上來說, 字串就是由若干個字元組成的向量 (《【資料結構】向量 (順序表)》). 很顯然, C++ 標準樣板程式庫中的字串 std::string 和 std::vector<char> 的區別並不是很大 (不考慮具體的實作, 只考慮基礎的結構). 但是由於字串的特殊性, 所以字串也有很多屬於自己的標準和演算法.

1. 字元

實用定義 1. 與符號相關的一個資訊單位稱為字元 (character), 包括但不限於數字, 英文字母, 標點符號等.

字元的實用定義告訴我們, 只要有標記作用的符號, 都可以被稱為字元. 也就是說, 我們在任何書上看到的一個文字, 不論它最終屬於什麼語言, 它都是一個字元. 所以字元不僅僅只是英文. 字元也必定有著一些顯著的區分, 例如大小. 從感覺上來說, 幾乎所有中文字元都比英文字元或者希臘文字元要大一些; 而正體中文又比簡化字要更正統和複雜一些.

由於字元本身可以變化多樣, 例如 1 可以變成 1⃣️ 也可以變成 ①, A 有 ÀÁÂÄÆÃÅĀ 這麼多變種, 所以字元很難有精確的數學定義. 只要一個符號和資訊相關, 可以在特定背景下傳遞一定的信息, 那麼我們就可以視這個符號是一個字元.

1.1 字元編碼系統

定義 1. 設 C = \left \{ c \right \} 是字元集合, N = \left \{ n \right \} 是非零整數集合. 若存在一個影射 M, 滿足

1. M(n) = c;
2. M 的逆影射 M^{-1} 滿足 M^{-1}(c) = n;
3. 對於任意兩個 C 中的不同字元 c_{1} 和 c_{2}, 若 N 中總存在兩個不同的值 n_{1} 和 n_{2}, 有 \displaystyle {M(c_{1}) = n_{1} \neq n_{2} = M(C_{2})},

那麼我們稱 M 為字元編碼系統 (character encoding system), n 為碼位值 (code point value).

簡單地來說, 字元編碼系統是將某個系統中的所有字元指派對應的數字作為其特徵. 例如我們可以自己設計一套字元編碼系統, 這個系統的字元有 C = \left \{ A, B, C \right \}, 其對應的碼位值集合為 \left \{ 100, 101, 102 \right \}. 那麼在這套字元編碼系統下, 有 \displaystyle {M(A) = 100, M(B) = 101 \text { 且 } M(C) = 102}. 通俗來說, 就是用數字 100 來代表字元 A.

那麼現在有一個問題 : 為什麼要設計字元編碼系統, 為什麼要有字元編碼系統? 從直覺上來說, 每一個字元本身就是一個獨立的值, 都是一個不同的符號, 再用不同的數字為其標記是否有點多此一舉? 實際上在電腦中, 儲存信息的資訊單位是 0 和 1. 也就是說, 電腦硬體中並不能直接儲存那些字元, 特別是比較新的一些表情符號. 於是, 我們通過字元編碼系統, 讓電腦通過儲存字元對應的碼位值, 然後再通過字元編碼系統將碼位值轉換為實際字元. 這樣, 就不需要改變電腦的硬體結構.

現在我們可以推斷, 電腦記憶體和硬碟中儲存的實際上並不是真實的數據, 而是用 0 和 1 去表示的數據. 假如記憶體中某個區域儲存了 01000001, 在 ASCII 這個特定的字元編碼系統下, 對應了英文字母 A.

常用的字元編碼系統有 ASCII, UTF-8, UTF-16 和 UTF-32. 常用的正體中文字元編碼系統有 BIG-5 和 HKSCS, 常用的簡體中文字元編碼系統有 GBK 和 GB-18030. 在這些字元編碼系統中, 每一個字元都會對應一個獨立的碼位值, 且相互可能會存在一定的相容性.

1.1.1 ASCII 與 Unicode

我們知道, 電腦首先來源於使用英文的國家——美國. 因此, 最開始的電腦是被用來處理英文信息的. 而英文信息中所使用的字元非常少, 這些字元幾乎都被列在了鍵盤上. 慢慢地, ASCII 便成為了最常用的字元編碼系統, 它包含了 128 個字元, 正好是 C/C++ 中型別 char 的非負部分 (0-127) :

但是後來, 隨著電腦普及到其它非英文國家與地區, ASCII 字元編碼系統的缺點就變得非常明顯 : 它包括的字元太少了, 也沒有考慮擴展到其它符號的問題. 於是 Unicode (包括其字元編碼系統 UTF-8, UTF-16 和 UTF-32) 和 BIG-5 等都對 ASCII 進行了擴充, 加入了本地化的字元. 例如 BIG-5 中加入了正體中文, Unicode 中甚至還加入了表情符號. 到目前為止, Unicode 幾乎整合了世界上現存的所有符號, 大概有十四萬個字元, 每一個字元都有獨立的碼位值與之對應. 當我們使用 UTF-32 字元編碼系統的時候, 就是在使用 Unicode. Unicode 在前 128 個字元上保持了 ASCII 一致, 也就是向 ASCII 相容. 在 C++ 中, ASCII 通常使用的是 char 來儲存, UTF-32 通常使用 char32_t 來儲存 (在 C++ 98/03 中, UTF-32 可能會採用 wchar_t 或者 unsigned int 來替代).

通過 ASCII 表中的二進位欄位, 我們可以發現常用的英文字元至多使用了七位元. 但電腦一般按照位元組來存取, 例如一次取一個位元組, 也就是八位元. 因此, ASCII 通常使用一個位元組來儲存, 這也就是 C/C++ 中 sizeof(char) 的結果通常是 1 的原因. Unicode 中的字元很多, 整個表也非常大, 而且還存在繼續擴展的可能. 因此僅僅使用八位元來儲存是遠遠不夠的, 至少需要 32 位元, 即 4 位元組. 同樣對應地, C++ 中 sizeof(char32_t) 的結果通常是 4.

1.1.2 UTF-8

如果一個檔案是純英文的, 若採用 ASCII 進行編碼, 最終檔案的大小通常是 8 \times n 位元. 其中, n 是檔案中字元的數量, 且我們此處採用一個字元使用八位元進行儲存. 但是如果採用 UTF-32 進行編碼, 其大小通過就要擴大四倍, 還不包括一些用於標記的字元. 但是不論用 ASCII 進行編碼, 還是用 UTF-32 進行編碼, 當我們打開這個檔案的時候, 我們看到的實際內容並不會發生改變. 另一方面, Unicode 雖然容納了幾乎所有符號, 但是我們日常並不會把這十四萬個符號都用一遍, 有時候僅僅需要其中的幾千個甚至幾百個字元. 例如字元 x, 其二進位為 1111000. 如果採用 ASCII 進行編碼, 我們只需要在最前補齊一個 0 從而使得其對齊到八位元即可. 但是如果要讓二進位對齊到 32 位元, 那麼就需要額外補足 25 個 0. 在這種情況下, 使用 UTF-32 編碼, 會浪費掉很多空間. 為此, 我們希望有一個可以壓縮的方案, 於是便有了 UTF-8.

UTF-8 仍然採用 8 位元為基礎的形式來儲存字元, 但是它可以表示任意 Unicode 字元. 對於 ASCII 中存在的字元, UTF-8 和它們是完全相容的, 碼位值也是完全一樣的. 換句話說, [0, 128) 中的任意數值, 在 UTF-8 和 ASCII 這兩個字元編碼系統下都會影射到相同的字元. 對於那些 ASCII 中不存在的字元, UTF-8 採用了針對 Unicode 字元的可變長度編碼. 在可變長度編碼下, 一個採用 UTF-8 位字元編碼系統的字元來說, 它最少使用 8 位元儲存, 至多使用 32 位元儲存. 不難想像, 對於常用的字元, UTF-8 會將其對應的編碼壓縮得儘可能短. 例如英文字元這樣的常用字元, UTF-8 和 ASCII 一樣只採用 8 位元來儲存. 這樣, 採用 UTF-8 編碼的英文檔案和採用 ASCII 編碼的英文檔案大小是一樣的, 並且兩者可以相容.

設字元 c 在 UTF-32 字元編碼系統中的碼位值為 n, 那麼對應的 UTF-8 的碼位值為 \displaystyle {\mathop {\mathrm {u8}}(n) = \begin {cases} 0b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}b_{7} & {0 \leq n < 2^{7}} \\\\ 110b_{1}b_{2}b_{3}b_{4}b_{5} \quad 10b_{6}b_{7}b_{8}b_{9}b_{10}b_{11} & {2^{7} \leq n < 2^{11}} \\\\ 1110b_{1}b_{2}b_{3}b_{4} \quad 10b_{5}b_{6}b_{7}b_{8}b_{9}b_{10} \quad 10b_{11}b_{12}b_{13}b_{14}b_{15}b_{16} & {2^{11} \leq n < 2^{16}} \\\\ \begin {aligned} &11110b_{1}b_{2}b_{3} \quad \quad \quad \quad 10b_{4}b_{5}b_{6}b_{7}b_{8}b_{9} \\ &10b_{10}b_{11}b_{12}b_{13}b_{14}b_{15} \quad 10b_{16}b_{17}b_{18}b_{19}b_{20}b_{21} \end {aligned} & {2^{16} \leq n < 2^{21}}. \end {cases}} 把 UTF-8 二進位值中的 b_{i} 按照順序拼接起來, 便是 UTF-32 下對應的碼位值. 到目前為止, Unicode 字元集合中僅有十四萬個字元, 故 32 位元完全足夠表示所有字元.

在處理 UTF-8 檔案的時候, 一次只讀入 8 位元, 那麼那些文本編輯器如何處理非 ASCII 字元, 即可變的那一部分呢? 當讀入的一位元組之後, 編輯器首先會存取首個位元, 如果它是 0, 那麼說明這個字元就是 ASCII 字元, 直接把剩下的 7 位元轉換為對應的字元即可; 如果它是 1 開頭, 那麼就說明現在已經進入了可變長度處理部分. 然後接下來有幾個 1 才遇到 0, 就說明了下面有幾個位元組是需要一次性讀入的. 當然還有另一種方法, 當開頭的位元值是 1, 那麼不斷往下讀, 只要是 10 開頭的都必定是該字元的一部分.

例題 1. 解析 UTF-8 編碼的值 \displaystyle {\begin {aligned} &01110110 \quad 11110000 \quad 10100000 \quad 10001100 \\ &10001010 \quad 11100010 \quad 10101010 \quad 10111000. \end {aligned}}

解 :

讀入 01110110, 這個二進位值是 0 開頭, 所以它是 ASCII 字元, 它對應了英文字母 v.

讀入 11110000, 開頭是 1, 然後是 1110, 就說明接下來還跟著三個位元組的變長部分, 所以讀入 10100000 \quad 10001100 \quad 10001010. 將 UTF-8 表示值的那部分二進位位元拼接起來, 便可以得到 100000001100001010 : \displaystyle {00000000 \quad 00000010 \quad 00000011 \quad 00001010}, 它對應的 UTF-32 字元為 𠌊.

讀入 11100010, 開頭是 1, 然後是 110, 所以還要讀入跟著的兩個位元組的變長部分, 所以讀入 10101010 \quad 10111000. 去掉 UTF-8 表示值的那部分, 然後把剩下的二進位位元拼接起來, 便可以得到 101010101010111000, 它對應的 UTF-32 字元為 ⪸.

所以最終的字串為 v𠌊⪸.

\blacksquare

1.1.3 UTF-16

UTF-16 是以 2 位元組為單位, 一次至少使用 2 位元組至多使用 4 位元組的可變長度編碼系統. 任意字元如果採用 UTF-16 進行編碼, 那麼這個字元至少佔了 2 位元組, 即 16 位元. 若某個檔案採用了 UTF-16 編碼, 那麼一次必須至少讀入 16 位元, 這不同於 UTF-8 或者 ASCII 一次只需要讀入 8 位元. 這也就導致了 UTF-16 和 UTF-8/ASCII 是不相容的. 另外, 若文字編輯檔案是純英文的, 那麼採用 UTF-16 編碼之後, 其大小至少是 ASCII 編碼的兩倍.

設字元 c 在 UTF-32 字元編碼系統中的碼位值為 n, 那麼對應的 UTF-8 的碼位值為 \displaystyle {\mathop {\mathrm {u16}}(n) = \begin {cases} b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}b_{7}b_{8} \quad b_{9}b_{10}b_{11}b_{12}b_{13}b_{14}b_{15}b_{16} & {0 \leq n < 2^{16}} \\\\ \begin {aligned} &110110b_{1}b_{2} \quad\quad b_{3}b_{4}b_{5}b_{6}b_{7}b_{8}b_{9}b_{10} \\ &110111b_{11}b_{12} \quad b_{13}b_{14}b_{15}b_{16}b_{17}b_{18}b_{19}b_{20} \end {aligned} & {2^{16} \leq n < 2^{29}}. \end {cases}} 把 UTF-16 二進位值中的 b_{i} 按照順序拼接起來, 便是 UTF-32 下對應的碼位值.

在處理 UTF-16 檔案的時候, 一次固定讀取 2 位元組, 即 16 位元. 當讀入的前 8 位元以 110110 開頭的時候, 說明後面兩個位元組也是字元的一部分, 這個時候會再讀取兩個位元組. 對於純英文檔案來說, 每次讀取的兩個位元組中, 前面那 8 位元的值一定是 0, 即 \displaystyle {00000000 \quad 0b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}b_{7}}. 所以使用 UTF-16 編碼的純英文檔案大小至少是 ASCII 的兩倍.

在 UTF-8 中, 不同的範圍有著不同的開頭, 而且是一一對應的, 所以不會存在歧異 (例如當 0 \leq n < 2^{7} 時, 必定是 0 開頭; 當看到 1110 開頭時, 必定有 n \in [2^{11}, 2^{24})). 但是在 UTF-16 中就會存在歧異. 假如現在得到的二進位串為 11011011 \quad 00001111, 那麼究竟如何判斷是否需要再讀入兩個位元組呢? 當 0 \leq n < 2^{16} 時, 是否存在二進位串的開頭為 110110 或者 110111 的情形呢? 答案是不存在, UTF-16 在設計的時候就考慮了這個問題. 為此, Unicode 將區間為 [1011000 \ 00000000, 11011111 \ 11111111] 中的任意碼位值置空, 即不存在任何字元會被影射到上面這個區間中. 那麼, 當我們讀到 11011b 開頭的二進位值時, n 必定落在 [2^{16}, 2^{29}) 中. 這樣便解決了 UTF-16 中可能造成歧義的問題.

1.1.4 位元組順序標記

有一部分裝置或者程式碼對位元組的存取順序時不同的. 例如 11000011 \quad 10101001, 一般的裝置會先讀入 11000011, 然後在讀入 10101001; 但是特殊的裝置或者特定的程式的讀取順序剛好是相反的, 先讀入 10101001, 然後再讀入 11000011. 換句話說, 一般的存取順序是從高位到低位 (左高右低), 而特殊的裝置或者特定的程式的存取順序是從低位到高位. 因此便有了位元組順序 (endian) 這樣的概念. 小端序 (little-endian) 是指低位儲存在空間中較高的位置, 高位儲存在空間中較低的位置; 大端序 (big-endian) 是指低位儲存在空間中較低的位置, 高位儲存在空間中較高的位置. 由於一般裝置的存取順序是從高位到低位的, 所以高位應該儲存在較高的位置, 低位應該儲存在較低的位置, 即一般裝置偏向於存取大端序. 大端序和我們平時閱讀的順序是相同的, 從左到右然後從上到下 (但是香港的書籍排列可能是從上到下, 從右到左, 這裡我們一般指的是互聯網上文章的閱讀順序, 就比如本文). 為此, 我們將 UTF-16 和 UTF-32 分成 UTF-16LE, UTF-16BE, UTF-32LE, UTF-32BE 四種, 分別標記了對應的儲存順序. UTF-16LE 會在檔案最開始增加一個標記 \text {FF FE} (11111111 \ 11111110), UTF-16BE 會在檔案最開始增加一個標記 \text {FE FF} (11111110 \ 11111111). 這樣會讓檔案額外增加兩個位元組的大小. 這也就是為什麼上面章節在比較 UTF-16 和 ASCII 檔案大小的時候, 使用的說法是至少兩倍, 而不是精確到兩倍的原因. 對應的, UTF-32LE 會在檔案最開始增加一個標記 \text {FF FE 00 00}, UTF-32BE 會在檔案最開始增加 \text {00 00 FE FF}.

需要指出的是, UTF-8 並不存在位元組順序問題. 若一個檔案明確地指出本檔案採用的是 UTF-8 字元編碼系統, 那麼可能會在檔案頭部增加 \text {EF BB BF} 這樣的標記. 這同樣也是 UTF-8 檔案可能會比 ASCII 檔案大的原因.

1.2 存取效能

很顯然, UTF-8 和 UTF-16 在存取檔案的時候, 都需要進行一定的計算. 那麼當我們打開使用 UTF-8 或者 UTF-16 編碼的檔案的時候, 其打開的速度不會比 ASCII 或者 UTF-32 檔案要快.

考慮到字元的數量和存取效能, 一般純英文檔案會直接採用 ASCII 進行編碼. 因為 ASCII 的相容性是所有字元編碼系統中最高的. 另外, 如果檔案不僅僅需要英文字元, 還需要用到 ASCII 中不存在的字元時, 我們可以採用 UTF-8, UTF-16 或者 UTF-32 來編碼. 最終用哪一種字元編碼系統取決於實際需求.

2. 字串

定義 2. 設向量 S = \left \{ c_{1}, c_{2}, ..., c_{n} \right \} 中任意 c_{i} 都是字元. 對於某一固定的影射 M, 任取 c_{i}, c_{j} \in S, 總有 \displaystyle {\begin {cases} M(c_{i}) = M(c_{j}) & {i = j} \\ M(c_{i}) \neq M(c_{j}) & {c_{i} \neq c_{j}} \end {cases}} 成立, 那麼我們稱 S 為字串 (string). 其中, S 可以簡寫為 c_{1}c_{2}...c_{n}, i, j = 1, 2, ..., n.

定義 3. 設 S = c_{1}c_{2}...c_{n} 是字串, 任取滿足 1 \leq i < j \leq n 的 i 和 j, 我們稱字串 c_{i}c_{i + 1}...c_{j - 1}c_{j} 為字串 S 的子串 (substring).

根據定義 2, 由於字串的本質是向量, 所以所有可以用於向量的演算法都可以用於字串. 又根據定義 3 可知, 任意字串也是其本身的子串.

2.1 字典樹

定義 4. 設樹 \mathcal {T} 中所有節點儲存的元素都是字元, 若將根節點到葉子節點路徑上所有節點的值從上到下按順序排列可以得到一個規則的單詞, 那麼我們稱 \mathcal {T} 為字典樹 (trie).

實際上 Figure 1-1 中有三棵字典樹, 組成了字典森林. 但對於一篇文章來說, 即使排除數字, 標點符號和特殊字元並且忽略大小寫問題, 這篇文章可能仍然會有二十幾棵字典樹. 我們可以參考 B 樹 (《【資料結構】B 樹》) 那樣的根節點, 對字典森林的各個根節點進行合併 :

2.1.1 搜尋

在字典樹中搜尋某個單詞非常高效, 因為英文中的常用單詞通常都不超過十個字母. 換言之, 字典樹的高度通常都不會太高. 若只需要搜尋某個字串是否在文章中出現, 不需要確定這個字串在文章中的具體位置, 那麼為文章構建字典樹來搜尋是較好的方案.

當要搜尋某個字串的時候, 我們需要逐個字母進行檢查. 對於字串 c_{1}c_{2}...c_{n} 來說, 首先搜尋根節點中是否有 c_{1} : 若有, 那麼在其子節點中搜尋 c_{2}; 若沒有, 那麼字典樹中不存在單詞 c_{1}c_{2}...c_{n}. 以此類推, 若存在一條從根節點到某個節點的路徑, 其組合的字串為 c_{1}c_{2}...c_{n}, 則字串在文章中存在. 值得注意的是, 當值為 c_{n} 的節點還有子節點也沒有關係, 因為我們只是搜尋字串 c_{1}c_{2}...c_{n} 是否存在.

若文章中最長的單詞有 n 個字母, 那麼在字典樹中搜尋的時間複雜度為 O(n). 另一方面, 搜尋不需要與節點數量或者單詞字串長度相關的額外輔助空間, 所以在字典樹中搜尋的空間複雜度為 \Theta(1).

對於 Figure 1 中的字典樹, 我們很容易確定 shells 這個單詞出現在文章中, 但是如果我們要確定 she 這個單詞是否出現在文章中, 則束手無策. 因此, 我們通常給每個節點增加一個標記, 以表示是否存在結束於當前節點的單詞.

在 Figure 2 中, 我們用 1 來表示從根節點到該節點路徑組成的單詞存在於文章中, 0 表示從根節點到目前節點組成的單詞在文章中沒有出現. 這樣, 當我們檢查到 e 的時候, 發現其標記為 1, 這說明了單詞 she 在文章中出現.

2.1.2 插入

向字典樹中插入單詞 c_{1}c_{2}...c_{n} 非常簡單, 只需要將 c_{1}, c_{2}, ..., c_{n} 按順序從上至下插入樹中即可, 前面的字母所代表的節點是後面字母所代表節點的父節點, 每個字母都在不同的層級. 若發現 c_{1}c_{2}...c_{i} 已經存在於字典樹中, 那麼只需要將 c_{i + 1}c_{i + 2}...c_{n} 插入到 c_{i} 的子節點中即可. 若 c_{1}c_{2}...c_{n} 都已經存在於樹中, 那麼無需插入新的節點. 最後只需要檢查一下字典樹的標記即可. 如果 c_{n} 的標記不是 1, 那麼就改變為 1. 除了 c_{n} 之外, 其它的標記值是不需要檢查, 也不需要更新的.

2.1.3 移除

若從字典樹中移除單詞 c_{1}c_{2}...c_{n}, 我們首先檢查 c_{n} 下面有沒有子節點 : 若有, 那麼僅需要更新 c_{n} 的標記為 0, 以說明單詞 c_{1}c_{2}...c_{n} 不出現在文章之中; 若沒有, 那麼需要向上不斷移除. 在移除節點的時候, 首先從 c_{n} 開始. 除了檢查當前節點的標記是否為 1 之外, 還要檢查當前節點的父節點是否存在其它子節點. 若滿足其中一個條件, 那麼僅需要移除當前節點即可; 否則, 就不斷上溯, 直到某個節點滿足其中一個條件或者全部節點都被移除才停止.

2.1.4 尋訪

字典樹的尋訪和普通樹的尋訪不太一樣. 按照樹的層次尋訪, 前序尋訪和後序尋訪 (參考《【資料結構】樹》第 2 節) 以及二元樹的中序尋訪 (參考《【資料結構】樹——二元樹》第 4 節) 方式對字典樹進行尋訪沒有任何意義, 因為我們希望最終尋訪的結果是若干個單詞, 而不是無意義的字元序列.

不難想像, 字典樹的尋訪是按路徑進行的, 即從不同的根節點到各個葉子節點的路徑, 這樣才能產生規則的單詞. 在尋訪的過程中, 我們逐漸將各節點中的字元拼接成字串. 假設目前位於某個中間節點 k, 我們會得到根節點到 k 這條路徑上所有單詞組成的子串 S. 接下來從節點 k 開始尋訪, 到達某個葉子節點之後就會得到另一個子串 S', 拼接這兩個子串 SS' 便是一個單詞. 例如在 Figure 1-2 的字典樹中, 我們已經尋訪了 s 和 h, 得到子串 sh. 接下來我們只需要將 h 子節點的尋訪結果 ells 加到 sh 尾部, 便得到了 shells. 如果字典樹像 Figure 2 那樣有標記, 那麼當我們遇到標記為 1 的節點時, 就把之前的尋訪子串加上這個節點中的字元得到一個字串, 然後進行保存或者輸出即可. 在 Figure 1-2 中, 我們只有遇到了葉子節點才對 shells 進行一次保存或者輸出, 在 Figure 2 中, 當我們遇到 e 的時候就需要對單詞 she 進行一次保存或者輸出. 顯然, 整個過程可以由遞迴來完成.

需要注意的是, Algorithm 1 中的尋訪演算法只是針對單棵字典樹的. 如果存在字典森林, 那麼就需要對應地將每一棵字典樹都使用一次路徑尋訪.

2.1.5 三向字典樹

為了更方便地進行搜尋, 字典樹的子節點可以像 B 樹那樣順序化. 我們要求比當前節點元素小的子節點必須排列在左側, 等於當前節點元素的子節點排列在中間, 比當前節點元素大的子節點排列在右側. 從而形成了三向字典樹. 在搜尋的時候, 我們可以通過比較字元在某一編碼系統下的前後順序來確定字元位於哪一個方向. 這樣就可以使得搜尋的效率增加.

2.2 子串搜尋

設有一長度為 n 的字串 S = s_{1}s_{2}...s_{n}, 驗證其中是否存在長度為 m 的另一字串 S' = s_{1}'s_{2}'...s_{m}', 然後要在 S 中找到 S' 的具體位置. 其中, 0 < m \leq n. 在較長字串中搜尋較短字串這樣的問題便是子串搜尋問題, 這個問題非常經典, 應用場景非常多. 例如在網頁中搜尋我們想要看的內容, 在基因庫中搜尋某個基因片段, 在文章中搜尋某個片段等.

2.2.1 Brute-force 演算法

要搜尋子串的位置, 最簡單的方法便是逐個字元進行配對. 例如在 ABACADABRAC 中搜尋 ABRA, 逐個字元配對就過程類似於

這種非常暴力的匹配方法稱為 Brute-force 演算法. 顯然, Brute-force 演算法需要的額外輔助空間和原始字串長度 n 以及要搜尋的子串長度 m 都無關. 因此 Brute-force 演算法的空間複雜度為 \Theta(1). 最壞情況下, Brute-force 演算法之多需要進行 n \cdot m 次比較, 故時間複雜度為 \Theta(nm). 但是由於 0 < m \leq n, 根據大 O 記法的定義 (《漸近分析基礎》定義 1), 有 m = O(n). 故 Brute-force 演算法的時間複雜度又可以表示為 O(n^{2}).

2.2.2 基於有限狀態機的搜尋

Brute-force 演算法的優點是足夠簡單, 但是缺點也很明顯 : 當字串非常長的時候, 在運氣不好的情況下, 搜尋時間會較長. 因此, 我們必然會想盡一切辦法來優化 Brute-force 演算法.

假如我們在 AAABAAAAAA 中搜尋 AAAAAA, 那麼根據 Brute-force 演算法的過程, 應該有

但事實上, 在第一遍比較的時候, 我們已經可以確定第 4 個字元 B 並不會和要搜尋字串中的任何字元匹配. 我們也許可以想方設法跳過 (2), (3) 和 (4) 這三個比較. 另一方面, 如果要在 AABAABAAAA 中搜尋 AABAAA 時, AABAAB 和 AABAAA 的比較會在最後一個字元失敗. 根據 Brute-force 演算法, 接下來應該比較 ABAABA 和 AABAAA. 但是由於ABA 和 AAB 根本不會匹配, 是否也可以設法跳過中間的比較呢?

我們在本小節中將要介紹的基於有限狀態機的搜尋方法和下一小節中將要介紹的 Knuth-Morris-Pratt 演算法都設法利用了第一次搜尋中的已知信息, 跳過了不必要的比較.

有限狀態機的理論來源於計算理論 (《【計算理論】自動機與語言 – 正規語言之有限自動機》, 對於有限狀態機的完整定義和介紹請閱覽該文章, 本文中不再詳細介紹).

定義 5. 一個字串的有限狀態機 \mathbb {M} 是一個五元組 \mathbb {M} = (Q, q_{0}, A, \Sigma, \delta). 其中,

• Q 是狀態的有限集合;
• q_{0} \in Q 是 \mathbb {M} 的初始狀態;
• A \subseteq Q 是 \mathbb {M} 的接受狀態集合, Q \setminus A 是 \mathbb {m} 的拒絕狀態集合;
• \Sigma 是有限輸入字元集合;
• \delta 是 Q \times \Sigma 到 Q 的函數, 稱為 \mathbb {M} 的轉移函數.

有限狀態機初始時處於狀態 q_{0} = 0, 每從 \Sigma 中讀入一個字元 c, 則通過轉移函數 \delta(q, c) 來計算轉移狀態. 若 \delta(q, c) \in A, 則稱 \mathbb {m} 接受了狀態 \delta(q, c); 否則, 稱 \mathbb {M} 拒絕了狀態 \delta(q, c).

Figure 6 中展現了一個簡單的有限狀態機 \mathbb {M}. 在 \mathbb {M} 中, Q = \left \{ 0, 1, 2, 3 \right \}, q_{0} = 0 是初始狀態 (在 Figure 6 中被標記為灰色), A = \left \{ 3 \right \} 是接受狀態集合 (在 Figure 6 中被標記為紅色), \Sigma = \left \{ \text {a}, \text {b}, \text {c} \right \}. 從 Figure 6 中, 我們可以總結出 \mathbb {M} 的轉移函數為 \displaystyle {\begin {cases} \delta(0, \text {a}) = 1 \\ \delta(1, \text {a}) = 1 \\ \delta(1, \text {b}) = 2 \\ \delta(1, \text {c}) = 3 \\ \delta(2, \text {a}) = 1 \\ \delta(2, \text {b}) = 1 \\ \delta(2, \text {c}) = 3 \\ \delta(3, \text {a}) = 2 \\ \delta(3, \text {b}) = 2 \\ \delta(3, \text {c}) = 3. \end {cases}}

例題 2. 設輸入字串為 ababc, Figure 6 中的有限狀態機 \mathbb {M} 是否接受該字串?

解 :

初始時, q_{0} = 0, 讀入第一個字元 a 時, \mathbb {M} 的狀態轉移至 q = \delta(0, \text {a}) = 1. 讀入第二個字元 b 時, \mathbb {M} 的狀態轉移至 q = \delta(1, \text {b}) = 2. 讀入第三個字元 a 時, \mathbb {M} 的狀態轉移至 q = \delta(2, \text {a}) = 1. 讀入第四個字元 b 時, \mathbb {M} 的狀態轉移至 q = \delta(1, \text {b}) = 2. 最後讀入字元 c 時, \mathbb {M} 的狀態轉移至 q = \delta(2, \text {c}) = 3. 而最終狀態 q = 3 屬於 \mathbb {M} 的接受集合, 因此 \mathbb {M} 接受了字串 ababc.

\blacksquare

為了借助有限自動機跳過那些不必要的比較, 我們首先要明確在字串搜尋中, 有限狀態機在何時的狀態表明存在一個成功的匹配. 以在 S = s_{1}s_{2}s_{3}s_{4}s_{5}s_{6}s_{7} = \text {abababc} 中搜尋 S' = s_{1}'s_{2}'s_{3}'s_{4}'s_{5}' = \text {ababc} 為例. 顯然, s_{3}s_{4}s_{5}s_{6}s_{7} 與 S' 匹配. 因此, \delta(q = 6, s_{7}) 的值應該表示在 S 中找到了一個匹配. 容易地, 我們想到利用 \delta(q, s_{7}) = \mathop {\mathrm {card}}{S'} 來表示在 S 中找到了 S', 即轉移函數的值恰好等於子串 S' 的長度. 那些不能使得子串完全匹配的 \delta(q, s_{i}) 的值不應為 \mathop {\mathrm {card}}{S'}. 例如, s_{1}s_{2}s_{3}s_{4}s_{5} = \text {ababa} 和 S' 無法匹配, 故 \delta(q = 4, s_{5}) \neq \mathop {\mathrm {card}}{S'}.

如何定義 \delta(q = 4, s_{5}) 比較合理呢? 由於 \delta(q, s_{7}) = \mathop {\mathrm {card}}{S'} = 5, 所以在 \delta(0, s_{1}), \delta(1, s_{2}), ..., \delta(q, s_{6}) 會有一個逐漸增加的過程, 至少在靠近 q 時會存在局部增加的過程. 仔細觀察, 我們可以發現 S' 實際上是 S 的後綴. 而要想 S' 是 S 的後綴, S' \setminus \left \{ s_{5}' \right \} 必須是 S \setminus \left \{ s_{7} \right \} 的後綴. 遞迴地, S' \setminus \left \{ s_{5}', s_{4}' \right \} 必須是 S \setminus \left \{ s_{7}, s_{6} \right \} 的後綴; ...; S' \setminus \left \{ s_{5}', s_{4}', s_{3}', s_{2}' \right \} = s_{1}' 必須是 S \setminus \left \{ s_{7}, s_{6}, s_{5}, s_{4} \right \} = s_{1}s_{2}s_{3} 的後綴. 這裡, 我們便可以發現一個逐漸增加的過程, 即 S 的後綴和 S' 的前綴的重疊字元數量. 但是 S 後面可能還跟隨其它字元, 例如 S = \text {abababcdef}. 但是不論 S 如何變化, 如果 S' 存在於 S 中, 那麼總有一個 S 的前綴 S_{0} 使得 S' 是 S_{0} 的後綴. 自然地, 就有了上述遞迴的過程. 其中, S_{0} = s_{1}s_{2}...s_{i}s_{i + 1}...s_{i + \mathop {\mathrm {card}}{S'} - 1}, S' = s_{i}s_{i + 1}...s_{i + \mathop {\mathrm {card}}{S'} - 1}.

綜合上面的討論, 我們可以定義字串搜尋的輔助函數 \sigma(X, Y), 其滿足 \displaystyle {\sigma(X, Y) = \max \left \{ k : y_{1}y_{2}...y_{k} \text { 是 } X \text { 的後綴} \right \}}. 其中, X = x_{1}x_{2}..., Y = y_{1}y_{2}...y_{k}.... 根據 \sigma 的定義, 我們可以知道 \sigma(X, Y) 表示字串 X 的後綴和 Y 的前綴的最大重疊部分長度. 例如對於 X = \text {abcde}, Y = \text {deabc}, Z = \text {ea} 和 U = \text {fe}, 有 \sigma(X, Y) = 2 (X 的後綴 de 與 Y 的前綴 de 重疊, 並且該重疊為最長的部分), \sigma(X, Z) = 1 和 \sigma(X, U) = 0. 對於一個長度為 m 的字串 Y, 若且唯若 Y 是 X 的後綴時, \sigma(X, Y) = m. 除此之外, 根據 \sigma 的定義, 若 Y 是 X 的後綴, 則 \sigma(Z, Y) \leq \sigma(Z, X). 其中, Z 是任意字串.

對於字串 S = s_{1}s_{2}...s_{n} 和 S' = s_{1}'s_{2}'...s_{m}' (m \leq n), 若有 s_{1}'s_{2}'...s_{k - 1}' \in S 且 s_{1}'s_{2}'...s_{k - 1}'s_{k}' \in S, 設 s_{1}' 在 S 中的某個起始位置為 r + 1, 則應有 \displaystyle {\begin {aligned} &\ \ \ \ \ \sigma(s_{1}s_{2}...s_{r}s_{r + 1}...s_{r + k}, s_{1}'s_{2}'...s_{k}') \\ &= \sigma(s_{1}s_{2}...s_{r}s_{r + 1}...s_{r + k - 1}, s_{1}'s_{2}'...s_{k - 1}) + 1 \\ &= \sigma(s_{1}s_{2}...s_{q}s_{r + 1}...s_{r + k - 2}, s_{1'}s_{2}'...s_{k - 2}') + 2 \\ &= ... \\ &= \sigma(s_{1}s_{2}...s_{r}s_{r + 1}, s_{1}') + k - 1 = k. \end {aligned}} 根據等式, 理應有 \sigma(s_{1}s_{2}...s_{r}s_{r + 1}, s_{1}') = \delta(q, s_{1}') = 1. 這樣, 若 s_{1}'s_{2}'...s_{k}' 在 S 中的起始位置同樣為 r + 1 且 \sigma(s_{1}s_{2}...s_{r}, s_{1}') = \delta(\cdot, s_{1}') = 0, 則可得 \displaystyle {\begin {cases} q \leftarrow \delta(0, s_{1}') = \sigma(s_{1}s_{2}...s_{r}s_{r + 1}, s_{1}') = 1 \\ q \leftarrow \delta(1, s_{2}') = \sigma(s_{1}s_{2}...s_{r}s_{r + 1}s_{r + 2}, s_{1}'s_{2}') = 2 \\ \vdots \\ q \leftarrow \delta(k - 1, s_{k}') = \sigma(s_{1}s_{2}...s_{r}s_{r + 1}s_{r + 2}...s_{r + k}, s_{1}'s_{2}'...s_{k}') = k. \end {cases}} 在這個子過程中, q 的值實現了局部增加, 從 0 增加到了 k.

通過上面的分析, 我們其實可以得到 Brute-force 演算法的有限狀態機 \mathbb {M} 轉移函數為 \displaystyle {\delta(q, s_{k}) = \begin {cases} \sigma(s_{1}s_{2}...s_{k}, S') & {s_{r + k} = s_{k}'} \\ 0 & {s_{r + k} \neq s_{k}'} \end {cases}}. 在 Brute-force 演算法下, 每一次匹配失敗的時候, 狀態 q 的值就會從零重新開始. 而優化 Brute-force 演算法的關鍵就在於避免 q 在每一次比較失敗之後清零.

假設現在要在 s_{1}s_{2}...s_{k}s_{k + 1}s_{k + 2}...s_{k + q}s_{k + q + 1}...s_{n} 中搜尋子串 s_{1}'s_{2}'...s_{q}'s_{q + 1}'...s_{m}'. 若有 \sigma(s_{1}s_{2}...s_{k}s_{k + 1}s_{k + 2}...s_{k + q}, s_{1}'s_{2}'...s_{q}') = q \neq 0, 狀態 q 其實表示了 s_{k + 1}s_{k + 2}...s_{k + q} = s_{1}'s_{2}'...s_{q}'. 優化 Brute-force 演算法的關鍵點在於當 s_{k + q + 1} \neq s_{q + 1}' 時, q 的值應該如何變化.

根據 Figure 7, 假如 s_{k + q + 1} \neq s_{q + 1}', 但是如果 s_{k + t}s_{k + t + 1}...s_{k + q}s_{k + q + 1} = s_{1}'s_{2}'...s_{q - t + 1}', 我們可以設法跳過這兩個子串之間的比較. 詳細地說, s_{k + t}s_{k + t + 1}...s_{k + q + 1} 是 Figure 7 中第一個字串灰色部分到紅色部分 \text {b} 的後綴, 其長度為 q - t + 1, 這個後綴和 Figure 7 中第二個字串灰色部分的前 q - t + 1 個字元所形成的前綴是匹配的. 那我們可以跳過前 q - t + 1 個字元的比較. 例如在 ccccabababacadddd 中搜尋 ababaca, cccc 就是 Figure 7 中的 s_{1}s_{2}...s_{k}, ababa 是 s_{k + 1}s_{k + 2}...s_{k + q}, 它和 ababaca 中的前五個字元 (s_{1}'s_{2}'...s_{q}') 可以產生匹配, 故此時 q = 5. 但是 s_{k + q + 1} 為 a, 而 s_{q + 1}' 為 c, 無法匹配. 也就是 cccc|ababab 的後綴和 ababac 無法匹配, Brute-force 演算法會接著比較 cccca|bababa 和 ababac. 然而仔細觀察之後, 我們可以發現 cccc|ab|abab 的後綴 abab 和 abab|aca 的前綴 (前四個字元) 可以匹配. 即 cccc|ab|abab 的後綴 abab 是 Figure 7 中的 s_{k + t}s_{k + t + 1}...s_{k + q + 1}; abab|aca 的前綴 abab 是 Figure 7 中的 s_{1}'s_{2}'...s_{q - t + 1}'. 這四個字元是我們已經尋訪過且已知的字元, 我們自然希望有限狀態機可以告訴我們, 當 s_{k + q + 1} \neq s_{q - t + 1}' 時, 跳過 s_{k + 1}s_{k + 2}...s_{k + q + 1} 和 s_{1}'s_{2}'...s_{q - t + 1}' 的比較, 直接比較 s_{k + q + 2} 和 s_{q - t + 2}' 以及之後的字元即可. 在 Figure 7 這個實例中, 上一次匹配失敗發生在子串的第六個字元, 當時的 q 值為 5. 直接比較 s_{k + q + 2} 和 s_{q - t + 2}' 的話, 我們可以容易得出此時匹配發生在子串的第五個字元, 自然 q 要向前回退一.

總結上面的討論 : 在 Figure 7 這個實例中, 我們希望有限狀態機告訴我們 : 當字串的第十個字元 b 和子串的第六個字元 c 匹配失敗, 我們可以知道 cccc|ab|abab 的後綴有四個字元可以和 abab|aca 的前綴匹配, 接下來的比較應該從第十一個字元和子串的第 q 個字元開始 (此時 q 被更新為 5). 而 q 的更新方式在前面被我們定義為 \displaystyle {q \leftarrow \sigma(s_{1}s_{2}...s_{k}, s_{1}'s_{2}'...s_{q_{0} - 1}'s_{q_{0}}'s_{q_{0} + 1}'...s_{m}')}. 其中, q_{0} 是舊值.

設有字串 S = s_{1}s_{2}...s_{n} 的前綴 s_{1}s_{2}...s_{k} 和 S' = s_{1}'s_{2}'...s_{m}' (0 < m \leq n). 根據輔助函數 \sigma 的定義, \sigma(s_{1}s_{2}...s_{k}, S') 的意義是 s_{1}s_{2}...s_{k} 的後 q 個字元 s_{k - q + 1}s_{k - q + 2}...s_{k} 和 s_{1}'s_{2}'...s_{q}' 是相同的. 也就是說, \displaystyle {s_{1}s_{2}...s_{k - q}s_{k - q + 1}s_{k - q + 2}...s_{k} = s_{1}s_{2}...s_{k - q}s_{1}'s_{2}'...s_{q}'}. 事實上, 我們不再關心前 k - q 個字元, 因為在那裡面並不能找到 S'. 於是問題就轉變成在 s_{k - q + 1}s_{k - q + 2}...s_{k}s_{k + 1}...s_{n} 中搜尋 S'. 另外, 由於 \displaystyle {\delta(q, s_{k + 1}) = \begin {cases} q + 1 & {s_{k + 1} = s_{q + 1}'} \\ \sigma(s_{k - q + 1}s_{k - q + 2}...s_{k}s_{k + 1}, S') & {s_{k + 1} \neq s_{q + 1}'}. \end {cases}} 我們可以將其中的 \sigma(s_{k - q + 1}s_{k - q + 2}...s_{k}s_{k + 1}, S') 替換為 \sigma(s_{1}'s_{2}'...s_{q}'s_{k + 1}, S'). 此時, \sigma 的值僅依賴於 s_{1}'s_{2}'...s_{q}' 和一個未知的字元 s_{k + 1}. 如果把未知字元作為變量, 基於有限狀態機的子串搜尋的轉移函數可以定義為 \displaystyle {\delta(q, s_{k + 1}) = \sigma(s_{1}'s_{2}'...s_{q}'s_{k + 1}, S')}.

定義 5'. 若要在字串 S = s_{1}s_{2}...s_{n} 中搜尋子串 S' = s_{1}'s_{2}'...s_{m}', 其有限狀態機為 \displaystyle {\mathbb {M} = (Q, q_{0}, A, \Sigma, \delta)}. 其中,

• Q = \left \{ 0, 1, 2, ..., m \right \} 是狀態機的有限集合;
• q_{0} \in Q 是 \mathbb {M} 的初始狀態;
• m \in Q 是 \mathbb {M} 的唯一接受狀態, 即 A = \left \{ M \right \};
• \Sigma = \left \{ s_{i_{1}}', s_{i_{2}}', ..., s_{i_{k}}' \right \} 是有限輸入字元集合 (s_{i_{j}} \in S', s_{i_{t}} \neq s_{i_{u}}, j, t, u = 1, 2, ..., k 且 t \neq u);
• 對於任意狀態 q 和即將讀入的字元 c, 定義轉移函數為 \displaystyle {\delta(q, c) = \sigma(s_{1}'s_{2}'...s_{q}'c, S')}. 我們約定 \delta(q = 0, \emptyset) = 0.

有了有限狀態機 \mathbb {M} 的定義之後, 我們可以逐個讀入 S 中的字元 s_{k}, 結合狀態 q 得到 \delta(q, s_{k}) 的值. 若 \delta(q, s_{k}) = \mathop {\mathrm {card}}{S'}, 則我們找到了 S' 在 S 中的一個位置 k - \mathop {\mathrm {card}}{S}' + 1. 其中, q = 0, 1, 2, ..., \mathop {\mathrm {card}}{S'}. 當 q = q_{0} = 0 時, \mathbb {M} 開始讀入 S 的第一個字元 s_{1}, 並且計算 \sigma(q = 0, s_{1}).

現在還有一個問題懸而未決. 我們定義轉移函數的討論看似合理, 但是等式是否總是成立?

引理 1. 對於任意字串 X = x_{1}x_{2}...x_{n} 與 Y = y_{1}y_{2}...y_{m} 和任意字元 c, 有 \displaystyle {\sigma(Xc, Y) \leq \sigma(X, Y) + 1}. 其中, Xc = x_{1}x_{2}...x_{n}c.

證明 :

設 \sigma(X, Y) = 0, 即 X 的後綴與 Y 的前綴沒有重疊的部分, 亦即

在 X 後面增加 c 有且唯有兩種情況 :

綜上所述, \sigma(Xc, Y) \leq \sigma(X, Y) + 1 在 \sigma(X, Y) = 0 時成立.

設 q = \sigma(X, Y) \neq 0, 那麼 X 的後綴與 Y 的前綴存在重疊部分, 也就有

綜上所述, \sigma(Xc, Y) \leq \sigma(X, Y) + 1 在 \sigma(X, Y) > 0 時成立.

綜合上面的討論, \sigma(Xc, Y) \leq \sigma(X, Y) + 1 成立.

\blacksquare

引理 2. 設有字串 X, Y 和 Z, 總有 \displaystyle {\sigma(X, Z) \leq \sigma(XY, Z)} 成立. 其中, XY 表示在字串 X 尾部拼接 Y.

證明 :

顯然地, 我們可以知道 \mathop {\mathrm {card}} {X} \leq \mathop {\mathrm {card}} {XY}. X 與 XY 的後綴和 Z 前綴的匹配情況分為兩種 :

1. 當 \mathop {\mathrm {card}} {Z} < \mathop {\mathrm {card}} {Y} 時, 我們令 k = \sigma(Y, Z). 記 Z_{k} 是 Z 的前 k 個字元, 那麼 Z_{k} 是 Y 的後綴, 而 Y 是 XY 的後綴, 自然 Z_{k} 也是 XY 的後綴. 此時, 我們可以將 Y 寫為 Y = Y'Z_{k}. 因為 Z 的長度有限, 所以不論 Y' 發生什麼變化, 都不會影響 \sigma(Y, Z) 的值. 同樣地, 因 XY = XY'Z_{k}, 相當於將 Y' 變成了 XY', 即在 Y' 之前增加了一些字元, 亦即在 Y 之前增加了一些字元, 所以 \sigma 的值仍然不變, 我們便有了 \displaystyle {\sigma(Y, Z) = \sigma(XY, Z) \Rightarrow \sigma(Y, Z) \leq \sigma(XY, Z)}.

   

2. 當 \mathop {\mathrm {card}} {Z} \geq \mathop {\mathrm {card}} {Y} 時, 我們記 k = \sigma(Y, Z). 我們容易得到 Z 的前 k 個字元 Z_{k} 與 Y 和 XY 的後綴匹配. 但對於 Z, 可能存在一個 i > k 使得 \sigma(XY, Z) = i, 例如 Y = \text {a}, XY = \text {daba}, Z = \text {abac}. 此時, \sigma(Y, Z) < \sigma(XY, Z). 若不存在這樣的 i, 那麼 \sigma(Y, Z) = \sigma(XY, Z). 綜合兩種情況, 我們有 \displaystyle {\sigma(Y, Z) \leq \sigma(XY, Z)}.

   

綜上所述, \displaystyle {\sigma(X, Z) \leq \sigma(XY, Z)} 成立.

引理 3. 對於任意字串 X, s_{1}'s_{2}'...s_{m}' 和字元 c, 若 q = \sigma(X, s_{1}'s_{2}'...s_{m}'), 則有 \displaystyle {\sigma(Xc, s_{1}'s_{2}'...s_{m}') = \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}')}.

證明 :

根據 \sigma 的定義, 可以知道 s_{1}'s_{2}'...s_{q}' 是 X 的後綴. 自然地, s_{1}'s_{2}'...s_{q}'c 也是 Xc 的後綴. 若設 r = \sigma(Xc, s_{1}'s_{2}'...s_{m}'), 則 s_{1}'s_{2}'...s_{r}' 是 Xc 的後綴. 根據引理 1 可知 r \leq q + 1, 即 s_{1}'s_{2}'...s_{r}' 的長度不大於 s_{1}'s_{2}'...s_{q}'c 的長度. 由於 s_{1}'s_{2}'...s_{q}'c 和 s_{1}'s_{2}'...s_{r}' 都是 Xc 的後綴, 所以根據長度可以得到 s_{1}'s_{2}'...s_{r}' 是 s_{1}'s_{2}'...s_{q}'c 的後綴. 根據引理 2, \sigma(s_{1}'s_{2}'...s_{r}', s_{1}'s_{2}'...s_{m}') \leq \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}'). 又因為 r = \sigma(s_{1}'s_{2}'...s_{r}', s_{1}'s_{2}'...s_{m}'), 有 r = \sigma(Xc, s_{1}'s_{2}'...s_{m}') = \sigma(s_{1}'s_{2}'...s_{r}', s_{1}'s_{2}'...s_{m}') \leq \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}'), 即 \sigma(Xc, s_{1}'s_{2}'...s_{m}') \leq \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}').

另一方面, s_{1}'s_{2}'...s_{q}'c 是 Xc 的後綴, 根據引理 2 又有 \sigma(Xc, s_{1}'s_{2}'...s_{m}') \geq \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}').

綜上所述, 有 \displaystyle {\sigma(Xc, s_{1}'s_{2}'...s_{m}') = \sigma(s_{1}'s_{2}'...s_{q}'c, s_{1}'s_{2}'...s_{m}')}.

\blacksquare

實際上, 我們在引出定義 5' 的時候已經討論甚至導出了引理 3, 只是上面我們給出了更加嚴格的證明.

要證明轉移函數是正確的, 我們應該首先證明在 S = s_{1}s_{2}... 中搜尋子串 S' = s_{1}'s_{2}'... 時, 當 S' 的狀態機 \mathbb {M} 每讀入一個字元 s_{k} 時, \delta(q, s_{k}) 與 \sigma(s_{1}s_{2}...s_{k}, S') 總是保持著恆等關係. 這樣才能導出對於任意字元 c, 轉移函數 \delta(q, c) = \sigma(s_{1}'s_{2}'...s_{q}'c, S') 的正確性.

為了表示狀態 q 的不同變化, 我們定義輔助函數 \varphi : \displaystyle {\varphi(Xc) = \begin {cases} 0 & {Xc = \emptyset} \\ \delta(0, c) & {X = \emptyset, Xc \neq \emptyset} \\ \delta(\varphi(X), c) & {X \neq \emptyset, Xc \neq \emptyset}. \end {cases}}

定理 1. 若要在字串 S = s_{1}s_{2}...s_{n} 中搜尋 S' = s_{1}'s_{2}'...s_{m}', 對於 i = 0, 1, 2, ..., n, 有 \displaystyle {\varphi(s_{1}s_{2}...s_{i}) = \sigma(s_{1}s_{2}...s_{i}, S')}. 其中, m \leq n.

證明 :

我們使用歸納法進行證明. 當 i = 0 時, S = \emptyset, 此時 \varphi(\emptyset) = 0 = \sigma(\emptyset, S').

現在假設對於 i \leq k, 總有 \varphi(s_{1}s_{2}...s_{i}) = \sigma(s_{1}s_{2}...s_{i}, S').

當 i = k + 1 時, 記 q = \varphi(s_{1}s_{2}...s_{k}), 根據假設有 q = \sigma(s_{1}s_{2}...s_{k}, S'). 根據 \sigma 的定義可知 s_{k - q + 1}s_{k - q + 2}...s_{k} 時 S' 的前綴, 即 s_{k - q + 1}s_{k - q + 2}...s_{k} = s_{1}'s_{2}'...s_{q}'. 根據引理 3 可得 \displaystyle {\begin {aligned} \sigma(s_{1}'s_{2}'...s_{q}'s_{k + 1}, S') &= \sigma(s_{k - q + 1}s_{k - q + 2}'...s_{k}s_{k + 1}, S') \\ &= \sigma(s_{1}s_{2}...s_{k - q + 1}s_{k - q + 2}...s_{k}s_{k + 1}, S') \\ &= \sigma(s_{1}s_{2}...s_{k}, S'). \end {aligned}} 所以, \varphi(s_{1}s_{2}...s_{k}s_{k + 1}) = \sigma(s_{1}s_{2}...s_{k}s_{k + 1}, S'), 也就是當 i = k + 1 時, 仍然有 \varphi(s_{1}s_{2}...s_{i}) = \sigma(s_{1}s_{2}...s_{i}, S').

綜上所述, \varphi(s_{1}s_{2}...s_{i}) = \sigma(s_{1}s_{2}...s_{i}, S') 成立.

\blacksquare

在歸納過程中的 i = k + 1 情形中, 若記 c = s_{k + 1}, 便可得到 \delta(q, c) = \sigma(s_{1}'s_{2}'...s_{q}'c, S') 恆成立. 因此我們這樣定義轉移函數是正確的.

當有了轉移函數之後, 我們很容易就可以計算每個 \delta 值. 假設要在字串 S 中搜尋子串 S' = s_{1}'s_{2}'...s_{m}', 我們每次都取 S' 的前 i 個, 然後不斷從 \Sigma 中取出一個字元 c, 計算 \sigma(s_{1}'s_{2}'...s_{i}'c, S') 的值, 這便是 \delta(i, c) 的值. 其中, i = 0, 1, 2, ..., m. 注意, \delta(0, c) = 1 若且唯若 c = s_{1}'.

Algorithm 3 在尋訪 S' 的前 i 個字元的時候, 每次尋訪的途中都需要額外尋訪整個 \Sigma, 然後檢測 s_{1}'s_{2}'...s_{i}'c 後綴和 S' 前綴的最大重疊長度. 因此 Algorithm 3 的時間複雜度為 O(m^{3}\mathop {\mathrm {card}}{\Sigma}). Algorithm 3 在第 i 步時會產生 \mathop {\mathrm {card}}{\Sigma} 個狀態, 這些狀態都需要儲存. 因此 Algorithm 3 空間複雜度為 \Theta(m\mathop {\mathrm {card}}{\Sigma}).

Algorithm 3 還可以繼續被優化, 例如對於任意 c \in \Sigma, 我們可以首先檢測 c 是否同時也在 S' 中. 如果 c \notin S', 那麼我們直接令 \delta(i, c) = 0 即可.

雖然 Algorithm 3 的時間複雜度和空間複雜度都非常高, 但是好在有限狀態機是針對 S' 的狀態機, 而不是 S 的狀態機. 這就意味著如果子串 S' 是固定的, 當我們需要在不同子串中搜尋 S' 的時候, 我們只需要建立一次有限狀態機即可. 值得慶幸的是, 預處理的高複雜度換來的是線性時間複雜度的搜尋時間!

當搜尋開始的時候, 狀態 q = 0. 讀入第一個字元 c 之後, 我們只需要查表即可知道 q 的最新狀態. 接下來每次讀入一個字元都進行類似的處理, 當 q = \mathop {\mathrm {card}}{S'} 的時候, 我們就在 S 中找到了 S'.

Algorithm 4 並沒有使用額外的輔助空間, 所以空間複雜度為 \Theta(1). 另外, Algorithm 4 只尋訪了一次 S, 並沒有尋訪 S', 所以時間複雜度為 \Theta(\mathop {\mathrm {card}}{S}) = \Theta(n).

2.2.3 Knuth-Morris-Pratt 演算法

基於有限狀態機的字串搜尋演算法雖然在搜尋的過程中表現出了高效的線性時間複雜度, 但是其初始化 \delta 的代價極高. 現在我們的目標應該是維持線性時間複雜度的搜尋時間, 並且將初始化的時間複雜度盡可能降低. 如果有可能的話, 我們希望初始化的時間複雜度降低到線性級別, 空間複雜度也同樣下降到線性級別.

我們首先討論空間複雜度下降的可能性. Algorithm 3 的空間複雜度為 \Theta(m\mathop {\mathrm {card}}{\Sigma}), 那麼下降的目標應該是 \Theta(m) 還是 \Theta(\mathop {\mathrm {card}}{\Sigma}) 呢? 在基於有限狀態機的字串搜尋中, 狀態機是針對子串的狀態機, 所以 \Theta(m) 的空間是必須的. 我們也不難想到, 基於子串建立狀態機是最高效的, 因為有限輸入字元集合中的元素數量必然多於子串所形成的元素集合. 從另一角度來說, 從存在一些 c \in \Sigma, 這些字元不存在於子串當中.

對比 Brute-force 演算法和基於有限狀態機的演算法, 我們可以發現這兩個演算法幾乎完全不同. 詳細地說, Brute-force 是基於檢測時偏移的演算法, 每次檢測到不匹配後會向後偏移一個字元重新進行檢測; 基於有限狀態機的演算法完全沒有使用偏移, 而是查 \delta 表. 那麼是否存在一種方法, 提前準備了一些狀態 (類似於 \delta 表), 在偏移的時候利用提前準備好的狀態跳過一些無用比較呢?

重新考慮 Figure 5 :

Brute-force 演算法在每次匹配失敗之後, 都會使子串向後偏移一個字元, 然後重新開始新的比較. 第一次比較在 B 處失敗, 但是這一次的比較已經提供了足夠的信息 : AAAAAA 的前三個字元不存在 B, 所以可以直接跳過 (2), (3) 和 (4) 的比較. 下面我們就嘗試將這種信息利用起來.

假設 s_{t + 1}s_{t + 2}...s_{t + q} = s_{1}'s_{2}'...s_{q}', 即從 t + 1 這個位置開始有 q 個字元發生了匹配, 但在 s_{t + q + 1} 和 s_{q + 1}' 處匹配失敗. 對於已比較的部分 s_{t + 1}s_{t + 2}...s_{t + q}, 我們希望在其中找到一個 t' \in (t + 1, t + q], 使得 \displaystyle {s_{t' + 1}s_{t' + 2}...s_{t + q} = s_{1}'s_{2}'...s_{k}'}. 換句話說, 我們希望向後偏移若干個字元, 從 s_{t' + 1} 開始, 有 k 個字元和 s_{1}'s_{2}'...s_{q}' 的前 k 個字元匹配. 不難算出, 偏移量為 (t' + 1) - (t + 1) = t' - t.

這樣做的好處是我們不僅可以跳過 s_{t + 2}s_{t + 3}...s_{t'} 這些字元與子串的比較, 還可以跳過 s_{t' + 1}s_{t' + 2}...s_{t + q} 和子串的比較, 因為我們通過已經比較得到的信息可以確定 \displaystyle {s_{t' + 1}s_{t' + 2}...s_{t + q} = s_{1}'s_{2}'...s_{k}'}.

當比較進行至 s_{t + q + 1} 和 s_{k + 1}' 時, 目前我們雖然沒有分析得到具體的偏移量, 但是可以確定的是 t 和 q 的值暫時固定. 顯然, k 越大, t 便越小, t' - t 也越小; k 越小, t' 便越大, t' - t 也越大. 這樣就有了兩種較優的情形 :

1. k 靠近 t + q, 說明 s_{t' + 1}s_{t' + 2}...s_{t + q} 後綴中有越多的字元和 s_{1}'s_{2}'...s_{m}' 的前綴相匹配. 從另一角度來說, 接下來需要進行比較的字元越少, 匹配的成功率自然也就越高;
2. k 越接近於零, 說明 s_{t' + 1}s_{t' + 2}...s_{t + q} 的後綴中只有很少的字元可以和 s_{1}'s_{2}'...s_{m}' 的前綴相匹配. 雖然接下來需要比較字元數量比第一種情況更多, 但是跳過的字元數量也相當多, 跳過中間不必要的比較為整個演算法節省了不少時間. 對於 k = 0 這種極端情況來說, 從任意 s_{i} 開始的 m 個字元 s_{i + 1}s_{i + 2}...s_{i + m} 都不可能和 s_{1}'s_{2}'...s_{m}' 匹配, 所以這中間所有的比較都可以跳過. 下一次比較直接從 s_{t + q + 1} 和 s_{1}' 開始.

雖然 s_{t + q + 1} \neq s_{q + 1}', 由於 s_{t' + 1}s_{t' + 2}...s_{t + q} = s_{1}'s_{2}'...s_{k}', 想要在 s_{t + 1}s_{t + 2}...s_{t + q} 中找到一個最長的後綴與 s_{1}'s_{2}'...s_{q}' 的前綴匹配, 也就等同於在 s_{1}'s_{2}'...s_{q}' 中找到一個最長的後綴與其自身的前綴 s_{1}'s_{2}'...s_{k}' 匹配. 這個最長的前綴保證了 k 可以取得最大值. 經過上面的討論, 我們可以定義一個前綴函數 \pi, 用來表示對於任意 q = 1, 2, ..., m, 滿足 s_{1}'s_{2}'...s_{k}' 是 s_{1}'s_{2}'...s_{q}' 的後綴最大值 k : \displaystyle {\pi(q) = \max \left \{ k : k < q \text { 且 } s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{k}' \text { 的後綴} \right \}}.

例題 2. 求字串 S' = \text {abababcab} 的前綴函數 \pi_{S'}(q).

解 :

當 q = 1 時, k 只能為零, 故 \displaystyle {\pi_{S'}(1) = \pi_{S'}[\text {a}] = 0}.

當 q = 2 時, 有 k \in \left \{ 0, 1 \right \}. 若 k = 1, a 必須是 ab 的後綴, 這顯然不成立. 故唯有 k = 0, 即 \displaystyle {\pi_{S'}(2) = \pi_{S'}[\text {ab}] = 0}.

當 q = 3 時, 有 k \in \left \{ 0, 1, 2 \right \}.

當 k = 1 時, a 是 aba 的後綴; 當 k = 2 時, ab 並非 aba 的後綴. 故 \displaystyle {\pi_{S'}(3) = \pi_{S'}[\text {aba}] = 1}.

當 q = 4 時, 有 k \in \left \{ 0, 1, 2, 3 \right \}, 列出前後綴比較圖可知 \displaystyle {\pi_{S'}(4) = \pi_{S'}[\text {abab}] = 2}.

當 q = 5 時, 有 k \in \left \{ 0, 1, 2, 3, 4 \right \}, 列出前後綴比較圖可知 \displaystyle {\pi_{S'}(5) = \pi_{S'}[\text {ababa}] = 3}.

類似地, 根據

我們分別可以得到 \displaystyle {\pi_{S'}(6) = 4, \pi_{S'}(7) = 0, \pi_{S'}(8) = 1, \pi_{S'}(9) = 2}.

\blacksquare

當我們得到子串 S' 的前綴函數 \pi_{S'}(q) 後, 我們可以透過和基於有限狀態機的字串搜尋演算法類似的比較方法, 在字串 S 中搜尋子串 S' : 設比較進行至 s_{t + q + 1} 和 s_{q + 1}' 時發生了不匹配, 首先查表得到 k = \pi(q). 接下來的比較從 s_{t + q + 1} 和 s_{k + 1}' 開始, 若仍不匹配, 則重新查表得到 k = \pi(\pi(q)); 如果匹配, 那麼就繼續向後比較. 如此循環往復, 直到狀態轉移到 \mathop {\mathrm {card}} {S'} 停止.

根據例題 2 所呈現的步驟, 我們可以很快寫出 \pi(q) 的初始化演算法, 但是例題 2 中是透過列舉每一個可能的前綴得到最終 \pi(q) 值的. 仔細觀察 Figure 13-2 和 Figure 13-3,

同時關注兩個字串的前綴部分, 我們可以發現右側比左側多出一個字元, 即新加入的字元 b 恰好也與左側 s_{\pi(q) + 1} 相同. 因此在建立 \pi 的時候, 對於 \pi(q + 1) 的值, 我們可以首先比較 s_{\pi(q) + 1} 與新加入的字元 s_{q + 1}. 若 s_{\pi(q) + 1} = s_{q + 1}, 則有 \displaystyle {\pi(q + 1) = \pi(q) + 1}. 接下來的關鍵便是 \pi(q + 1) > \pi(q) + 1 是否有可能成立.

斷言 1. 若要在字串 S 中搜尋子串 S', 對於任意 q = 1, 2, ..., \mathop {\mathrm {card}}{S'}, \pi(q + 1) > \pi(q) + 1 無法成立.

證明 :

不妨假設 \pi(q + 1) > \pi(q) + 1 可以成立, 那麼至少有 \displaystyle {\pi(q + 1) \geq \pi(q) + 2}. 我們首先取 \pi(q + 1) = \pi(q) + 2 能夠成立的情形來討論.

記 k = \pi(q). 由 \pi 的定義可知, s_{1}'s_{2}'...s_{k}'s_{k + 1}' 是 s_{1}'s_{2}'...s_{q}'s_{q + 1}' 的後綴, s_{1}'s_{2}'...s_{k}' 是 s_{1}'s_{2}'...s_{q}' 的後綴.

顯然, s_{1}'s_{2}'...s_{k}'s_{k + 1}' 是 s_{1}'s_{2}'...s_{q}' 的後綴, 故 \pi(q) 的值應該是 k + 1, 這與 \pi(q) = k 的事實不相符. 因此 \pi(q + 1) = \pi(q) + 2 不成立.

對於 \pi(q + 1) > \pi(q) + 2 的情形, 我們都可以使用類似的方式證明 \pi(q + 1) = \pi(q) + c (c > 2) 不成立. 綜上所述, \pi(q + 1) > \pi(q) + 1 不成立.

\blacksquare

上面只是解決了當 s_{q + 1}' = s_{\pi(q) + 1} 的情形, 若 s_{q + 1}' \neq s_{\pi(q) + 1} 的時候, 我們已經可以確定 \pi(q + 1) < \pi(q). 最容易想到的確定 \pi(q + 1) 的方案是比較 s_{q - \pi(q) + 2}'s_{q - \pi(q) + 3}...s_{q}' 與 s_{1}'s_{2}'...s_{\pi(q)}', 且比較的順序是從後往前. 若 s_{\pi(q)}' = s_{q}', 則比較 s_{\pi(q) - 1}' 與 s_{q - 1}', 循環往復; 若 s_{\pi(q)}' \neq s_{q}', 則比較 s_{q - \pi(q) + 2}'s_{q - \pi(q) + 3}...s_{q}' 與 s_{1}'s_{2}'...s_{\pi(q) - 1}'. 不斷重複上述過程, 直到得到 \pi(q + 1) 的值為止. 當 \pi(q + 1) = 0 時, 上述流程可以提前終止.

然而這個方法並不是最優的方法, 它只是最容易想到的方案. 在本節的最開始, 我們已經提到希望充分利用之前比較已經產生的信息, 跳過中間的一些無用比較. 現在讓我們重新考慮 s_{q + 1}' \neq s_{\pi(q) + 1} 的情形. 我們已經知道 \pi(q + 1) < \pi(q), 所以接下來的比較就會被限定在 s_{1}'s_{2}'...s_{\pi(q)}'. 由 \pi(q) 的定義可知 s_{1}'s_{2}'...s_{q}' 的前綴 s_{1}'s_{2}'...s_{q}' 又是其後綴.

要想計算 \pi(q + 1) 的值, 實際上就是要計算 s_{1}'s_{2}'...s_{\pi(q)}'s_{q + 1}' 的 \pi 值. 此時, 我們已知 \pi(\pi(q)) 的值, 因此需要比較 s_{\pi(\pi(q)) + 1} 與 s_{q + 1}' 是否相等. 若相等, 則 \pi(q + 1) = \pi(\pi(q)) + 1; 若不相等, 則問題又演變為計算 s_{1}'s_{2}'...s_{\pi(\pi(q))}'s_{q + 1}' 的 \pi 值. 重複上面步驟的結果僅有兩種 : \displaystyle {\pi(q + 1) = \begin {cases} \pi^{i}(q) + 1 \\ 0. \end {cases}} 其中, \pi^{i}(q) = \pi(\pi^{i - 1}(q)), \pi^{1}(q) = \pi(q). 若且唯若 \pi^{i}(q) = 0 且 s_{1}' \neq s_{q + 1}' 時, 有 \pi(q + 1) = 0.

Algorithm 6 使用了 k 來代表 \pi^{i}(q) 的變化. 當 k = 0 時, 說明了在加入 s_{q + 1}' 之前, 前一個子串的 \pi 值為零, 此時直接比較 s_{1}' 和 s_{q + 1} 即可. 當 k 不為零, 就是前面分析所得到的步驟. 前一個子串得到的 k 值在接下來可以復用, 不需要反覆取 \pi^{i}(q) 的值.

現在我們來分析 Knuth-Morris-Pratt 演算法的時間複雜度和空間複雜度. 結合 Algorithm 5 和 Algorithm 6, 我們可以知道前綴函數 \pi 的初始化和搜尋是相互獨立的, 因此兩者的複雜度應該是線性疊加的. 先來分析前綴函數 \pi 初始化的複雜度. 其空間複雜度十分簡單, 需要使用額外 m 個空間去儲存 \pi 值, 所以初始化 \pi 的空間複雜度為 \Theta(m). 一眼看上去, Algorithm 6 中的 q 值從 2 增加至 m, 每次 q 增加的時候, 內部的 k 至多計算 m 次. 所以初始化 \pi 的時間複雜度為 \Theta(m^{2})? 這是錯誤的. 事實上, k 的計算次數和 q 值無關, 即使演算法結束, k \leftarrow \pi(\pi(k)) 的計算總次數應該是至多 m - 1 次.

斷言 2. 在 Algorithm 6 中, k \leftarrow \pi(k) 的計算總次數至多為 m - 1 次.

證明 :

由於對於任意的 q, 總有 k < q. 若一個子串內只包含一個字元, 那麼 k 的增加至多為 m - 1 次, 其遞增只來源於 k \leftarrow k + 1. 如果想要證明斷言成立, 那麼只需要證明 k 減少的次數不大於 m - 1 次就可以了. 顯然, Algorithm 6 將 k 值初始化為零, 並且在 k 減少的過程中 (僅限於 Algorithm 6 第六行), 還保持了 k 值不能小於零. 這樣, 不論 k 值在減少的過程中如何變化, 其減少的次數必然不能大於 m - 1 次, 否則就打破了 k > 0 這一條件. 綜上所述, 在整個 Algorithm 6 中, k \leftarrow \pi(k) 的計算總次數至多為 m - 1 次.

\blacksquare

根據斷言 2, 我們可以輕鬆推論得出 k 的變化和 q 不是關聯的. 因為在計算不同 \pi(q) 的過程中, 和 k 有關的運算總次數的上界並不會隨著 q 的變化而發生變化. 所以我們可以得出 Algorithm 6 的時間複雜度為 \Theta(m) + O(m - 1) = \Theta(m).

有了斷言 2, Algorithm 5 的時間複雜度和空間複雜度的分析會簡單得多. Algorithm 5 中所使用的輔助空間數量和 S 與 S' 的長度都沒有關係, 因此其空間複雜度為 \Theta(1). 因為 \pi 是單調減少的函數, 所以 q \leftarrow \pi(q) 這樣的回退在整個演算法運作的過程中至多進行 m 次 (這個證明和斷言 2 幾乎一致). 與此同時, \pi 保證了跳過演算法中可能產生的任何無意義的比較, 使得 i 可以始終保持按 1 步長單調增加. 那麼比較至多進行 \Theta(m) + \Theta(n) 次.

由於 Algorithm 5 和 Algorithm 6 的時間複雜度和空間複雜度是線性疊加的關係, 因此 Knuth-Morris-Pratt 演算法的時間複雜度為 \Theta(m) + \Theta(n) = \Theta(n) + O(n) = \Theta(n) (這裡要注意我們一開始就假設了 m \leq n, 否則時間複雜度應該是 \Theta(m + n)), 空間複雜度為 \Theta(m). 我們可以看到, Knuth-Morris-Pratt 演算法在保持搜尋時間為 \Theta(n) 的前提下, 將預處理的時間複雜度從基於有限狀態機的字串搜尋演算法的 \Theta(m^{3}\mathop {\mathrm {card}}{\Sigma}) 下降到了 \Theta(m), 還將空間複雜度從 \Theta(m\mathop {\mathrm {card}}{\Sigma}) 下降到了 \Theta(m).

在證明 Knuth-Morris-Pratt 演算法的正確性之前, 我們首先要證明前綴函數 \pi 是正確的. 也就是對於 \pi(q), 其值必須代表著 s_{1}'s_{2}'...s_{q}' 的前綴 s_{1}'s_{2}'...s_{k}' 同時也是後綴, 同時 k 取到了最大值. 為此我們定義序列 \displaystyle {\pi^{*}(q) = \left \{ \pi(q), \pi^{(2)}(q), \pi^{(3)}(q), ..., \pi^{(t)}(q) \right \}}, 其中, \pi^{(0)}(q) = 0, 且對於任意 i > 0, \pi^{(i)}(q) = \pi \left ( \pi^{(i - 1)}(q) \right ). 當 \pi^{(t)}(q) = 0 時, 序列 \pi^{*}(q) 終止.

引理 4. 設 \pi 是子串 S' = s_{1}'s_{2}'...s_{m}' 的前綴函數, 對於 q = 1, 2, ..., m, 有 \displaystyle {\pi^{*}(q) = \left \{ k : k < q \text { 且 } s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{q}' \text { 的後綴} \right \}}.

證明 :

記 K = \left \{ k : k < q \text { 且 } s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{q}' \text { 的後綴} \right \}.

我們首先證明 \pi^{*}(q) \subseteq K, 這等同於證明對於任意 i \in \pi^{*}(q), 都有 i < q 且 s_{1}'s_{2}'...s_{i}' 是 s_{1}'s_{2}'...s_{q}' 的後綴. 若 i \in \pi^{*}(q), 則存在某個 u > 0, 使得 i = \pi^{(u)}(q). 接下來我們使用歸納法進行證明 :

1. 當 u = 1 時, i = \pi(q). 根據 \pi 的定義, 自然有 i < q 且 s_{1}' 是 s_{1}'s_{2}'...s_{q}' 的後綴;
2. 不妨假設當 u \leq k 時, 等價條件都成立;
3. 當 u = k + 1 時, i = \pi^{(u)}(q) = \pi^{(k + 1)}(q) = \pi \left ( \pi^{(k)}(q) \right ). 記 j = \pi^{(k)}(q), 代表著 j \in \pi^{*}(q), j < q 且 s_{1}'s_{2}'...s_{j}' 是 s_{1}'s_{2}'...s_{q}' 的後綴. 根據 \pi 的定義, 我們容易想到有序序列 \pi^{*} 是單調減少的, 因此 \pi \left ( \pi^{(k)}(q) \right ) < \pi^{(k)}(q), 即 i < j. 又因為 j < q, 所以 i < q. 根據 \pi 的定義, s_{1}'s_{2}'...s_{i}' 是 s_{1}'s_{2}'...s_{j}' 的後綴. 由於 s_{1}'s_{2}'...s_{j}' 是 s_{1}'s_{2}'...s_{q}' 的後綴, 所以 s_{1}'s_{2}'...s_{i}' 也是 s_{1}'s_{2}'...s_{q}' 的後綴. 最終我們可以得到等價條件在 u = k + 1 時也是成立的.

綜上所述, \pi^{*}(q) \subseteq K.

接下來我們證明 K \subseteq \pi^{*}(q). 不妨假設 K \setminus \pi^{*}(q) \neq \emptyset. 記 j = \max {K \setminus \pi^{*}(q)}. 由於有序序列 \pi^{*} 單調減少, 所以 \pi(q) 是 K 中的最大值, 同時 \pi(q) \in \pi^{*}(q), 故 j < \pi(q). 取 j' \in \pi^{*}(q), 其滿足 j' 是大小僅大於 j 的數 (不存在 j_{0} \in K 使得 j < j_{0} < j'). 若 j 已經是 \pi^{*}(q) 中第二大的數, 那麼可以取 j' = \pi(q). 因為 s_{1}'s_{2}'...s_{j}' 是 s_{1}'s_{2}'...s_{q}' 的後綴且 s_{1}'s_{2}'...s_{j'}' 也是 s_{1}'s_{2}'...s_{q}' 的後綴, 又因為 j < j', 因此 s_{1}'s_{2}'...s_{j}' 是 s_{1}'s_{2}'...s_{j'}' 的後綴. 綜合可得 \pi(j') = j, 那麼可以推導出 j' \in \pi^{*}(q) 且 j \in \pi^{*}(q). 但 j 與 j' 在集合減法中理應被排除, 與假設相互矛盾, 所以假設不成立. 最終有 K \subseteq \pi^{*}(q).

結合 \pi^{*}(q) \subseteq K 與 K \subseteq \pi^{*}(q), 我們有 \displaystyle {\pi^{*}(q) = \left \{ k : k < q \text { 且 } s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{q}' \text { 的後綴} \right \}}.

\blacksquare

引理 5. 設 \pi 是子串 S' = s_{1}'s_{2}'...s_{m}' 的前綴函數, 對於 q = 1, 2, ..., m, 若 \pi(q) > 0, 則 \displaystyle {\pi(q) - 1 \in \pi^{*}(q - 1)}.

證明 :

記 r = \pi(q), 根據 \pi 的定義可得 r < q 且 s_{1}'s_{2}'...s_{r}' 是 s_{1}'s_{2}'...s_{q}' 的後綴. 由於 \pi(q) > 0, 去掉最後一個字元, 仍然有 s_{1}'s_{2}'...s_{r - 1}' 是 s_{1}'s_{2}'...s_{q - 1}' 的後綴, 同時 r - 1 < q - 1. 根據引理 4, \pi^{*}(q - 1) = \left \{ k : k < q - 1 \text { 且 } s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{q - 1}' \text { 的後綴} \right \}, 故 r - 1 \in \pi^{*}(q - 1), 即 \pi(q) - 1 \in \pi^{*}(q - 1).

\blacksquare

為了證明在 \pi^{(i)}(q) 迭代的過程中, 若遇到 s_{1}'s_{2}'...s_{k}' 是 s_{1}'s_{2}'...s_{q - 1}' 後綴時, 當同時有 s_{1}'s_{2}'...s_{k}'s_{k + 1}' 是 s_{1}'s_{2}'...s_{q}' 的後綴, 則必然有 \pi(q) = \pi(q - 1) + 1, 我們需要引入一個 \pi^{*}(q - 1) 的子集 \displaystyle {E_{q - 1} = \left \{ k : k \in \pi^{*}(q - 1) \text { 且 } s_{1}'s_{2}'...s_{k + 1}' = s_{1}'s_{2}'...s_{q}' \right \}}. 根據引理 4, 展開 k \in \pi^{*}(q - 1) 可得 \displaystyle {E_{q - 1} = \left \{ k : k < q - 1 \wedge s_{1}'s_{2}'...s_{k}' \text { 是 } s_{1}'s_{2}'...s_{q - 1}' \text { 的後綴} \wedge s_{1}'s_{2}'...s_{k + 1}' = s_{1}'s_{2}'...s_{q - 1}'s_{q}' \right \}}. 又因為 s_{k + 1}' = s_{q}', 因此 s_{1}'s_{2}'...s_{k}'s_{k + 1}' 是 s_{1}'s_{2}'...s_{q - 1}'s_{q}' 的後綴, 我們又可以將 E_{q - 1} 寫為 \displaystyle {E_{q - 1} = \left \{ k : k < q \text { 且 } s_{1}'s_{2}'...s_{k}'s_{k + 1}' \text { 是 } s_{1}'s_{2}'...s_{q - 1}'s_{q}' \text { 的後綴} \right \}}.

推論 1. 設 \pi 是子串 S' = s_{1}'s_{2}'...s_{m}' 的前綴函數, 對於 q = 2, 3, ..., m, 有 \displaystyle {\pi(q) = \begin {cases} 0 & {E_{q - 1} = \emptyset} \\ 1 + \max {E_{q - 1}} & {E_{q - 1} \neq \emptyset}. \end {cases}}

證明 :

根據 E_{q - 1} 的定義, 當 E_{q - 1} = \emptyset 時, 不存在這樣的 k (含 k = 0), 使得 s_{1}'s_{2}'...s_{k}' 時 s_{1}'s_{2}'...s_{q}' 的後綴, 因此 \pi(q) = 0.

當 E_{q - 1} \neq \emptyset 時, 對於每一個 k \in E_{q - 1}, 都有 k + 1 < q 且 s_{1}'s_{2}'...s_{k}'s_{k + 1}' 時 s_{1}'s_{2}'...s_{q}' 的後綴. 根據 \pi 的定義, \pi(q) \geq 1 + \max {E_{q - 1}}. 注意到 \pi(q) 必然滿足 \pi(q) > 0. 設 r = \pi(q) - 1, 則 \pi(q) = r + 1 > 0. 顯然 s_{1}'s_{2}'...s_{r}'s_{r + 1}' 是 s_{1}'s_{2}'...s_{q}' 的後綴, 同時可得 s_{r + 1}' = s_{q}'. 因此 s_{1}'s_{2}'...s_{r}' 是 s_{1}'s_{2}'...s_{q}' 的後綴. 又因為 r + 1> 0, 根據引理 5, 有 \displaystyle {r = \pi(q) - 1 \in \pi^{*}(q - 1)}. 根據 E_{q - 1} 對其元素的要求, r 顯然符合, 因此 r \in E_{q - 1}, 必定同時也滿足 \displaystyle {\pi(q) - 1 = r \leq \max {E_{q - 1}}}. 變換後可得 \pi(q) \leq 1 + \max {E_{q - 1}}.

結合 \pi(q) \geq 1 + \max {E_{q - 1}} 與 \pi(q) \leq 1 + \max {E_{q - 1}}, 當 E_{q - 1} \neq \emptyset 時, \displaystyle {\pi(q) = 1 + \max {E_{q - 1}}}.

\blacksquare

仔細觀察可以發現, 推論 1 事實上就是更嚴格的斷言 1.

斷言 3. Algorithm 6 正確.

證明 :

在 Algorithm 6 中, \textbf {while} 區塊所做的事情時搜尋所有 k \in \pi^{*}(q - 1), 找到符合條件的 k, 使得 s_{k + 1} = s_{q + 1}'. 若 k 找到, 那麼 k 必定滿足 k = \max {E_{q - 1}}. 根據推論 1, \pi(q) = 1 + k. 在 \textbf {if} 區塊中, 正好將符合條件的 k 增加一, 並在下面的通用流程中將 \pi(q) 的值設定為 k. 若這樣的 k 無法找到, 那麼 \textbf {while} 區塊結束後, k 的值將會被置為零. 此時如果 s_{1}' = s_{q}', 則 \pi(q) = k + 1 = 1; 否則, \pi(q) = 0. \textbf {if} 區塊之後所做的事情僅僅是對 \pi(q) 和 q 的值進行更新. 另外, 對於任意字元 c, 必然有 \pi_{c}(1) = 1. 綜上所述, Algorithm 6 中的每一步都是正確的.

比較 Algorithm 4 和 Algorithm 5 後, 不難發現它們之間有相似之處. 只是 Algorithm 4 使用了轉移函數 \delta, 而 Algorithm 5 使用了前綴函數 \pi. Algorithm 4 已經被我們證明是正確的, 如果我們可以證明 Algorithm 5 是特別版的 Algorithm 4, 尤其是在檢測 q = m 是否成立時, 經由經由\delta 和 \pi 得到的 q 值是相同的, 那麼由 Algorithm 4 的正確性必然也可以導出 Algorithm 5 的正確性.

事實上, Algorithm 5 只是使用 \pi 替代了 Algorithm 4 中的 \delta. 回顧一下, 當基於有限狀態機的搜尋處於狀態 q 時, 接下來會讀取下一個字元 c 並將狀態轉移至 \delta(q, c). 如果 c = s_{q + 1}', 那麼 \delta(q, c) = q + 1. 在 Knuth-Morris-Pratt 演算法中, 該狀態由 c = s_{k + 1}' = s_{q + 1}' 模擬. 如果 c \neq s_{q + 1}', 基於有限狀態機的搜尋會將狀態轉移至區間 [0, q] 之內. 在 Knuth-Morris-Pratt 演算法中, 基於 \pi^{(i)} 的迭代將會使得狀態轉移到區間 [0, q) 之內. 但是當 c = s_{k + 1}' = s_{q + 1}' 成立時, 狀態應該在區間 [0, q] 之內. 因此, 從區間結果上來看, 基於有限狀態機的搜尋和 Knuth-Morris-Pratt 演算法是相同的.

斷言 4. Algorithm 5 正確.

證明 :

要想證明 Algorithm 5 是正確的, 首先要證明在每一次進入新的 \textbf {while} (第六行) 時, 迭代初始狀態 q' 滿足 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}'). 接著在本次迭代中, 只要證明初始狀態 q' 被轉移到了 q = \sigma(s_{1}s_{2}...s_{i}, s_{1}'s_{2}'...s_{m}'), 便可以通過基於有限狀態機的字串搜尋的正確性, 導出 Algorithm 5 是正確的.

對於迭代初始狀態 q', 我們使用歸納法證明其滿足 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}') :

1. 當 i = 1 時, 匹配還未開始, 此時 q' = 0. 聯立 \sigma(\emptyset, s_{1}'s_{2}'...s_{m}') = 0 可得 \displaystyle {q' = \sigma(\emptyset, s_{1}'s_{2}'...s_{m}')};
2. 不妨假設當 i \leq k 時, 都有 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}');
3. 當 i = k + 1 時, 分為兩種情況進行討論. 如果 s_{i - 1} = s_{k} = s_{q' + 1}', 那麼 q' 會被更新為 q' + 1. 而 \sigma(s_{1}s_{2}...s_{i}, s_{1}'s_{2}'...s_{m}') = q' + 1, 此時有 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}'); 如果 s_{k} \neq s_{q' + 1}', 根據 \pi 的定義和 Algorithm 5 的第七行至第九行, 不論回退多少次, 最終總會找到 s_{1}s_{2}...s_{k} 後綴與 s_{1}'s_{2}'...s_{m}' 前綴的最大匹配長度, 這正好是 \sigma(s_{1}s_{2}...s_{k}, s_{1}'s_{2}'...s_{m}') 的定義, 故此時 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}') = \sigma(s_{1}s_{2}...s_{k}, s_{1}'s_{2}'...s_{m}').

綜上所述, 對於迭代初始狀態 q', 總有 q' = \sigma(s_{1}s_{2}...s_{i - 1}, s_{1}'s_{2}'...s_{m}').

接下來我們證明當一次 \textbf {while} 迭代結束後, 有 q = \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_ {m}'). 對於已經得到的狀態 q', 接下來考慮字元 s_{i}, 其僅會對結果產生兩種影響 : 一個是 s_{i} = s_{q' + 1}', 另一個是 s_{i} \neq s_{q' + 1}'. 第二個影響會導致我們只能在 s_{1}'s_{2}'…s_{q'}' 中尋找一個前綴 (可能找不到), 使得其為 s_{1}s_{2}…s_{i} 的後綴. 於是我們可以將情況分成三種進行討論 :

1. 當 \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}') = 0 時, 我們無法在 s_{1}'s_{2}'…s_{q'}'s_{q' + 1}' 中找到任何有效前綴和 s_{1}s_{2}…s_{i} 的後綴匹配. 在 Algorithm 5 第七行至第八行中, 不論 q 如何迭代, 都無法找到一個 q \neq 0 使得 s_{i} = s_{q + 1}' 成立. 結束迭代之後, 有 q = 0. 又因爲 s_{i} \neq s_{1}', 因此 Algorithm 5 中第十一行無法成立. 最終, q = 0 = \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}');
2. 當 \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}') = q' + 1 時, 容易得到 s_{i} = s_{q' + 1}', Algorithm 5 第七行的迭代條件不會成立, 因此不會進入 \pi^{(i)} 的迭代. 此時, 上一次 \textbf {while} 迭代得到的條件 q' 值沒有發生變化. 又因爲 s_{i} = s_{q' + 1}', 因此 Algorithm 5 中第十行條件成立, q' 的值被增加一, 也就是 q = q' + 1 = \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}');
3. 當 0 < \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}') \leq q' 時, 在 Algorithm 5 第七行至第八行至少迭代一次, 使得新狀態 q 必定滿足 q < q'. 最終, 演算法可以找到一個 q 使得 s_{i} = s_{q + 1}' 成立, 狀態 q 的值被第十一行增加一. 此時, s_{1}s_{2}…s_{i} 的後綴 s_{i - q + 1}s_{i - q + 2}…s_{i} 是 s_{1}'s_{2}'…s_{q'}'s_{q' + 1}' 的前綴. 那麽有 \displaystyle {q + 1 = \sigma(s_{i - q + 1}s_{i - q + 2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}')}. 根據引理 3, 有 q + 1 = \sigma(s_{1}s_{2}…s_{i - q}s_{i - q + 1}s_{i - q + 2}…s_{i}, s_{1}'s_{2}'…s_{q'}'s_{q' + 1}').
   綜上所述, 當一次 \textbf {while} 迭代終結時, 有 q = \sigma(s_{1}s_{2}…s_{i}, s_{1}'s_{2}'…s_{m}') 成立.

結合剛進入 \textbf {while} 時的狀態和 \textbf {while} 迭代一次后的狀態, Algorithm 5 模擬了 Algorithm 4 的操作. 由 Algorithm 4 的正確性可以導出 Algorithm 5 正確.
我們可以根據 Algorithm 5 和 Algorithm 6 的正確性, 推導出 Knuth-Morris-Pratt 演算法是正確的.

\blacksquare

2.2.4 Rabin-Karp 演算法

上面三個演算法都是較爲通用的演算法, 字串中可以包含任意字元. 然而有一部分字串比較特殊, 其可能只包含十進製數字, 即 \Sigma = \left \{ 0, 1, 2, …, 9 \right \}. 在更一般的情況下, 我們可以將數字表示爲 d 進位的表達式, 其中 d = \mathop {\mathrm {card}} {\Sigma}. 在目前的電腦體系結構下, 在討論演算法時我們通常將數字的比較視爲 \Theta(1) 的操作, 於是我們可以運用數字這個特性來討論只針對數字字串的字串搜尋演算法.

設有字串 S = s_{1}s_{2}…s_{n} 與 S' = s_{1}'s_{2}'…s_{m}', 其中 s_{i} \in \Sigma_{N}, s_{j}' \in \Sigma, i = 1, 2, …, n, j = 1, 2, …, m. 我們用 \gamma 表示 S' 的十進位數字, 用 \alpha_{t} 表示 S 的字串 s_{t + 1}s_{t + 2}…s_{t + m} 的十進位數字. 其中, t = 0, 1, 2, …, n - m. 若 S' 在 S 中的起始位置為 t, 那麽自然有 \displaystyle {\gamma = \alpha_{t}}. 對於所有已知的 \alpha_{t}, 我們在 \Theta(n - m + 1) 的時間内就可以知道 S' 是否出現在 S 中.

任意十進位數字 N 都可以表示爲 \displaystyle {N = \sum \limits_{i = 0}^{k} 10^{i}a_{i + 1}}. 其中, k 是 N 的數字位數, a_{i + 1} 表示對應位數的具體數值, 0 \leq a_{i + 1} \leq 9. 那麽, 我們可以將 S' 的數字形式 \gamma 表示爲 \displaystyle {\gamma = s_{m}' + 10 \cdot (s_{m - 1}' + 10 \cdot (s_{m - 2}' + …))}. 這樣, 我們在 \Theta(m) 的時間内將 S' 轉變成了其數字形式 \gamma.

對於被搜尋的字串 S, 一開始必須按照計算 \gamma 那樣計算 \alpha_{0} 的值. 對於 \alpha_{1}, \alpha_{2}, … 的值, 我們按需計算即可, 每次去掉最高位並加入最低位 : \displaystyle {\alpha_{i + 1} = 10 \left ( \alpha_{i} - 10^{m - 1}s_{i + 1} \right ) + s_{i + m + 1}}. 這樣, 至多比較 n - m + 1 次, 便可得到 S' 是否出現在 S 中. 我們稱這樣的演算法為 Rabin-Karp 演算法. 容易地, 我們知道 Rabin-Karp 演算法的時間複雜度為 \Theta(n - m + 1) = \Theta(n) - O(n) = \Theta(n), 空間複雜度為 \Theta(1).

上面的時間複雜度其實是基於一個假設 : 即數字之間的比較被我們視爲 \Theta(1) 的. 現在讓我們來考慮另一種情況, 當 n 和 m 的長度非常大的時候, 這個假設就不再合理了. 幸運的是, 我們可以透過選取一個模 q 來解決這個問題. 對於字串 S, 我們可以逐個計算 \displaystyle {\alpha_{0}' = \alpha_{0} \mod q, \alpha_{1}' = \alpha_{1} \mod q, \alpha_{2}' = \alpha_{2} \mod q, …, \alpha_{n - m}' = \alpha_{n - m} \mod q}. 接著計算 \gamma' = \gamma \mod q. 只要 \alpha_{i}' \neq \gamma', 我們就可以判定 \alpha_{i} \neq \gamma. 但是若 \alpha_{i}' = \gamma', 我們還無法直接確定 \alpha_{i} = \gamma. 因爲能夠使得 x \mod q = \alpha_{i}' 的 x 有無數個, 可能這樣的 x 大量出現在 S 中. 因此, 當 \alpha_{i}' = \gamma' 時, 我們必須逐個字元比較 s_{i + 1}s_{i + 2}…s_{i + m} 與 s_{1}'s_{2}'…s_{m}' 確認全等后, 才能最終得出 S' 出現在 S 中. 其中, i = 0, 1, 2, …, n - m.
在 m 和 n 非常大的時候, 我們需要計算 n - m 個 \alpha_{i} \mod q, 還要將這些計算結果儲存下來. 另外, 在最壞的情況下, 所有 \alpha_{i}' = \gamma' 都成立, 那麽我們還需要進行 m 次字元比較. 最終我們可以得到, 數字極大情況下的 Rabin-Karp 演算法的時間複雜度為 \Theta(m(n - m + 1)) (由於 m = O(n), 最終可以寫爲 \Theta(n^{2})), 空間複雜度為 \Theta(m). 其中, i = 0, 1, 2, …, n - m.

對於 q 的選取, 應該盡量是一個素數, 可以的話盡量滿足 10q 恰好是一個字組大小, 這樣僅用單精度算術運算便可以完成所有必須的運算. 一般情況下, 對於 d 進位的 \Sigma = \left \{ 0, 1, 2, …, d - 1 \right \}, 可以從中選取一個 q, 使得 dq 在一個字組長度之内. \alpha_{i} 和 \alpha_{i + 1} 的關係就變成了 \displaystyle {\alpha_{i + 1} = d \left ( \alpha_{i} - s_{i + 1}(d^{m - 1} \mod q) \right ) + s_{i + m + 1} \mod q}.

2.3 近似匹配

設有字串 X 和 Y, 給定距離函數 D 和閾值 \delta, 若有 \displaystyle {D(X, Y) \leq \delta}, 那麽我們稱字串 X 和 Y 近似匹配 (approximately matched). 字串的近似匹配問題也是字串中的一個熱門問題, 結合子串, 可以衍生出在 X 中尋找某一子串 X_{0}, 使得其與 Y 近似匹配.

一般來説, 應用於陣列的距離函數同樣可以應用於字串. 但是對於字串來説, 我們更傾向於使用編輯距離 (edit distance), 即一個字串需要經過多少次處理才能轉換爲另一個字串. 字串的處理方式包括 :

1. 向字串中的某個位置加入一個字元
2. 移除字串中某個位置上的字元
3. 用另一字元替換掉字串上某個位置中的字元
4. 交換字串中任意兩個位置的字元
   對於第三種處理方式, 更嚴格地, 如果我們只允許交換相鄰字元, 那麽這種處理方式被稱爲字元轉置 (character transposition).

2.3.1 Hamming 距離

若 \mathop {\mathrm {card}} {X} = \mathop {\mathrm {card}} {Y}, 那麼我們只需要替換字元便可以使得 X = Y. 若字串 X 透過替換 k 次字元就成了 Y, 那麼我們稱 k 為 X 與 Y 之間的 Hamming 距離.

2.3.2 Lee 距離

設影射 f 的值域 R_{f} = \left \{ 0, 1, 2, ..., q - 1 \right \}. 其中, q \geq 2. f(c) 能夠將字元 c 影射到 R_{f} 中的某個數值上. 對於字串 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{n}, 我們稱 \displaystyle {D_{\text {Lee}}(X, Y) = \sum \limits_{i = 1}^{n} \min \left \{ |f(x_{i}) - f(y_{i})|, q - |f(x_{i}) - f(y_{i})| \right \}} 為字串 X 與 Y 的 Lee 距離.

在 Lee 距離下, 若 q = 2, 則 R_{f} = \left \{ 0, 1 \right \}. 當 x_{i} = y_{i} 時, f(x_{i}) - f(y_{i}) = 0. 此時, 第 i 個字元不影響 D_{\text {Lee}} 的值. 如果 x_{i} \neq y_{i}, 那麼可能有 f(x_{i}) \neq f(y_{i}) (注意 f(x_{i}) = f(y_{i}) 的情況等同於 x_{i} = y_{i}). 由於 R_{f} 中只有兩個可以取到的值, 所以 \displaystyle {|f(x_{i}) - f(y_{i})| = q - |f(x_{i}) - f(y_{i})| = 1}. 若 f 滿足在 x_{i} \neq y_{i} 下必定有 f(x_{i}) \neq f(y_{i}), 此時 Lee 距離將退化為 Hamming 距離.

另外, 當 q = 3 時, R_{f} = \left \{ 0, 1, 2 \right \}. x_{i} = y_{i} 的情況和 q = 2 時相同. 當 x_{i} \neq y_{i} 且 f 滿足在 x_{i} \neq y_{i} 下必定有 f(x_{i}) \neq f(y_{i}) 時,

• 若 f(x_{i}) = 2 且 f(y_{i}) = 1, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 1, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1;}
• 若 f(x_{i}) = 2 且 f(y_{i}) = 0, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 2, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1;}
• 若 f(x_{i}) = 1 且 f(y_{i}) = 2, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 1, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1;}
• 若 f(x_{i}) = 1 且 f(y_{i}) = 0, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 1, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1;}
• 若 f(x_{i}) = 0 且 f(y_{i}) = 2, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 2, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1;}
• 若 f(x_{i}) = 0 且 f(y_{i}) = 1, 則 \displaystyle {|f(x_{i}) - f(y_{i})| = 1, q - |f(x_{i}) - f(y_{i})| = 1 \Rightarrow D_{\text {Lee}}(x_{i}, y_{i}) = 1.}

綜合來說, 當 q = 3 時仍然有 \displaystyle {D_{\text {Lee}} = \begin {cases} 0 & {x_{i} = y_{i}} \\ 1 & {x_{i} \neq y_{i}}. \end {cases}} 那麼 q = 3 時, Lee 距離依然退化為 Hamming 距離.

2.3.3 Levenshtein 距離

Levenshtein 距離採用了除交換之外的所有操作. 若有字串 X = x_{1}x_{2}…x_{n} 和 Y = y_{1} y_{2}…y_{m}, 則 X 和 Y 的 Levenshtein 距離定義爲 \displaystyle {D_{\text {Levenshtein}}(X, Y) = \begin {cases} n & {n \neq 0 \wedge m = 0} \\ m & {n = 0 \wedge m \neq 0} \\ 0 & {n = 0 \wedge n = 0} \\ D_{\text {Levenshtein}}(x_{2}x_{3}…x_{n}, y_{1}y_{2}…y_{m}) & {x_{1} = y_{2}} \\ 1 + \min {\begin {cases} D_{\text {Levenshtein}}(x_{2}x_{3}…x_{n}, y_{1}y_{2}…y_{m}) \\ D_{\text {Levenshtein}}(x_{1}x_{2}…x_{n}, y_{2}y_{3}…y_{m}) \\ D_{\text {Levenshtein}}(x_{1}x_{2}…x_{n}, y_{1}y_{2}…y_{m}) \end {cases}} & {\text {else}}. \end {cases}} 當 \mathop {\mathrm {card}} {X} 或者 \mathop {\mathrm {card}} {Y} 都爲零時, 要想使得兩個字串完全匹配, 那麽逐個加入另一個字串的字元便可以讓兩個字串等價. 對於 x_{1} = y_{1} 的情形, 無需進行任何處理, 所以 \displaystyle {D_{\text {Levenshtein}}(x_{1}, y_{1}) = 0}. 對於剩餘情況, Levenshtein 距離遞迴地計算子串的 Levenshtein 距離 :

• D_{\text {Levenshtein}}(x_{2}x_{3}…x_{n}, y_{1}y_{2}…y_{m}) 表示的是要從 x_{1}x_{2}…x_{n} 中移除 x_{1};
• D_{\text {Levenshtein}}(x_{1}x_{2}…x_{n}, y_{2}y_{3}…y_{m}) 表示的是要從 y_{1}y_{2}…y_{m} 中移除 y_{1};
• D_{\text {Levenshtein}}(x_{1}x_{2}…x_{n}, y_{1}y_{2}…y_{m}) 表示 x_{1} 雖然和 y_{1} 不相等, 但是透過替換可以達到等價的目的.

在遞迴的過程中, D_{\text {Levenshtein}} 會不斷去計算 x_{2}x_{3}…x_{n}, x_{3}x_{4}…x_{n}, …, x_{n} 和 y_{1}y_{2}…y_{m} 的 Levenshtein 距離. 因此時間複雜度為 \Theta(n \times m). 爲了方便之後的計算, 我們需要將每一次計算得到的狀態結果儲存下來, 這樣空間複雜度也爲 \Theta(n \times m).

2.3.4 Damerau-Levenshtein 距離

在日常鍵入文本的過程中, 左右字元不小心交換的場景時有出現. 例如我想要鍵入 first, 但是因爲我打字速度過快變成了 frist. Damerau 曾經調查過, 80% 的鍵入錯誤源於左右交換, 因此擴展了 Levenshtein 距離, 將字元轉置納入了考慮範圍, 便有了 Damerau-Levenshtein 距離. 對於字串 X = x_{1}x_{2}…x_{n} 和 Y = y_{1}y_{2}…y_{m}, 其 Damerau-Levenshtein 距離定義爲 \displaystyle {\mathop {\mathrm {DL}}(X, Y) = \begin {cases} 0 & {n = 0 \wedge m = 0} \\ \mathop {\mathrm {DL}}(x_{2}x_{3}...x_{n}, Y) + 1 & {n \neq 0 \wedge m = 0} \\ \mathop {\mathrm {DL}}(X, y_{2}y_{3}...y_{m}) + 1 & {n = 0 \wedge m \neq 0} \\ \mathop {\mathrm {DL}}(x_{3}x_{4}...x_{n}, y_{3}y_{4}...y_{m}) + \ell(x_{1}, y_{1}) & {\left \{ \begin {aligned} &n > 1 \wedge m > 1 \wedge \\ &x_{1} = y_{2} \wedge x_{2} = y_{1} \end {aligned} \right \}} \\ \mathop {\mathrm {DL}}(x_{2}x_{3}...x_{n}, y_{2}y_{3}...y_{m}) + \ell(x_{1}, y_{1}) & {\text {else.}} \end {cases}} 其中, \ell(x_{1}, y_{1}) = \begin {cases} 1 & {x_{1} \neq y_{1}} \\ 0 & {x_{1} = y_{1}}. \end {cases}

在距離的定義表達式中, 想要將字串從 X 變成 Y :

• \mathop {\mathrm {DL}}(x_{2}x_{3}...x_{n}, Y) + 1 表示從 X 中刪除一個字元;
• \mathop {\mathrm {DL}}(X, y_{2}y_{3}...y_{m}) + 1 表示向 X 中插入一個字元;
• \mathop {\mathrm {DL}}(x_{3}x_{4}...x_{n}, y_{3}y_{4}...y_{m}) + \ell(x_{1}, y_{1}) 表示在 x_{1} = y_{1} 的情況下, \mathop {\mathrm {DL}}(X, Y) = \mathop {\mathrm {DL}}(x_{3}x_{4}...x_{n}, y_{3}y_{4}...y_{m}); 否則, 表示 x_{2}x_{1} = y_{1}y_{2}, 即交換相鄰字元;
• \mathop {\mathrm {DL}}(x_{2}x_{3}...x_{n}, y_{2}y_{3}...y_{m}) + \ell(x_{1}, y_{1}) 表示在 x_{1} = y_{1} 的情況下, \mathop {\mathrm {DL}}(X, Y) = \mathop {\mathrm {DL}}(x_{3}x_{4}...x_{n}, y_{3}y_{4}...y_{m}); 否則, 表示透過替換 x_{1} 為 y_{1}.

2.3.5 Jaro-Winkler 距離

給定兩個字串 X 和 Y, 其 Jaro 相似度定義為 \displaystyle {J(X, Y) = \frac {1}{3} \left ( \frac {m}{\mathop {\mathrm {card}} {X}} + \frac {m}{\mathop {\mathrm {card}} {Y}} + \frac {m - t}{m} \right )}. 其中, m 是近似匹配數量, t 是字元轉置的次數除以二. Jaro 相似度中的近似匹配主要是指對於 x_{i}, 它會和 Y_{d} = \left \{ y_{i - d}, y_{i - d + 1}, ..., y_{i}, y_{i + 1}, y_{i + 2}, ..., y_{i + d} \right \} 中的元素進行匹配, 若 x_{i} \in Y_{d}, 那麽 m 的值增加一. 其中, d = \left \lfloor \frac {\max \left \{\mathop {\mathrm {card}} {X}, \mathop {\mathrm {card}} {Y} \right \}}{2} \right \rfloor - 1. 其中, i = 1, 2, ..., \mathop {\mathrm {card}} {X}. 換句話説, m 值的含義是對於任意 x_{i}, 所謂的近似匹配不要求嚴格的 x_{i} = y_{i} (如果能夠成立當然最好), 只需要在 y_{i} 的指定距離之内找到 x_{i} 我們就可以認爲匹配. t 值是基於 m 值計算的. 對於 x_{i} 而言, 若 x_{i} \in Y_{d} 且 x_{i} \neq y_{i} 時, 若有 x_{i} = y_{i - 1} 或者 x_{i} = y_{i + 2}, 那麽 t 值增加一. 注意 t 值計算完成后, 還要除以二才能應用到 Jaro 相似度當中.

Jaro-Winkler 相似度在 Jaro 相似度的基礎上, 引入共同前綴的權重提升來調整相似度分數 : \displaystyle {\mathop {\mathrm {JW}}(X, Y) = J(X, Y) + p\ell(X, Y) \cdot (1 - J(X, Y))}. 其中, J(X, Y) 是 Jaro 相似度, \ell(X, Y) 是 X 和 Y 的前綴匹配長度 (最大值限定於 4), p 是前綴權重參數, 通常取 0.1. Jaro-Winkler 相似度一般用於人名和地名的相似匹配, 所以它比較注重前綴的匹配程度.

Jaro-Winkler 距離基於 Jaro-Winkler 相似度定義為 \displaystyle {D_{\text {Jaro-Winkler}}(X, Y) = 1 - \mathop {\mathrm {JW}}(X, Y)}.

2.3.6 最長公共子序列

定義 6. 設有字串 X = x_{1}x_{2}...x_{n}, 若有嚴格單調增加序列 \displaystyle {i_{1}, i_{2}, ..., i_{k}} 使得對於字串 Z = z_{i_{1}}z_{i_{2}}...z_{i_{k}} 中的任意字串 z_{i_{j}} 都有 z_{i_{j}} \in X 且 i_{j} \leq n, 那麼我們稱字串 Z 是 X 的子序列 (subsequence).

透過子序列的定義我們知道, Z 中字元的組成實際上就是從 X 中隨機剃除掉一些不需要的字元. 例如 123456789 中剔除掉偶數變成了 13579, 那麼 13579 就是 123456789 的子序列. 需要注意的是, 根據 \displaystyle {i_{1}, i_{2}, ..., i_{k}} 的嚴格單調增加和 i_{j} \leq n, 子序列中的字元前後順序是不能改變的, 而且所有字元必須來源於原字串, 不能新增任何新的字元. 比如 31579 和 315799 就不是 123456789 的子序列.

定義 7. 若 Z = z_{i_{1}}z_{i_{2}}...z_{i_{k}} 同時為字串 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{m} 的子序列, 那麼我們稱 Z 是 X 與 Y 的公共子序列 (common subsequence).

定義 8. 如果 Z 是 X 和 Y 的公共子序列, 對於嚴格單調增加序列 \displaystyle {i_{1}, i_{2}, ..., i_{k}, i_{k + 1}} 使得字串 Z' = z_{i_{1}}'z_{i_{2}}'...z_{i_{k}}'z_{i_{k + 1}}' 中存在某個 z_{j}' 滿足 z_{j}' \notin X 或者 z_{j}' \notin Y, 那麼我們稱 Z 是 X 和 Y 的最長公共子序列 (longest common subsequence). 其中, j = 1, 2, ..., k, k + 1.

值得提到的是, 最長公共子序列並不一定是唯一的. 例如 BCAB 是 BCBDAB 和 BDCAB 的最長公共子序列, BDAB 也是最長公共子序列. 為了尋找兩個字串之間的最長公共子序列是一個非常經典的問題, 例如我們要在 DNA 中尋找最長公共子序列, 看看兩個生物相似度如何; 又例如我們要在文章中尋找若干個最長公共子序列, 看看兩篇文章是否類似.

為了確定兩個字串的最長公共子序列, 我們可以列舉兩個字串所有可能的子序列, 然後逐個對比留下匹配的, 最後從匹配子序列中選擇長度最大的. 但這種方法的時間複雜度和空間複雜度都是指數級別的.

定理 2. 若字串 Z = z_{1}z_{2}...z_{k} 是 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{m} 的最長公共子序列,

• 如果 x_{m} = y_{n}, 那麼 z_{k} = x_{n} = y_{m} 且 Z_{k - 1} 是 X_{n - 1} 和 Y_{n - 1} 的最長公共子序列;
• 如果 x_{n} \neq y_{m}, 那麼 z_{k} \neq x_{n} 意味著 Z 是 X_{n - 1} 和 Y 的最長公共子序列;
• 如果 x_{n} \neq y_{m}, 那麼 z_{k} \neq y_{m} 意味著 Z 是 X 和 Y_{m - 1} 的最長公共子序列.

證明 :

令 X_{i} 和 Y_{j} 分別表示前綴 x_{1}x_{2}...x_{i} 和 y_{1}y_{2}...y_{j}. 其中, i = 1, 2, ..., n, j = 1, 2, ..., m.

在第一項中, 如果 z_{k} \neq x_{n}, 那麼可以將 x_{n} = y_{m} 追加到 Z 的末尾, 這樣就得到了一個長度為 k + 1 的 X 和 Y 的最長公共子序列. 這和假設是矛盾的, 那麼必然有 z_{k} = x_{n} = y_{m}. 另一方面, 如果存在一個長度大於 k - 1 的字串 Z' 使得其為 X_{n - 1} 和 Y_{m - 1} 的最長公共子序列, 那麼把 x_{n} 追加到 Z' 之後, Z' 將成為 X 和 Y 的最長公共子序列. 但是 Z' 的長度又大於 k, 又和假設矛盾. 因此 Z_{k - 1} 是 X_{n - 1} 和 Y_{m - 1} 的最長公共子序列.

第二項和第三項的情況是對稱的, 只要證明某一項正確, 交換 X 和 Y, 便可以得到另一項也正確. 我們選擇第二項來證明. 如果 z_{k} \neq x_{n} 且存在 X_{n - 1} 和 Y 的一個長度大於 k 的公共子序列 Z', 那麼 Z' 也必定是 X 和 Y 的公共子序列. 這和假設中 X_{n - 1} 和 Y 的最長公共子序列長度為 k 不相符, 存在矛盾. 因此第二項成立, 第三項也成立.

\blacksquare

定理 2 告訴我們, 兩個字串的最長公共子序列, 其子序列必然包含著兩個字串的子串的最長公共子序列. 所以我們可以拆分問題, 先求出子串的最長公共子序列, 逐漸增加字元後便可以得到原始字串之間的最長公共子序列. 顯然, 在求解原問題的時候, 需要將問題拆分成子問題, 子問題的解影響到了最終解. 最終解要求的最長長度也必定決定著子問題的解也必然取得最長長度. 換句話說, 子問題能否取得最佳解決定了最終解能否取得最佳解, 這非常適合使用動態規劃 (《動態規劃演算法》).

根據定理 2, 若要求 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{m} 的最長公共子序列, 在 x_{n} = y_{m} 的情況下, 我們只需要在 X_{n - 1} 和 Y_{m - 1} 的最長公共子序列最後把 x_{n} 加上即可; 在 x_{n} \neq y_{m} 的情況下, 我們需要求 X_{n - 1} 和 Y 的最長公共子序列以及 X 和 Y_{m - 1} 的最長公共子序列, 然後選擇那個較長的作為最終結果. 這樣, 我們就很容易寫出動態規劃遞迴方程式 : \displaystyle {\mathop {\mathrm {LCS}}(X, Y) = \begin {cases} 0 & {n = 0 \vee m = 0} \\ \mathop {\mathrm {LCS}}(X_{n - 1}, Y_{m - 1}) + \left \{ x_{n} \right \} & {n \neq 0 \wedge m \neq 0 \wedge x_{n} = y_{m}} \\ \argmax \left \{ \mathop {\mathrm {LCS}}(X_{n - 1}, Y), \mathop {\mathrm {LCS}}(X, Y_{m - 1}) \right \} & {\text {else}}. \end {cases}}

如果我們嚴格依據動態規劃遞迴方程式去計算最長公共子序列, 那麼時間複雜度必然是指數級別的. 重新考慮子問題的數量, 我們會求 X_{1}, X_{2}, ..., X_{n} 和 Y_{1} 的最長公共子序列, 這裡有 n 次計算; 而 Y 的長度為 m, 因此總共需要計算 n \times m 次. 根據這個思想, 我們可以構造一個 n \times m 大小的矩陣, 矩陣中的每個元素記錄著到目前為止最長公共子序列的長度.

例題 3. 構造字串 ABCBDAB 和 BDCABA 的最長公共子序列狀態矩陣.

解 :

\blacksquare

但是狀態矩陣中儲存的僅僅是最長公共子序列的長度, 我們還無法直接從狀態矩陣推導出最長公共子序列. 根據定理 2 我們知道, 當 x_{i} = y_{j} 的時候, 一定會向結果序列中加入字元. 那麼根據這個狀態, 我們可以為狀態矩陣中滿足 x_{i} = y_{j} 狀態的位置進行特殊標記.

矩陣右下角的長度一定是最大的, 所以我們從右下角開始尋找, 首先判斷這個位置是否存在特殊標記,

• 若存在, 則說明 x_{n} = y_{m}, 根據定理 2, 理應將 x_{n} 放入結果序列當中. 接下來 \mathop {\mathrm {LCS}}(X_{n - 1}, Y) 和 \mathop {\mathrm {LCS}}(X, Y_{m - 1}) 已經沒有意義了, 因為這兩個分支不會被動態規劃遞迴方程式選中. 所以此時我們定位到 \mathop {\mathrm {LCS}}(X_{n - 1}, Y_{m - 1}) 上, 也就是狀態矩陣中第 n - 1 行第 m - 1 列這個位置;
• 若不存在, 則說明 x_{n} \neq y_{m}, 這兩個字元都不能放入結果序列當中. 接著我們要依賴於 \mathop {\mathrm {LCS}}(X_{n - 1}, Y) 與 \mathop {\mathrm {LCS}}(X, Y_{m - 1}), 定位到值更大的位置. 例如 \mathop {\mathrm {LCS}}(X_{n - 1}, Y) > \mathop {\mathrm {LCS}}(X, Y_{m - 1}), 那麼定位到狀態矩陣第 n - 1 行第 m 列這個位置. 但如果 \mathop {\mathrm {LCS}}(X_{n - 1}, Y) = \mathop {\mathrm {LCS}}(X, Y_{m - 1}), 那麼我們就要分成兩條路徑求解 : 第 n - 1 行第 m 列和第 n 行第 m - 1 列這兩個位置. 但是如果其中一個位置進行了特殊標記, 另一個位置沒有, 那麼我們可以排除那個沒有特殊標記的位置. 如果兩個位置都有特殊標記或者兩個位置都沒有特殊標記, 我們就要對兩個位置分別求解.

定位更新之後, 重複進行上述操作, 直到某個第 i 行第 j 列這個位置滿足 \mathop {\mathrm {LCS}}(X_{i}, Y_{j}) = 1 且 x_{i} = y_{j} 為止 (也就是這個位置同時還被特殊標記). 這個路徑上的標記位置對應的字元按順序排列後便是 X 和 Y 的最長公共子序列. 當然還有另一種情況, 在尋找時遇到了長度為零的位置, 這個時候可以立即終止當前路徑上的計算. 其中, i = 1, 2, ..., n, j = 1, 2, ..., m.

根據上面的討論, 我們可以很容易寫出根據狀態矩陣尋找最長公共子序列的方程式 : \displaystyle {\mathop {\mathrm {L}} \left ( (M_{ij})_{n \times m} \right ) = \begin {cases} \emptyset & {m = 0 \vee n = 0 \vee M_{nm} = 0} \\ \mathop {\mathrm {L}} \left ( (M_{ij})_{(n - 1)(m - 1)} \right ) \bigcup \left \{ M_{ij}^{*} \right \} & {M_{ij} \text { is specially marked}} \\ \mathop {\mathrm {L}} \left ( (M_{ij})_{(n - 1)m} \right ) & {M_{(n - 1)m} > M_{n(m - 1)}} \\ \mathop {\mathrm {L}} \left ( (M_{ij})_{n(m - 1)} \right ) & {M_{(n - 1)m} < M_{n(m - 1)}} \\ \argmax \limits_{\mathop {\mathrm {card}}{\mathop {\mathrm {L}}}} \left \{ \begin {aligned} &\mathop {\mathrm {L}} \left ( (M_{ij})_{n(m - 1)} \right ), \\ &\mathop {\mathrm {L}} \left ( (M_{ij})_{(n - 1)m} \right ) \end {aligned} \right \} & {M_{(n - 1)m} = M_{m(n - 1)}}. \end {cases}} 其中, M_{ij}^{*} 表示字元 x_{i} = y_{j}.

在求解的過程中, 我們可以標記一下定位的狀態. 如果某個定位已經被求解過了, 那麼下次再遇到的時候, 就可以直接停止當前路徑的求解. 所有可行路徑 (Figure 20 中為最終箭頭藍色的路徑) 上帶有標記的定位點對應的字元按順序逐個取出, 便可以得到 ABCBDAB 和 BDCABA 的所有最長公共子序列 : BDAB 和 BCBA.

要構造一個狀態矩陣, 至多需要 \Theta(mn) 的時間. 求解路徑的構造至多也需要 \Theta(mn) 的時間, 因為一個路徑中, 一行或者一列至多尋訪一個定位點. 這樣, 最長公共子序列問題的求解時間複雜度為 \Theta(mn). 由於我們需要儲存狀態矩陣, 所以空間複雜度也為 \Theta(mn).

有時候, 我們可能僅需要得到任意一個最長公共子序列即可. 仔細分析定理 2, 我們可以發現求解路徑上某個定位點 \left \langle i, j \right \rangle 的接下來求解路徑只與 \left \langle i - 1, j \right \rangle, \left \langle i, j - 1 \right \rangle 還有 \left \langle i - 1, j - 1 \right \rangle 有關. 其中, i = 1, 2, …, n, j = 1, 2, …, m. 那麼狀態矩陣只需要保持其中兩行兩列實時更新即可, 剩下的狀態都可以在用完之後拋棄掉. 這樣可以再減少一些空間複雜度, 但是不會改變漸進意義上的空間複雜度.