《资料结构与演算法上课讲义》由会员分享，可在线阅读，更多相关《资料结构与演算法上课讲义（98页珍藏版）》请在金锄头文库上搜索。
1、資料結構與演算法,台大資工系 呂學一 http:/www.csie.ntu.edu.tw/hil/algo/,1,2,Suffix Tree,字尾樹、後綴樹 an extremely powerful data structure for string algorithms,3,上次: Gusfields algorithm,Input: P and S. Output: All occurrences of P in S. Time: O(|P| + |S|) Technique: Z values of PS. Z(i + |P|) |P| iff P = Sii + |P| 1.,P,S
2、,4,To P or not to P .,Preprocessing P Gusfield Boyer-Moore Knuth-Morris-Pratt Preprocessing S Suffix tree,6,Suffixes of S,S = b b a b b a a b S18= b b a b b a a b S28= b a b b a a b S38= a b b a a b S48= b b a a b S58= b a a b S68= a a b S78= a b S88= b,1st suffix,2nd suffix,3rd suffix,4th suffix,5t
3、h suffix,6th suffix,7th suffix,8th suffix,7,KEY: P occurs in S iff P is a prefix of a suffix of S.,S = b b a b b a a b S18= b b a b b a a b S28= b a b b a a b S38= a b b a a b S48= b b a a b S58= b a a b S68= a a b S78= a b S88= b,1st suffix,2nd suffix,3rd suffix,4th suffix,5th suffix,6th suffix,7th
4、 suffix,8th suffix,8,T = Suffix Trie of S,b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,9,Why suffix trie?,The following statements are equivalent. P occurrs in S. P is a prefix of a suffix of S. P corresponds to a path of T starting from the root of T.,10,P = b a b b a,b b
5、 a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,P occurs in S!,11,P = b b a a b a,b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,P doesnt occur in S!,12,P = a b b b a a,b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,P doesnt occu
6、r in S!,13,Q: P出現在S的哪個位置？,14,P = a b b a a,8,4,4,4,4,1,1,1,1,1,5,5,5,2,2,2,2,2,6,7,6,3,3,3,7,3,1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,Output: 3,15,用suffix trie來解題,Question: If we are given a suffix trie of S, what is the time complexity for finding an
7、 occurrence of P in S? Answer: O(|P|) time.,16,建構Suffix Trie,Q: Time complexity for constructing the suffix trie T of S?,Q(|S|),Q(|S| log |S|),Q(|S|2),Q(|S|3),17,Time = O(|S|2),8,4,4,4,4,1,1,1,1,1,5,5,5,2,2,2,2,2,6,7,6,3,3,3,7,3,1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a
8、 a b a a b a b b,18,Worst-case time = W(|S|2),How to establish a lower bound? Answer: Showing an example which takes W(|S|2) time for any algorithm.,19,S = a a a a b b b b,20,Summary,Suffix trie is good in solving Substring Problem, but may require W(|S|2) time and space. Question: is there a compac
9、t representation of suffix trie that needs only O(|S|) time and space?,21,Suffix Tree,A compact representation of suffix trie,22,Observations on Trie T of S,T has at most |S| leaves. Why? T has at most |S| 1 branching nodes. Why?,23,Keeping leaves and branching nodes only. compact representation of
10、edge labels,S = a a a a b b b b,5,8,5,8,5,8,5,8,4,8,1,1,2,2,3,3,24,S = a a a a b b b b,25,S = b b a b b a a b,26,S = b b a b b a a b,1,1,2,3,4,8,7,8,4,8,7,8,4,8,7,8,3,3,3,3,27,S = b b a b b a a b,28,Question,The space complexity of suffix tree O(|S|) O(|S| log |S|) O(|S|2) O(|S|3) Why? Number of nod
11、es = O(|S|). Number of edges = O(|S|). Space required by each edge = O(1).,29,The challenge,Constructing Suffix Tree in Linear Time,30,History of Suffix Tree Algorithms,Weiner, IEEE FOCS 1973 Linear time but expensive in space. D. E. Knuth: “the algorithm of 1973”. McCreight, J. ACM 1976 Linear time
12、 and quadratic space. Ukkonen, Algorithmica 1995 Linear time and linear space. Much better readability.,31,Esko Ukkonen, University of Helsinki, Finland,32,Ukkonens Algorithm,Let T(k) denote the suffix tree of S1k. Framework compute T(1); for k = 2 to |S| do compute T(k) from T(k-1);,33,|S| iteratio
13、ns the k-th iteration has k steps,S = b b a b b a a b S18= b b a b b a a b S28= b a b b a a b S38= a b b a a b S48= b b a a b S58= b a a b S68= a a b S78= a b S88= b,34,Ukkonens approach on Suffix Trie,b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b,35,S =,b,b,a,b,b,a,a,b,1,1
14、,2,3,1,2,3,3,3,3,1,1,2,4,3,4,3,4,2,5,3,5,3,5,2,6,3,6,3,6,3,3,7,7,4,7,3,3,7,7,4,7,2,3,7,7,4,7,7,8,4,8,7,8,4,8,7,8,4,8,The corresponding process of growing suffix tree,Observation: The tree structure does not change very often, i.e., only O(|S|) times.,36,Observation,At the beginning of the k-th iteration, there are exactly k “growing points”(生長點), all with different heights. The k-th iteration iteratively grows k edges with label Sk at those k growing points.,37,Ukkonens approach on Suffix Trie,b b a b b a a b b a b b a a
