Space-efficient construction of compressed indexes in deterministic linear time

DOI10.1137/1.9781611974782.26MaRDI QIDQ4575763zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Yakov Nekrich, 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) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: We show that the compressed suffix array and the compressed suffix tree of a string $T$ can be built in $O(n)$ deterministic time using $O(nlogsigma)$ bits of space, where $n$ is the string length and $sigma$ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need $omega(nlogsigma)$ bits of working space. Our result has immediate applications to other problems, such as yielding the first linear-time LZ77 and LZ78 parsing algorithms that use $O(nlogsigma)$ bits.

Recommendations

• Linear time construction of compressed text indices in compact space
• Fast compressed self-indexes with deterministic linear-time construction
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Combinatorial Pattern Matching
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space

Cited in

(21)

• Optimal indexes for sparse bit vectors
• Fast compressed self-indexes with deterministic linear-time construction
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Lightweight merging of compressed indices based on BWT variants
• A simple algorithm for computing the document array
• External memory BWT and LCP computation for sequence collections with applications
• Lempel-Ziv factorization powered by space efficient suffix trees
• Lyndon array construction during Burrows-Wheeler inversion
• Algorithms to compute the Burrows-Wheeler similarity distribution
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Engineering practical Lempel-Ziv tries
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• Space-efficient construction of compressed suffix trees
• scientific article; zbMATH DE number 7378722 (Why is no real title available?)
• Parallel computation of the Burrows Wheeler transform in compact space
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Linear time construction of compressed text indices in compact space
• Burrows-Wheeler transform and LCP array construction in constant space
• LZ-End Parsing in Linear Time
• Space-efficient algorithms for computing minimal/shortest unique substrings

This page was built for publication: Space-efficient construction of compressed indexes in deterministic linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575763)