Udi Manber, Gene Myers, and the Suffix Array: Compact Full-Text Indexing
Udi Manber and Gene Myers introduced suffix arrays as a conceptually simple, space-efficient alternative to suffix trees, turning substring search into a sorted-index problem with major consequences for text processing and bioinformatics.
Substring search becomes difficult when the text is large and queries repeat
Scanning an entire text for every pattern is reasonable for a one-off query, but repeated searches invite preprocessing. The challenge is to build an index that accelerates later queries without consuming so much space that the index becomes harder to store than the text itself.
Suffix-based indexing attacks the problem by representing every possible starting position in the text.
Suffix trees showed the power of indexing every suffix
By the 1970s, suffix-tree techniques could support strong substring-search bounds, and Edward McCreight’s 1976 work gave a space-economical linear-time construction algorithm for a suffix tree.[1]
But pointer-rich trees can carry substantial constant-factor memory overhead, especially when the text is large.
The theoretical optimum can still be an awkward physical representation
A tree may have excellent asymptotic bounds while requiring nodes, edges, labels and pointers that fragment memory. This gap between abstract complexity and representation cost created room for a different index.
Manber and Myers introduced the suffix array around 1990
Udi Manber and Gene Myers presented “Suffix Arrays: A New Method for On-Line String Searches” at the first ACM-SIAM Symposium on Discrete Algorithms in 1990.[2] The expanded journal version appeared in SIAM Journal on Computing in 1993.[3]
The paper explicitly introduced the suffix array as a new, conceptually simple data structure for online string searches.
The data structure stores positions rather than explicit suffix strings
A suffix array is an array of starting offsets ordered by the lexicographic order of the suffixes beginning at those offsets. The text remains stored once; the array records how its suffixes are ordered.
Sorted suffixes reduce substring search to ordered comparison
All suffixes that begin with a query pattern appear contiguously in lexicographic order. A search can therefore use binary-search-style comparisons to locate the relevant range.
The journal paper gives a query bound of O(P + log N) in its described method, where P is the pattern length and N the text length.[3]
Space efficiency was the headline advantage over suffix trees
Manber and Myers reported that suffix arrays used substantially less space in practice than suffix trees, describing a three-to-five-times advantage in their setting.[3] Independent bibliographic summaries repeat that comparison and the paper’s expectation that arrays would be preferable in many applications.[4]
The saving comes from replacing a graph of heap objects and links with a dense ordered array of integer positions.
Dense arrays also interact well with memory hierarchy
Contiguous storage is friendly to caches and sequential scans. This systems advantage is not fully captured by big-O notation, but it became increasingly important as processor speed grew faster than memory latency.
Construction algorithms became a research field of their own
The original work described O(N log N) worst-case construction in its principal formulation and an expected-linear alternative with different space tradeoffs.[3] Later algorithms improved suffix-array construction substantially, including linear-work approaches such as the difference-cover method of Kärkkäinen and Sanders.[5]
Once the representation became important, building it efficiently across alphabets, memory models and data sizes became a major algorithmic problem.
The index invited auxiliary structures rather than remaining a single array
Longest-common-prefix arrays, compressed suffix arrays and related structures extend the basic ordering with information that speeds richer string operations or reduces memory further.
Suffix arrays became important in text and biological sequence processing
Full-text search, compression, repeated-substring analysis and genome-scale sequence processing all benefit from efficient ordering of suffixes. The method’s appeal is that a simple primitive—sort starting positions by suffix—supports a surprisingly broad set of queries.
The concept also became a foundation for later compressed indexes and Burrows-Wheeler-transform-based techniques.
Why suffix arrays belong in the CodeHistory timeline
Manber and Myers showed that an algorithmic breakthrough can come from changing representation rather than changing the underlying information. Their suffix array preserved the search power of suffix ordering while replacing a complex tree with a compact sorted index.[2][3]
The lasting lesson is one that recurs across systems history: asymptotic complexity matters, but the shape in which data is stored can determine whether an elegant algorithm becomes a practical one.
Works Cited
- 01
- 02
- 03
- 04
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead