西灣筆記

這篇筆記、翻譯自博文：Fast String Searching With Suffix Trees，作者Mark Nelson。尊重他人勞動果實，轉載請註明！

I think that I shall never see
A poem lovely as a tree.
Poems are made by fools like me,
But only God can make a tree.

–Joyce Kilmer

A tree’s a tree. How many more do you need to look at?

–Ronald Reagan-

字串序列匹配是電腦程式設計師經常需要面對的問題。一些編程任務，例如數據壓縮或DNA測序，可以從字串匹配演算法的改進中獲益匪淺。本文探討了一種相對未知的數據結構，即後綴樹，並展示如何使用它的特性着手解决字串匹配的難題。

問題的提出

想像一下，你剛剛被聘為一名DNA測序項目的程式設計師。研究人員正在忙著分切病毒遺傳物質，產生碎片化的核苷酸序列。他們將這些序列發送到你的伺服器，期望將序列在基因組數據庫中定位。給定病毒的基因組可能有成千上萬個核苷酸鹼基，數據庫中有數百種病毒。你需要實作客戶端/伺服器系統，以提供實時反饋給等不及的博士們。什麼才是最好的方法呢？

顯而易見，暴力字串搜尋將非常低效。這種搜尋需要對數據庫中每個基因組的每個核苷酸進行字串比較。測試部分匹配命中率很高的長片段將使你的客戶端/伺服器系統看起來像中古批處理機。你面臨的挑戰是提出一種高效的字串匹配解決方案。

直觀的解決方案

由於要測試的數據庫是不變的，因此對它預處理以簡化搜尋似乎是一個好主意。一種預處理的方法是構建搜尋字典樹。對於搜尋輸入文本，構建搜尋字典樹的直觀方法產生了一種稱為後綴字典樹的東西。（後綴字典樹距離我的最終標的，即後綴樹，只有一步之遙。）字典樹是一種樹，每個節點有N個可能的分支，其中N是字母表中的字符數。使用「後綴」一詞來指代這樣的情形：字典樹包含給定文本塊（可能是病毒基因組）的所有後綴。

第二點成就了後綴字典樹這麼好的結構。如果有一個長度為N的輸入文本和一個長度為M的搜尋字串，則一次傳統的暴力搜尋需要完成N*M次字符比較。最佳化的搜尋技術，例如Boyer-Moore演算法，可以保證搜尋不超過M+N次比較，並具有更好的平均性能。但後綴字典樹完全超越了這種性能：僅需M次字符比較，無論待搜尋文本的長度如何！

這可能看起來很不錯，意味著我可以通過執行區區七次字符比較來確定BANANAS這個詞是否在威廉·莎士比亞的作品集中！當然，只有一個小問題：構建字典樹所需的時間。

你不怎麼聽到後綴字典樹應用的原因是基於一個簡單的事實，即構建一個需要O(N²)的時間和空間。這種平方階性能使之無法用在最需要使用後綴字典樹的場合：搜尋長數據塊。

在後綴樹蔭下

1976年，Edward McCreight提出了一個合理的方法來解決這個困境。他發表了一篇論文來闡述後綴樹。給定數據塊的後綴樹保留與後綴字典樹相同的拓撲，但它消除了只有一個後代的節點。這個過程稱為路徑壓縮，意味著樹中的各個邊現在可以表示文本序列而不是單個字符。

圖2顯示了圖1的後綴字典樹轉換為後綴樹的樣子。你可以看到樹仍然具有相同的一般形狀，只是擁有更少的節點。通過消除所有的僅有單個後代的節點，計數從23減少到11。

實際上，節點數量的減少使得構造後綴樹的時間和空間要求從O(N²)減少到O(N)。在最壞的情況下，構建後綴樹最多需要2N個節點，其中N是輸入文本的長度。因此，只需與輸入文本長度成比例的一次性投資，我們就可以創建一個用於增強字串搜尋的樹。

即使你可以做一棵樹

構造後綴樹的原始McCreight演算法有一些缺點。其中的一項原則是要求樹以相反的順序構建，這意味著字符從輸入末端開始添加。這使得在線處理成為不可能，使得它更難以用於數據壓縮等應用程式。

二十年後，來自赫爾辛基大學的Esko Ukkonen打破了窘境。他稍微修改了演算法，使其從左向右運作。我的示例代碼和後面的描述均基於Ukkonen的學術論文，該論文發表在1995年9月的Algorithmica雜誌上。

對於給定的文本字串，T，Ukkonen的演算法以空樹開始，然後逐步將T的N個前綴逐個添加到後綴樹中。例如，在為BANANAS創建後綴樹時，將B插入樹中，然後插入BA，然後插入BAN，依此類推。最後插入BANANAS時，樹已完成。

後綴樹運作方式

向樹中添加新前綴是通過遍歷樹並訪問當前樹的每個後綴來完成的。我們從最長的後綴（圖3中的BAN）開始，然後向下遍歷到最短的後綴，即空字串。每個後綴都以這三種類型中的一種節點結束：

1. 葉節點。在圖4中，標記為1，2，4和5的節點是葉節點。
2. 顯式節點。在圖4中，標記為0和3的非葉節點是顯式節點。它們代表樹上的一個點，其上兩條或兩條以上的邊分開。
3. 隱式節點。在圖4中，諸如BO，BOO和OO之類的前綴都在邊的中間結束。這些位置稱為隱式節點。它們代表後綴字典樹中的節點，但路徑壓縮消除了它們。在構建樹時，隱式節點有時會轉換為顯式節點。
   

在圖4中，在將BOOK添加進來之後，樹中有五個後綴（包括空字串）。將下一個前綴BOOKK添加到樹中意味著訪問現有樹中的每個後綴，並在後綴的末尾添加字母K。

前四個後綴BOOK，OOK，OK和K都以葉節點結束。由於後綴樹使用了路徑壓縮，向葉節點添加新字符將始終只添加到該節點上的字串。它不會為新添加的字母創建新節點。

在更新了所有葉節點之後，我們仍然需要在空字串中添加字符「K」，該字串在節點0處找到。由於已經有一條以字母K開頭的離開節點0的邊，我們不需要做任何事情。新添加的後綴K將在節點0處找到，並且將在隱式節點處（沿著此處通向節點2的邊向下有一個字符）結束。

結果樹的最終形狀如圖5所示。

事情變得棘手了

更新圖4中的樹相對容易。我們執行了兩種類型的更新：第一種只是邊的擴充，第二種是隱式更新，不做任何事情。將BOOKKE添加到圖5中所示的樹將演示另外兩種類型的更新。第一種類型，創建一個新節點以在隱式節點處拆分現有邊，然後添加新邊。第二種類型，向顯式節點添加新邊。

當將BOOKKE添加到圖5中的樹時，我們再次以最長的後綴BOOKK開始，並遍歷到最短的空字串。只要我們更新葉節點，更新較長的後綴還是很容易的。在圖5中，以葉節點結尾的後綴是BOOKK，OOKK，OKK和KK。圖6中的第一個樹顯示了使用簡單字串擴充更新這些後綴後樹的樣子。

圖5中未在葉節點處終止的第一個後綴是K。當更新後綴樹時，第一個非葉節點被定義為樹的活躍點。所有比活躍點定義的後綴長的後綴都將以葉節點結束。此點之後的後綴都不會在葉節點處終止。

後綴K終止於KKE定義的沿邊向下的隱式節點。在測試非葉節點時，我們需要查看它們是否有任何與要追加的新字符匹配的後代。在這種情況下，那將是E。

快速查看KKE中的第一個K，發現它只有一個後代：K。所以這意味著我們必須添加一個代表字母E的葉節點。這個過程需要兩步。首先，我們拆分保持弧的邊，以使待測後綴的末尾有一個顯式節點。圖6中間的樹顯示了拆分後樹的樣子。

一旦拆分了邊，並且添加了新節點，你就會看到一個類似於圖6第三個位置的樹。注意成長為KE的K節點，已成為葉節點。

更新顯式節點

更新後綴K後，我們仍然需要更新下一個較短的後綴，即空字串。空字串在顯式節點0結束，所以我們只需檢查它是否有一個以字母E開頭的後代。快速查看圖6中的樹表明節點0沒有葉節點，所以添加了另一個葉節點，產生如圖7所示的樹。

泛化演算法

通過利用後綴樹的一些特性，我們可以得到一個相當高效的演算法。第一個重要特徵是：一旦為葉節點，總是葉節點。葉節點自創建後永遠不會有後代，它只會通過字符串接進行擴充。更重要的是，每次我們向樹添加新後綴時，我們將自動地向通往每個葉節點的邊擴充單個字符。該字符將是新後綴中的最後一個字符。

這使得對邊的管理變得容易。每當創建一個新的葉節點時，我們會自動設置其邊以表示從其起點到輸入文本末尾的所有字符。即使不知道這些字符是什麼，我們也知道它們最終會被添加到樹中。因此，一旦創建了葉節點，我們就可以忘掉它！如果邊被拆分，它的起始點可能會改變，但它仍然會一直延伸到輸入文本的末尾。

這意味著只需要關心在活躍點（第一個非葉節點）更新顯式和隱式節點。鑑於此，我們必須從活躍點到空字串，測試每個節點是否需要更新。

然而，提前停止更新可以節約時間。當遍歷後綴時，我們將為每個沒有以正確字符開頭的後代邊的節點添加一個新邊。當最終找到具有正確字符作為後代的節點時，我們就可以停止更新了。了解了構造演算法的工作原理，你可以看出：如果某個字符是特定後綴的後代，那它也是每個較小後綴的後代。

找到第一個匹配後代的點稱為終止點。終止點有一個額外的特別有用的特性。由於在活躍點和終止點之間的每個後綴中添加了葉節點，我們現在知道每個長於終止點的後綴是葉節點。這意味著終止點將在下一輪遍歷時變為活躍點!

通過將更新限制在活躍點和終止點之間的後綴，我們削減了更新樹所需的處理。通過追踪終止點，我們會自動知道下一輪的活躍點。使用此訊息的更新演算法的第一輪可能看起來像這樣（以類C的偽代碼）：

Update( new_suffix )
{
  current_suffix = active_point
  test_char = last_char in new_suffix
  done = false;
  while ( !done ) {
    if current_suffix ends at an explicit node {
      if the node has no descendant edge starting with test_char 
        create new leaf edge starting at the explicit node
      else
        done = true;
    } else {
      if the implicit node's next char isn't test_char {
        split the edge at the implicit node
        create new leaf edge starting at the split in the edge
      } else
        done = true;
    }
    if current_suffix is the empty string
      done = true; 
    else
       current_suffix = next_smaller_suffix( current_suffix )
  }
  active_point = current_suffix
}

後綴指標

上面顯示的偽代碼演算法大致正確，但它掩蓋了一個問題。當我們瀏覽樹時，我們通過調用next_smaller_suffix()移動到下一個較小的後綴。該程式必須找到對應於特定後綴的隱式或顯式節點。

如果簡單地順著樹從上往下直至找到正確的節點，演算法的運行時間將不是線性的。為了解決這個問題，我們必須為樹添加一個額外的指標：後綴指標。後綴指標是在每個內部節點都有的指標。每個內部節點表示從根開始的字符序列。後綴指標指向該字串的第一個後綴的節點。因此，如果特定字串包含輸入文本的字符0到N，則該字串的後綴指標將指向作為從根開始的字串（該字串表示輸入文本1到N的字符）的終止點的節點。

圖8顯示了字串ABABABC的後綴樹。第一個後綴指標位於表示ABAB的節點上。該字串的第一個後綴是BAB，這是在ABAB的後綴指標所指向的。同樣，BAB有自己的指向AB的節點的後綴指標。

後綴指標是在對樹進行更新的同時構建的。當從活躍點移動到終止點時，我會跟踪創建的每個新葉子的父節點。每次創建新邊時，我也會從上一個創建的葉邊的父節點創建一個後綴指標來指向當前父邊。（顯然，我不能為在更新中創建的第一條邊執行此操作，但我會對所有剩餘的邊執行此操作。）

隨著後綴指針的到位，從一個後綴轉到下一個後綴只要跟隨指標就行了。這是將演算法簡化為O(N)的重要補充。

樹屋

為了幫助說明這篇文章，我寫了一個簡短的程序STREE.CPP，它從標準輸入中讀取一串文本並構建一個後綴樹。清單1中顯示的是註釋完全的C++版本。第二個版本STREED.CPP加上了大量的調試輸出，可以從DDJ列表服務以及我的主頁獲得。

理解STREE.CPP實際上只是理解它包含的數據結構的工作原理。 最重要的數據結構是Edge物件。Edge的類別定義是：

class Edge {
    public :
        int first_char_index;
        int last_char_index;
        int end_node;
        int start_node;
        void Insert();
        void Remove();
        Edge();
        Edge( int init_first_char_index,
              int init_last_char_index,
              int parent_node );
        int SplitEdge( Suffix &s );
        static Edge Find( int node, int c );
        static int Hash( int node, int c );
};

每次創建後綴樹中的新邊時，都會創建一個新的Edge物件來表示它。該物件的四個數據成員定義如下：

構建後綴樹時執行的最常見任務之一是基於其字串首字符來搜尋從特定節點發出的邊。在面向位元組的計算機上，可能有多達256條邊來自單個節點。為了使搜索合理快速和簡單，我將邊存儲在雜湊表中，使用基於其起始節點編號和子字串首字符的雜湊鍵。成員函數Insert()和Remove()用於管理進出雜湊表的邊的傳輸。

構建後綴樹時使用的第二個重要數據結構是後綴物件。請記住，更新樹是通過處理當前存儲在樹中的字串的所有後綴來完成的，從最長點開始，到終止點結束。後綴只是一個字串，從節點0開始，到樹中的某個點結束。

合情合理地，我們可以通過僅定義其末字符在樹中的位置來安全地表示任何後綴，因為我們知道首字符從節點0開始，即根。後綴物件定義了使用該系統的後綴，其定義如下：

    class Suffix {
        public :
            int origin_node;
            int first_char_index;
            int last_char_index;
            Suffix( int node, int start, int stop );
            int Explicit();
            int Implicit();
            void Canonize();
    };

後綴物件從特定節點開始，跟隨由成員first_char_index和last_char_index指向的輸入文本中的字串，定義字串中的末字符。例如，在圖8中，最長的後綴「ABABABC」的origin_node為0，first_char_index為0，last_char_index為6。

Ukkonen的演算法要求我們以正規形式使用這些後綴定義。每次修改後綴物件時，都會調用函數Canonize()來執行此轉換。後綴的正規表示只需要後綴物件中的origin_node是與字串終止點最接近的父。這意味著由一對(0, “ABABABC”)表示的後綴字串將通過以下步驟進行正規化：先移動到(1, “ABABC”)，然後(4, “BC”)，最後(8, “”)。

當後綴字串在顯式節點上結束時，正規表示將使用空字串來定義字串中的剩餘字符。通過將first_char_index設置為大於last_char_index來定義空字符串。在這種情況下，我們知道後綴在顯式節點上結束。如果first_char_index小於或等於last_char_index，則表示後綴字串在隱式節點上結束。

給定這些數據結構的定義，我認為你會發現STREE.CPP中的程式碼是Ukkonen演算法的簡單實現。為了更加清晰，請使用STREED.CPP以便在運行時吐出大量的調試訊息。

致謝

通過閱讀Jesper Larsson關於1996年IEEE數據壓縮會議的論文，我終於解決了後綴樹的構建問題。Jesper也非常友好地向我提供了示例代碼和Ukkonen論文的連結。

參考書目

E.M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23:262-272, 1976.
E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, September 1995.

原始碼下載

stree.cpp    一個簡單的程式，可以從輸入字串創建後綴樹。
streed.cpp     相同的程式，添加了大量調試代碼。