演算法知識 - Suffix Tree 後綴樹 (Using Ukkonen Algorithm)

2020-11-03

字數統計： 5k | 閱讀時間≈ 20分鐘

Suffix Tree 介紹

Suffix Tree 是字典樹(Trie) 的延伸，透過對一字串的所有後綴去建構樹，是一個能解決許多字串特定問題的資料結構。

以下是 Suffix Tree 能解決的問題：

尋找 A 字串是否在字串 B 中

找出 B 在 A 字串重複的次數

最長共同子字串

簡單來說 Suffix Tree 是將字串的所有後綴建構成 Trie，再將其壓縮(沒有分支的節點都放在同個節點)。

建立 Suffix Tree 的時間複雜度為 $O(n)$，使用 Ukkonen Algorithm
通常建構 Suffix Tree 有兩種方法，一種時間複雜度為 $O(n)$，另一種為 $O(n^2)$，這裡只介紹普遍比賽會經用的演算法(Ukkonen Algorithm)

此文章跳開蠻多證明與理論，如果想要知道可再從下方參考連結點選即可

Suffix Tree 原理 (正確來說應該是Ukkonen Algorithm 原理)

這裡我們借助 Tushar Roy 的 Youtube 影片教學，此教學影片非常棒，連結將放在下方標題的參考連結
這裡我們將透過一字串 “xyzxyaxyz$” 來進行解說，有些地方會跟影片不一樣，因為我個人認為這樣寫對學習更有幫助，請不要理會右邊的變數，EX: remaining , active_Node…。

名詞介紹

先來介紹一些我們會用到的名詞

remaining 隱藏在 Suffix Tree 中的後綴節點
root = Suffix Tree 的最主要根節點
active_node 活動節點，主要是用來生長葉節點 (leaf)
active_e 隱藏節點的第一個字元
active_len 隱藏在 Suffix Tree 中節點的長度
node 一個 struct 用來存入 Suffix Tree 節點
- start 此節點開始的位置(index)
- end 此節點結束的位置(end)
  舉例： node.start = 3 and node.end = 5，則 string 的長度是 string.substr(3,2)，用數學表示則是 $(start , end ]$
- next 用來指出下一個節點的位置，個人習慣用 map
- slink 指出此節點的最長後綴節點，EX: XYZ 則指出 YZ。
- edge_length() 公式為 $min(end,pos+1) - start $
  用來找出此節點的字串長度

原理說明 - 初始建構

我們必須先建構 Suffix Tree Root，才可以讓 Suffix Tree 慢慢變長，Suffix Tree Root 的 start and end 都是 -1，Root 是起始點且並不包含任何資料。

remaining = 0
一開始不會有隱藏在 Suffix Tree 中的後綴節點於是設定成 0
root = 1
我們捨棄從 0 開始，從 1 開始會更好建構，於是起始點是 1
active_node = 1
由於一開始生長葉節點只能先從 root 開始，所以設定 active_node = root
active_e = 0
一開始沒有隱藏節點於是設定成 0
active_len = 0
一開始沒有隱藏在 Suffix Tree 中節點的長度，所以設定 0

原理說明 - “x”

由於一開始樹中並沒有 x 此字元，直接產生新節點(葉節點)，由於有產生節點，沒有隱藏節點所以 remaining = 0

葉節點(node) 建構設定
- start 等於此字元位置
- end 等於字串長度
- slink 設定為 0
- next.clear()

原理說明 - “x”

原理說明 - “xy”

樹中沒有 y 字元，也直接產生新節點，跟上個步驟一樣。

原理說明 - “xy”，這裡無法截圖到 remaining 為 0 的狀態，於是自己寫

原理說明 - “xyz”

樹中沒有 z 字元，也直接產生新節點，跟上個步驟一樣。

原理說明 - “xyz”，這裡無法截圖到 remaining 為 0 的狀態，於是自己寫

原理說明 - “xyzx”

樹中已經有 x 字元，且是在 active_node 底下，於是我們不新增節點，以符合壓縮原理，而我們多了一個隱藏節點並將隱藏節點長度則 +1，因為增加 x，且 remaining 也要 +1 表示增加一個隱藏節點。

原理說明 - “xyzx”

原理說明 - “xyzxy”

樹中已經有 y 字元，且是在 active_node 底下，於是我們不新增節點，以符合壓縮原理，而我們多了一個隱藏節點並將隱藏節點長度則 +1，因為增加 y，且 remaining 也要 +1 表示增加一個隱藏節點。

這時隱藏節點長度(active_len)則變成 2
remainging = 2
隱藏字元有 “xy”

原理說明 - “xyzxy”

原理說明 - “xyzxya”

這裡需要比較長的說明，共三個步驟。

step 1:

此時的隱藏長度為 2，我們無法因為字元 a 而增加隱藏長度，因為前面是 “xyz“(先從隱藏字元方向 “xy” )，而不是 “xya“，所以我們這邊要做出一個切割節點，切割方式為 root 往 x 的邊且長度為 2；來保持 “xyzxya” 後綴與 “xya” 後綴，分裂完成後 remaining 必須 -1，因為 x 此隱藏節點已經產生，隱藏長度(active_len)也需 -1。

這時隱藏節點長度(active_len)則變成 1
remainging = 1
隱藏字元有 “y”

原理說明 - “xyzxya” 切割點為 xy

step 2:

此時的隱藏長度為 1，我們無法因為字元 a 而增加隱藏長度，因為前面是 “yz“，而不是 “ya“，所以我們這邊要做出一個切割節點，切割方式為 root 往 y 的邊且長度為 2；來保持 “yzxya” 後綴與 “ya” 後綴，分裂完成後 remaining 必須 -1，因為 y 此隱藏節點已經產生，隱藏長度(active_len)也需 -1。

此時的 slink 則派上用場，需要指回在隱藏字元 “xy” 時所切割的節點，表示如果 xy 的葉節點們如果也需要更改時則表示隱藏字元 “y” 時所切割的葉節點也需要更改。

這時隱藏節點長度(active_len)則變成 0
remainging = 0
隱藏字元無

原理說明 - “xyzxya” 切割點為 y

step 3:

由於一開始樹中並沒有 a 此字元，直接產生新節點(葉節點)，由於有產生節點，沒有隱藏節點所以 remaining = 0

原理說明 - 新增 a 節點

原理說明 - “xyzxyax”

與第一個步驟相似

這時隱藏節點長度(active_len)則變成 1
remainging = 1
隱藏字元有 “x”

原理說明 - “xyzxyax”

原理說明 - “xyzxyaxy”

這時隱藏節點長度(active_len)則變成 2
remainging = 2
隱藏字元有 “xy”

原理說明 - “xyzxyaxy”

原理說明 - “xyzxyaxyz”

樹中已經有 z 字元，且是在 active_node 底下，於是我們不新增節點，以符合壓縮原理，而我們多了一個隱藏節點並將隱藏節點長度則 +1，因為增加 z，且 remaining 也要 +1 表示增加一個隱藏節點。

這時隱藏節點長度(active_len)則變成 3
remainging = 3
隱藏字元有 “xyz”

原理說明 - “xyzxyaxyz”

原理說明 - “xyzxyaxyz$”

由於我們希望只要是後綴樹的後綴都可以有一個節點而不被隱藏，於是我們增加一個從未出現的符號，來把這些隱藏節點全部都拉出來新增節點，有點類似於新增 a 的步驟，但在複雜一些，共有四步。

step 1

此時的隱藏長度為 3，我們無法因為字元 $ 而增加隱藏長度，因為前面是 “xyzx“，而不是 “xyz$“，所以我們這邊要做出一個切割節點，切割方式為 root 往 z 的邊且長度為 1，這是因為前面 xy 已經是一個節點，所以我們就必須先將 active_len 先減 2 的節點在往 z 的方向切割；來保持 “xyzxyaxyz$” 後綴與 “xyz$” 後綴，分裂完成後 remaining 必須 -1，因為 z 此隱藏節點已經產生，隱藏長度(active_len)也需 -1。

這時隱藏節點長度(active_len)則變成 2
remainging = 2
隱藏字元有 “yz”

原理說明 - “xyzxyaxyz$” 切割點為 xyz，這裡 remainding 應該為 2

step 2

此時的隱藏長度為 2，我們無法因為字元 $ 而增加隱藏長度，因為前面是 “yzx“，而不是 “yz$“，所以我們這邊要做出一個切割節點，切割方式為 root 往 z 的邊且長度為 1，這是因為前面 y 已經是一個節點，所以我們就必須先將 active_len 先減 1 的節點在往 z 的方向切割；來保持 “yzxyaxyz$” 後綴與 “yz$” 後綴，分裂完成後 remaining 必須 -1，因為 z 此隱藏節點已經產生，隱藏長度(active_len)也需 -1。

此時的 slink 則派上用場，需要指回在隱藏字元 “xyz” 時所切割的節點，表示如果 xyz 的葉節點們如果也需要更改時則表示隱藏字元 “yz” 時所切割的葉節點也需要更改。

這時隱藏節點長度(active_len)則變成 1
remainging = 1
隱藏字元有 “z”

原理說明 - “yzxyaxyz$” 切割點為 yz，這裡 remainding 應該為 1，沒辦法擷取到完整畫面，只好犧牲

step 3

此時的隱藏長度為 1，我們無法因為字元 $ 而增加隱藏長度，因為前面是 “zx“，而不是 “z$“，所以我們這邊要做出一個切割節點，切割方式為 root 往 z 的邊且長度為 1；來保持 “zxyaxyz$” 後綴與 “z$” 後綴，分裂完成後 remaining 必須 -1，因為 z 此隱藏節點已經產生，隱藏長度(active_len)也需 -1。

此時的 slink 則派上用場，需要指回在隱藏字元 “yz” 時所切割的節點，表示如果 yz 的葉節點們如果也需要更改時則表示隱藏字元 “z” 時所切割的葉節點也需要更改。

這時隱藏節點長度(active_len)則變成 0
remainging = 0
隱藏字元無

原理說明 - “zxyaxyz$” 切割點為 z，這裡 remainding 應該為 0，沒辦法擷取到完整畫面，只好犧牲

step 4

由於一開始樹中並沒有 $ 此字元，直接產生新節點(葉節點)，由於有產生節點，沒有隱藏節點所以 remaining = 0

原理說明 - “xyzxyaxyz$” 切割點為 $

總結

以上，就是 Suffix Tree 原理，謝謝各位觀看，如果還是看不太懂可以看Tushar Roy - Coding Made Simple 大神的影片教學，一定比我講得更棒。

程式碼實現與說明

程式碼實現與說明分成三大部分，建構、初始化、SAM 擴增長度。

建構

這裡比較簡單，於是請直接看此就沒問題的XD。
原理說明 - 初始建構

struct node{
    int start , end ,slink ; 
    map<char,int> next ;

    int edge_length(){
        return min(end , pos+1) - start ;
    }

    void init(int st , int ed = oo){
        start = st ;
        end = ed ;
        slink = 0 ;
        next.clear() ;
    }
}tree[2*N];

初始化

建議搭配名詞介紹會更好理解。
cnt 為我們 Suffix Tree 的總長度

void st_init(){
    //tree root is 1 not zero
    needSL = remainder_ = 0 ;
    active_node = active_e = active_len = 0 ;
    pos = -1 ;

    cnt = root = 1 ;
    active_node = 1 ;
    tree[cnt++].init(-1,-1);
    return ;
}

Suffix Tree 擴增長度

建議搭配原理說明-“x” 以下全部的原理說明會更好理解。
這份程式碼與影片教學方式有些許差別，原因是因為這份程式碼我是用簡潔的方式寫，而影片則是用好理解的方式去教導。

請注意 remainder 進入迴圈後是從 1 開始，之後再到迴圈的最後做 -1 的動作，上述原理說明有省略此步

char active_edge(){ //隱藏字元的第一個
    return text[active_e] ;
}

void add_SL(int node){ // slink 指回上一個隱藏節點的位置，如果上一個後綴節點的葉節點需要被更改時，
// 這裡的下方葉節點也能被迅速被更改，達到 O(1) 效果
    if(needSL > 0 ) tree[needSL].slink = node ;
    needSL = node ;
}

bool walkdown(int node){ //即 原理說明 - "xyzxyaxyz$" 的 step 1， xyz 但 xy 是一個節點，
// 需要在往下一個子節點前進
    if(active_len >= tree[node].edge_length()){
        active_e += tree[node].edge_length() ; //找到此長度後的第一個隱藏字元 
        active_len -= tree[node].edge_length() ; //減少長度
        active_node = node ; //往後方前進
        return true ;
    }
    return false ;
}

void st_extend(char c){ //擴增 suffix tree 
    pos++; // 往下個字串前進
    needSL = 0 ; // 紀錄上一個切割點的位置，用來 slink 的前一個點
    remainder_++ ; // 先 +1，如果這個點有被增加之後做 -1 的動作
    while(remainder_ > 0){
        if(active_len == 0 ) active_e = pos ; 
        // 如果 active len 等於 0，就表示沒有隱藏長度，所以我們要判斷的就是當前字元
        // 是否存在此 active_node 節點中
        if(tree[active_node].next[active_edge()] == 0){ 
            // active_node 沒有此字元的節點，新增節點
            int leaf = cnt ;
            tree[cnt++].init(pos) ;
            tree[active_node].next[active_edge()] = leaf ;
            add_SL(active_node) ;　// 紀錄 slink 的位置，以防下次用到
        }
        else{ // active_node 有此字元的節點
            int nxt = tree[active_node].next[active_edge()] ;
            if(walkdown(nxt)) continue ; // 如果還需要在往下一個節點走，就減少隱藏長度，
            //然後回去重新查詢
            if(text[tree[nxt].start + active_len] == c){ 
                // 如果此節點有包含到此字元，代表隱藏長度可以+1，因為後綴還是在節點長裡面
                active_len++ ; // 隱藏長度可以 +1
                add_SL(active_node) ; // 紀錄 slink 的位置，以防下次用到
                break ; //由於隱藏節點是 +1，所以我們沒必要減
            }
            // 需要做切割點
            int split = cnt ; 
            tree[cnt++].init(tree[nxt].start , tree[nxt].start + active_len) ;
            //製作切割點中...，結束位置就是當前節點的 start + 隱藏長度
            tree[active_node].next[active_edge()] = split ;
            // 需要將 active_node 指向我們的切割點，而不是原來的點
            int leaf = cnt ; // 需要葉節點
            tree[cnt++].init(pos) ;
            // 製作葉節點
            tree[split].next[c] = leaf ; // 把葉節點指向我們的切割點
            tree[nxt].start += active_len ; //原本的節點 start 往後到切割點的 end
            tree[split].next[text[tree[nxt].start]] = nxt ; //將原本節點指向我們的切割點
            add_SL(split) ; // 紀錄 slink 的位置，以防下次用到
        }
        remainder_-- ; // 由於有增加節點，所以 -1
        if(active_node == root && active_len > 0 ){ 
            //active_len > 0 表示我們現在做的是把隱藏節點新增，所以要減掉
            //active_node == root 確保有回到根節點才做隱藏節點減掉，否則 
            //text[node.start + active_len ] 就會亂掉
            active_len-- ;
            //由於我們減少了一個隱藏長度，所以 -1 
            active_e = pos - remainder_ + 1 ;
            //找到減少後隱藏長度的第一個隱藏字元，此時如果 active_len == 0，
            // 則下次迴圈則在 active_e 會被重新定義成 pos
        }
        else{
            // 跟著 slink 走去改動其他的後綴在 tree[active_node].slink > 0 時，
            // 否則則回到 root，繼續建立後綴樹
            active_node = tree[active_node].slink > 0 ? tree[active_node].slink : root ;
        }
    }
    return ;
}

Suffix Array 應用

我在學習此演算法的過程中如果有題目讓我應用到此演算法我則收錄在此，連結則是我的詳解如果想要去看題目的就搜尋一下吧！

最長重複子字串 longest repeated substring

參考連結

Suffix Tree using Ukkonen’s algorithm
简单的英语中的Ukkonen后缀树算法
上述兩個為我學習此演算法的學習重點
github makagonov/ST.cpp Secret

心得

學習這演算法花了我很多時間還耗盡了很多腦細胞呢…嗚嗚，太笨了，看網路上的資源都還看不太懂，其實在網路上找資料是一件很花時間的事情，有些 blog 的資訊是錯誤亦或是寫得過於簡單，於是希望我這篇是可以不誤導他人，~~我想應該很難，不過我的 blog 不太容易被找到吧XD，應該不會禍害大家~~，學習 Suffix Tree 可能是我方法不對，讓我這次的學習演算法之路非常痛苦，我不會說這一次的學習是快樂的，但確實是在困難中的演算法學習最快的，因為我有壓力，壓力大到連睡覺都睡不著，身體一直記著要趕快學好此演算法。

我想聊一些關於寫演算法的事情，寫演算法是快樂的，但在學習演算法的過程中其實是非常痛苦的，因為你想不透可又不想認輸是件非常痛苦的事情，你會懷疑自己，在這時候我突然認為許多書上講得符合在我的經驗中，「比賽，最大的敵人是你自己」，你在學習演算法時常會遇到新的困境，當你突破時又有可能遇到新的問題，過程中你會不斷詢問自己，自己是對的嗎？我是不是對演算法沒有天賦，到現在就算我學習了這個演算法還是覺得自己很沒有天賦，需要花很多時間學習與準備。

老實講，我很羨慕台灣頂大的學生，有很好的機會可以遇到好老師發展，在台北科大，會演算法的老師其實並不多，這是一個非常可怕的問題，他導致整間學校的演算法水準都停擺在會 Sort 的情況，這樣寫出來的程式品質怎麼會是好的，然後老師們也不熱心於去學習新的演算法，不在意學生的程式知識水準這樣怎麼可以培養出優秀的人才，當我向老師詢問比較進階的演算法時老師都保持消極的態度導致我只能在網路上自學，不斷遇到錯誤、遇到挫折，懷疑自己。

如果可以，有誰會想要遇到挫折，我只想要快樂的活著

總之，我希望台灣頂大的學生都可以好好把握住自己的機會，不然困在北科的我會很難過QQ，之後有空再讓我說說我認為台灣教育制度的不公平。

Suffix Tree 無註解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define T 110
#define N 100100
using namespace std;
int root , cnt , pos , needSL , remainder_ , // note:remainder is cmath function
    active_node , active_e , active_len ;
string text ;
int oo ;
int max_lrs = 0 , lrs_index = 0 , lrs_repeat = 0 ;

struct node{
    int start , end ,slink ;
    map<char,int> next ;

    int edge_length(){
        return min(end , pos+1) - start ;
    }

    void init(int st , int ed = oo){
        start = st ;
        end = ed ;
        slink = 0 ;
        next.clear() ;
    }
}tree[2*N];

char active_edge(){
    return text[active_e] ;
}

void add_SL(int node){
    if(needSL > 0 ) tree[needSL].slink = node ;
    needSL = node ;
}

bool walkdown(int node){
    if(active_len >= tree[node].edge_length()){
        active_e += tree[node].edge_length() ;
        active_len -= tree[node].edge_length() ;
        active_node = node ;
        return true ;
    }
    return false ;
}

void st_init(){
    //tree root is 1 not zero
    needSL = remainder_ = 0 ;
    active_node = active_e = active_len = 0 ;
    pos = -1 ;

    cnt = root = 1 ;
    active_node = 1 ;
    tree[cnt++].init(-1,-1);
    return ;
}

void st_extend(char c){
    pos++;
    needSL = 0 ;
    remainder_++ ;
    while(remainder_ > 0){
        if(active_len == 0 ) active_e = pos ;
        if(tree[active_node].next[active_edge()] == 0){
            int leaf = cnt ;
            tree[cnt++].init(pos) ;
            tree[active_node].next[active_edge()] = leaf ;
            add_SL(active_node) ;
        }
        else{
            int nxt = tree[active_node].next[active_edge()] ;
            if(walkdown(nxt)) continue ;
            if(text[tree[nxt].start + active_len] == c){
                active_len++ ;
                add_SL(active_node) ;
                break ;
            }

            int split = cnt ;
            tree[cnt++].init(tree[nxt].start , tree[nxt].start + active_len) ;
            tree[active_node].next[active_edge()] = split ;
            int leaf = cnt ;
            tree[cnt++].init(pos) ;
            tree[split].next[c] = leaf ;
            tree[nxt].start += active_len ;
            tree[split].next[text[tree[nxt].start]] = nxt ;
            add_SL(split) ;
        }
        remainder_-- ;
        if(active_node == root && active_len > 0 ){
            active_len -- ;
            active_e = pos - remainder_ + 1 ;
        }
        else{
            active_node = tree[active_node].slink > 0 ? tree[active_node].slink : root ;
        }
    }
    return ;
}

void debug(){
	for(int i = 0 ; i < cnt ; i++){
        cout << i << ' ' << tree[i].start << ' ' << tree[i].end << ' ' << tree[i].slink << '\n' ;
        for(auto it : tree[i].next)
            cout << it.first << ' ' << it.second << '\n' ;
    }
    return ;
}

用紙筆去模擬 Suffix Tree

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己學習的手稿，紀錄者我的學習過程。

“xyzxyaxyz$” 圖解步驟表，不含最後一步

“xyzxyaxyz$” 程式實際跑一遍圖表 A

“xyzxyaxyz$” 程式實際跑一遍圖表 B，加上 Suffix Tree 最後一步圖表

版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！