後綴樹（Suffix tree）是一種數據結構，能快速解決很多關於字元串的問題。後綴樹的概念最早由Weiner 於1973年提出，既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改進完善。
基本介紹
- 中文名：後綴樹
- 外文名：Suffix tree
- 類型：數據結構
- 功能：快速解決很多關於字元串的問題
基本信息,簡介,詳述,其它信息,舉例,其它例子,廣義後綴樹,
基本信息
簡介
後綴樹提出的目的是用來支持有效的字元串匹配和查詢。
詳述
一個具有m個詞的字元串S的後綴樹T，就是一個包含一個根節點的有向樹，該樹恰好帶有m個葉子，這些葉子被賦予從1到m的標號。 每一個內部節點，除了根節點以外，都至少有兩個子節點，而且每條邊都用$的一個非空子串來標識。出自同一節點的任意兩條邊的標識不會以相同的詞開始。後綴樹的關鍵特徵是：對於任何葉子i，從根節點到該葉子所經歷的邊的所有標識串聯起來後恰好拼出S的從i位置開始的後綴，即S[i,…,m]。樹中節點的標識被定義為從根到該節點的所有邊的標識的串聯。
其它信息
舉例
圖中示意了字元串 "I know you know I know "的後綴樹。內部節點用圓來表示，葉子用矩形來表示,該例子中有六個葉子，被標號為1到6。 終止字元在圖中被省略掉了。
其它例子
同理, 若干字元串組成的後綴樹, 稱為一個擴展的後綴樹：n個字元串Sn，其中字元串的長度為mn, 由這些字元串組成一個擴展的後綴樹 T ，它是一個包含一個根節點的有向樹，該樹有mn個葉子，每個葉子都用一個兩數字的坐標tuple(k,l)來標識，其中k的範圍是從1到n，而l的範圍是從1到mk ，每一個內部節點，除了根節點外，都有兩個子節點並且每條邊都用一個非空的S中若干單詞構成的一個子串來標識。並且出自同一節點的任意兩條邊的標識的第一個單詞不能相同。對於任意的葉子(i,j),從根節點到該葉子所經歷的所有邊的標識的串聯恰好拼出後綴Si，該後綴從位置j開始，就是說它們拼出了Si[j..mi]。
廣義後綴樹
對於字元串集合T={t1,t2…tn}的廣義後綴樹，是一個壓縮字典樹（trie）其中包含了T中每一個字元串的所有的後綴。
每一個葉節點，是由<StringID, Start position> 對來標記的，即包含了所在的字元串和在字元串中的開始位置。
廣義後綴數組的構造：
將T中的所有字元串加上終結符$連線在一起構成新的字元串S= t1$t2$…tn $；對字元串S構造，後綴樹；每一個葉節點標記上在S中的起始位置；移除橫跨多個字元串的後綴；將葉節點的起始位置映射成<String ID, Start position>對。說明：真實構造中對後綴的比較只比較到字元$就結束，這樣不會出現橫跨多個字元串的後綴。
