Sux Trees: A Survey, and Future Challenges
Mark Daniel Ward · 2010
Sux trees are one of the most fundamental structures for data compression and pattern matching algorithms. They are retrieval trees (a.k.a. tries) built from the suxes of a string (i.e., a data sequence). A rich combinatorial theory about overlapping strings has been known and utilized for three decades. Some of the combinatorial methods of analysis have been extended, to encompass sux trees built over random strings whose distribution follows a Bernoulli model or a Markov model. Many opportunities exist for an extended, robust theory to much richer stochastic models that are applicable in practice, such as high-order Markov models and Hidden Markov Models. We will survey some recent results about sux trees, derived by analytic, combinatorial, and probabilistic analysis in tandem. We will also outline some challenges for the future analysis of sux