Full-Text (Substring) Indexes in External Memory

Description

Preface......Page 15 Acknowledgments......Page 17 Indexing Substrings......Page 19 Suffix Array......Page 21 Suffix Trie......Page 22 Suffix Tree......Page 24 Representation of a Suffix Tree......Page 26 Index Compression......Page 30 Using Disk Space......Page 31 Bibliographic Notes......Page 33 External Construction of Suffix Trees......Page 35 Transformation Algorithms......Page 36 Brute-force Algorithms......Page 38 Algorithms Based on Suffix-links......Page 40 The Ukkonen Algorithm......Page 42 Distributed and Paged Suffix Trees......Page 46 The Top Down Algorithm......Page 48 The Partition-and-Merge Algorithm......Page 51 The Merge Sort Algorithm......Page 54 Bibliographic Notes......Page 57 The Wavefront Algorithm......Page 61 The B2ST Algorithm......Page 66 Bibliographic notes......Page 71 Partitioning by Prefix......Page 73 Partitioning by Intervals......Page 74 String B-tree......Page 75 Exact Pattern Matching......Page 76 Matching all Substrings of a Query String......Page 78 Approximate Pattern Matching......Page 79 Maximal Repeats......Page 81 Common and Unique Substrings......Page 83 Summary......Page 84 Bibliographic notes......Page 85 Need for Better Construction Algorithms......Page 87 Need for Better Query Algorithms......Page 88 Bibliography......Page 89 Authors' Biographies......Page 93