-
後綴樹
鎖定
- 中文名
- 後綴樹
- 外文名
- 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]。
[1]
後綴樹廣義後綴樹
對於字符串集合T={t1,t2…tn}的廣義後綴樹，是一個壓縮字典樹（trie）其中包含了T中每一個字符串的所有的後綴。
每一個葉節點，是由 對來標記的，即包含了所在的字符串和在字符串中的開始位置。
廣義後綴數組的構造：
將T中的所有字符串加上終結符$連接在一起構成新的字符串S= t1$t2$…tn $；對字符串S構造，後綴樹；每一個葉節點標記上在S中的起始位置；移除橫跨多個字符串的後綴；將葉節點的起始位置映射成對。説明：真實構造中對後綴的比較只比較到字符$就結束，這樣不會出現橫跨多個字符串的後綴。
[1]
