Flashcards
Suffix Trees
Flashcards do conjunto (10)
- 1What is the text indexing problem?Matching a pattern string P of length m to a text string T of length n. Finding all locations where P matches T.
- 2For exact pattern matching, what is the time complexity of the best known algorithm?O(n) (KMP)
- 3List 4 properties of an atomic suffix tree1. The suffix tree contains every suffix of T as a root to leaf path.
2. Every edge is labelled with a character from T
3. No two edges leaving the same node have the same label.
4. Each leaf corresponds to a suffix (so there are n leaves) - 4How do you find a pattern in an atomic suffix tree?Start at the root and walk down the tree. Matches occur at the leaves of the subtree.
- 5How does a compacted suffix tree differ from an atomic suffix tree?Each non-branching path in an atomic suffix tree is replaced with a single edge. Edges are labelled with substrings.
- 6List 6 properties of a compacted suffix tree1. It contains n leaves.
2. Every internal node has two or more children
3. Every edge is labelled with a substring
4. No two edges leaving the same node have the same first character
5. Each leaf is labelled with a location in T
6. Any root-to-leaf path spells out corresponding suffix - 7How can we construct a compacted suffix tree in O(n^2) time?Insert suffixes one at a time. Search for the new suffix in the partial suffix tree. Add a new edge and leaf for the new suffix (may require the breaking of an edge into two).
- 8What are the time complexities of a Compacted Suffix Tree?O(n) space. O(m+occ) matching time, O(n) building time
- 9How can we make sure that a compacted suffix tree always exists?Add a unique symbol $ to the end of the text
- 10How can we construct a suffix array in O(n) time given a suffix tree?Perform a depth first search in lexicographical order, reporting the index corresponding to the leaf.