The Algorithm Design Manual Second Edition

Implementations

: There now exist a wealth of suffix array implementations avail-

able. Indeed, all of the recent linear time construction algorithms have been im-

plemented and benchmarked

[PST07

]. Sch¨

urmann and Stoye

[SS07

] provide an

excellent C implementation at http://bibiserv.techfak.uni-bielefeld.de/bpr/.

No less than eight different C/C++ implementations of compressed text indexes

appear at the Pizza&Chili corpus (http://pizzachili.di.unipi.it/). These data struc-

tures go to great lengths to minimize space usage, typically compressing the input

string to near the empirical entropy while still achieving excellent query times!

Suffix tree implementations are also readily available. A SuffixTree class is

provided in BioJava (ttp://www.biojava.org/)—an open source project providing

a Java framework for processing biological data. Libstree is a C implementa-

tion of Ukkonen’s algorithm, available at http://www.icir.org/christian/libstree/.

---

380

1 2 .

D A T A S T R U C T U R E S

Nelson’s C++ code

[Nel96]

is available from http://marknelson.us/1996/08/01/

suffix-trees/.

Strmat is a collection of C programs implementing exact pattern matching

algorithms in association with

[Gus97

], including an implementation of suffix trees.

It is available at http://www.cs.ucdavis.edu/

∼gusfield/strmat.html.

Notes

:

Tries were first proposed by Fredkin

[Fre62]

, the name coming from the cen-

tral letters of the word “retrieval.” A survey of basic trie data structures with extensive

references appears in

[GBY91]

.

Efficient algorithms for suffix tree construction are due to Weiner

[Wei73]

, McCreight

[McC76]

, and Ukkonen

[Ukk92]

. Good expositions on these algorithms include Crochmore

and Rytter

[CR03]

and Gusfield

[Gus97]

.

Suffix arrays were invented by Manber and Myers

[MM93]

, although an equivalent

idea called Pat trees due to Gonnet and Baeza-Yates appears in

[GBY91]

. Three teams

independently emerged with linear-time suffix array algorithms in 2003

[KSPP03, KA03,

KSB05]

, and progress has continued rapidly. See

[PST07]

for a recent survey covering all

these developments.

Recent work has resulted in the development of compressed full text indexes that offer

essentially all the power of suffix trees/arrays in a data structure whose size is proportional

to the compressed text string. Makinen and Navarro

[MN07]

survey these remarkable data

structures.

The power of suffix trees can be further augmented by using a data structure for

computing the least common ancestor (LCA) of any pair of nodes x, y in a tree in constant

time, after linear-time preprocessing of the tree. The original data structure due to Harel

and Tarjan

[HT84]

, has been progressively simplified by Schieber and Vishkin

[SV88]

and

later Bender and Farach

[BF00]

. Expositions include Gusfield

[Gus97]

. The least common

ancestor of two nodes in a suffix tree or trie defines the node representing the longest

common prefix of the two associated strings. That we can answer such queries in constant

time is amazing, and proves useful as a building block for many other algorithms.