main page — COMP 526 Efficient Algorithms
Unit 6: Text Indexing – Searching whole genomes
This is an archived version of this module from Fall 2022.
Click here for the current iteration.
This unit covers data structures over static text
that enable very efficient searching in the indexed text,
including some more recent advances in this field.
We cover
- inverted indices
- suffix trees
- applications of suffix trees: string matching, longest repeated substrings, longest common substrings, k-mismatch matching
- suffix arrays, LCP array
- linear-time construction for suffix and LCP arrays
Learning outcomes
- Know and understand methods for text indexing: inverted indices, suffix trees, (enhanced) suffix arrays
- Know and understand generalized suffix trees
- Know properties, in particular performance characteristics, and limitations of the above data structures.
- Design (simple) algorithms based on suffix trees.
- Understand construction algorithms for suffix arrays and LCP arrays.
Material
- slides
- Video 6-1 · transcript (2022-11-09, 35:25):
§6.1 Motivation, inverted indices, tries
- Video 6-2 · transcript (2022-11-09, 26:03):
§6.2 Suffix trees
- Video 6-3 · transcript (2022-11-09, 27:56):
§6.3 Applications of suffix trees
Chapters
0:18 Applications of suffix trees
9:36 Application 1: Text Indexing/String Matching
15:05 Longest repeated substring
22:00 Generalized suffix trees
23:48 Clicker Question
24:29 Longest common substring ► With that new idea, we can find longest common substrings
24:39 Longest common substring - Example
27:05 Application 3: Longest common substring - Video 6-5 · transcript (2022-11-21, 30:14):
§6.4 Longest common extensions
- Video 6-6 · transcript (2022-11-21, 7:28):
§6.5 Suffix arrays (part 1)
- Video 6-6 · transcript (2022-11-23, 25:56):
§6.5 Suffix arrays (part 2)
- Video 6-7 · transcript (2022-11-23, 24:32):
§6.6 Linear-time suffix sorting – Overview
- Video 6-8 · transcript (2022-11-23, 10:15):
§6.7 Linear-time suffix sorting – DC3 recursion
- Video 6-9 · transcript (2022-11-23, 28:58):
§6.8 LCP arrays
Further reading and sources
There is no textbook that covers all topics, but parts can be found in the following sources, all of which cover much more than the topics I selected.
Tries: These are notoriously treated only in passing in most algorithms and data structures textbooks, and there are various little differences in the details. Apart from the fact that they do not insist on prefix-free keys, I find the most helpful treatment of tries is given by Sedgewick and Wayne:
Suffix trees:
- Gusfield: Algorithms on Strings, Trees, and Sequences (1997) Cambridge University Press
- Crochemore, Rytter: Jewels of Stringology (2002), World Scientific
Suffix arrays have not yet found widespread inclusion in standard textbooks; my way of presenting it is mostly my own, but took inspiration from
Suffix arrays and LCP arrays are also discussed (in slightly different form) in