資料結(jié)構(gòu)與演算法-文庫(kù)吧
2025-07-06 17:24 本頁(yè)面
【正文】 [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 [5,8] [5,8] [5,8] [5,8] [4,8] [1,1] [2,2] [3,3] 25 26 [1,1] [2,3] [4,8] [7,8] [4,8] [7,8] [4,8] [7,8] [3,3] [3,3] [3,3] [1,1] [3,3] [2,3] [7,8] [4,8] [7,8] [4,8] [7,8] [4,8] 27 [3,3] [1,1] [3,3] [2,3] [7,8] [4,8] [7,8] [4,8] [7,8] [4,8] 28 ? The space plexity of suffix tree ? O(|S|) ? O(|S| log |S|) ? O(|S|2) ? O(|S|3) ? Why? ? Number of nodes = O(|S|). ? Number of edges = O(|S|). ? Space required by each edge = O(1). 29 Constructing Suffix Tree in Linear Time 30 ? [Weiner, IEEE FOCS 1973] ? Linear time but expensive in space. ? D. E. Knuth: “the algorithm of 1973”. ? [McCreight, J. ACM 1976] ? Linear time and quadratic space. ? [Ukkonen, Algorithmica 1995] ? Linear time and linear space. ? Much better readability. 31 32 ? Let T(k) denote the suffix tree of S[1…k]. ? Framework pute T(1)。 for k = 2 to |S| do pute T(k) from T(k1)。 33 S = b b a b b a a b S[1…8]= b b a b b a a b S[2…8]= b a b b a a b S[3…8]= a b b a a b S[4…8]= b b a a b S[5…8]= b a a b S[6…8]= a a b S[7…8]= a b S[8…8]= b 34 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] [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]? Observation: ? The tree structure does not change very often, ., only O(|S|) times. 36 ? At the beginning of the kth iteration, there are exactly k “growing points”(生長(zhǎng)點(diǎn) ), all with different heights. ? The kth iteration iteratively grows k edges with label S[k] at those k growing points. 37 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 38 ? Three cases while growing trie ? Case 1: growing an edge at a leaf. ? Case 2: growing a new branch of leaf. ? Case 3: does not change the tree structure. 39 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 Case 1: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 40 ? Those k steps in the kth iteration have the following pattern: ? some (at least one) Case1 steps, ? followed by some (could be zero) Case2 steps, ? followed by some (could be zero) Case3 steps. 41 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 Case 1: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 42 ? 在同一個(gè) iteration之中，「長(zhǎng)此以往」之前 (下 )的 step一定也是「長(zhǎng)此以往」。 ? At the end of each iteration, if a growing point is a leaf, then all previous (lower) growing points are also leaves. ? Why? 43 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 44
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1