2806462
| Question | Answer |
| What 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. |
| For exact pattern matching, what is the time complexity of the best known algorithm? | O(n) (KMP) |
| List 4 properties of an atomic suffix tree | 1. 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) |
| How 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. |
| How 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. |
| List 6 properties of a compacted suffix tree | 1. 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 |
| How 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). |
| What are the time complexities of a Compacted Suffix Tree? | O(n) space. O(m+occ) matching time, O(n) building time |
| How can we make sure that a compacted suffix tree always exists? | Add a unique symbol $ to the end of the text |
| How 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. |
Want to create your own Flashcards for free with GoConqr? Learn more.