Compressed data structures for strings. On searching and extracting strings from compressed textual data (Q383835): Difference between revisions

Every two years, the Italian chapter of the EATCS (European Association for Theoretical Computer Science) selects two Italian PhD theses to be published by Atlantis Press. This book is Rossano Venturini's thesis, which was understandably judged to be the best on algorithms, automata, complexity or game theory from 2010 to 2012. It contains results from five of the author's papers [\textit{P. Ferragina} et al., Lect. Notes Comput. Sci. 5757, 420--431 (2009; Zbl 1256.68055); \textit{P. Ferragina} et al., SIAM J. Comput. 42, No. 4, 1521--1541 (2013; Zbl 1276.68069); \textit{P. Ferragina} and \textit{R. Venturini}, Theor. Comput. Sci. 372, No. 1, 115--121 (2007; Zbl 1110.68029); \textit{P. Ferragina} et al., ACM J. Exp. Algorithm. 13, Article No. 1.12, 31 p. (2009; Zbl 1284.68255); \textit{P. Ferragina} and \textit{R. Venturini}, ACM Trans. Algorithms 7, No. 1, Paper No. 10, 21 p. (2010; Zbl 1295.68108)]. Although the book focuses on the problems addressed and solutions offered in these papers -- and thus should probably not be considered as a regular textbook -- Chapters 2 and 6 in particular provide a brief but insightful introduction to the theory and practice of compressed data structures for strings. It could serve as an excellent example thesis and source of research topics for other PhD students, although they should still of course check work done since it was written: e.g., the problem of linear-time BWT construction with \(O(n \log \sigma)\) bits of auxiliary space has now been solved by \textit{D. Belazzougui} [``Linear time construction of compressed text indices in compact space'', in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14. New York, NY: ACM Press. 148--193 (2014; \url{doi:10.1145/2591796.2591885})], and SDSL (Succinct Data Structure Library, \url{https://github.com/simongog/sdsl-lite}) has probably replaced the Pizza \& Chili website as the main repository of implementations.