Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

DOI10.1137/1.9781611974782.26zbMath1410.68102arXiv1607.04346OpenAlexW2514119406MaRDI QIDQ4575763

Yakov Nekrich, J. Ian Munro, Gonzalo Navarro

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.04346

Mathematics Subject Classification ID

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

Related Items

Lyndon array construction during Burrows-Wheeler inversion, Engineering Practical Lempel-Ziv Tries, Algorithms to compute the Burrows-Wheeler similarity distribution, Unnamed Item, Space-efficient algorithms for computing minimal/shortest unique substrings, Space-efficient construction of compressed suffix trees, Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries, Fast compressed self-indexes with deterministic linear-time construction, Burrows-Wheeler transform and LCP array construction in constant space, A simple algorithm for computing the document array, Unnamed Item, Unnamed Item, Lempel-Ziv factorization powered by space efficient suffix trees, Parallel computation of the Burrows Wheeler transform in compact space, Lightweight merging of compressed indices based on BWT variants, Space-efficient computation of the LCP array from the Burrows-Wheeler transform, LZ-End Parsing in Linear Time, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction