zbMATH — the first resource for mathematics

Alphabet-independent compressed text indexing. (English) Zbl 1325.68307
Demetrescu, Camil (ed.) et al., Algorithms – ESA 2011. 19th annual European symposium, Saarbr├╝cken, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23718-8/pbk). Lecture Notes in Computer Science 6942, 748-759 (2011).
Summary: Self-indexes can represent a text in asymptotically optimal space under the \(k\)-th order entropy model, give access to text substrings, and support indexed pattern searches. Their time complexities are not optimal, however: they always depend on the alphabet size. In this paper we achieve, for the first time, full alphabet-independence in the time complexities of self-indexes, while retaining space optimality. We obtain also some relevant byproducts on compressed suffix trees.
Journal version in [ACM Trans. Algorithms 10, No. 4, Art. 23, 19 p. (2014; doi:10.1145/2635816)].
For the entire collection see [Zbl 1222.68007].

68W32 Algorithms on strings
68P05 Data structures
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Full Text: DOI