Efficient Text Representation and Search

Table of Contents
About the Author
About the Technical Reviewer
Chapter 1: Introduction
	Notation and conventions
	Graphical notation
	Code conventions
	Reporting a sequence of results
Chapter 2: Classical algorithms for exact search
	Naïve algorithm
	Border array and border search
	Borders and border arrays
	Exact search using borders
	Knuth-Morris-Pratt
	Boyer-Moore-Horspool
	Extended rightmost table
	Boyer-Moore
		Jump rule one
			Computing the Z array
			Z-based jump table
		Second jump table
		Combining the jump rules
	Aho-Corasick
		Tries
			Preprocessing
			The algorithm with iterators
	Comparisons
Chapter 3: Suffix trees
	Compacted trie and suffix representation
	Naïve construction algorithm
	Suffix trees and the SA and LCP arrays
		Constructing the SA and LCP arrays
		Constructing the suffix tree from the SA and LCP arrays
	McCreight’s algorithm
	Searching with suffix trees
		Leaf iterators
	Comparisons
Chapter 4: Suffix arrays
	Constructing suffix arrays
		Trivial constructions—Comparison-based sorting
		The skew algorithm
			Constructing SA3
			Recursively sorting sa12
			Merging arrays
			Construction function
	The SA-IS algorithm
		Remapping
		Implementing the algorithm
		Memory reduction
	Searching using suffix arrays
		Binary search
		Burrows-Wheeler transform–based search
			C and O tables
			Building the C and O tables
			Searching
	Getting the longest common prefix (LCP) array
	Comparisons
Chapter 5: Approximate search
	Local alignment and CIGAR notation
	Brute force approach
		Building an edit cloud
	Suffix trees
	The Li-Durbin algorithm
	Comparisons
Chapter 6: Conclusions
Appendix:
Fundamental data structures
	Vectors
	Lists
	Queues
Index