Optimal Construction of Compressed Indexes for Highly Repetitive Texts

DOI10.1137/1.9781611975482.82zbMath1431.68172arXiv1712.04886OpenAlexW2952899751MaRDI QIDQ5236266

Dominik Kempa

Publication date: 15 October 2019

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

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

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

Novel results on the number of runs of the Burrows-Wheeler-transform, Efficient construction of the BWT for repetitive text using string compression, Unnamed Item, Space-efficient algorithms for computing minimal/shortest unique substrings, Block trees, Unnamed Item, Refining the \(r\)-index