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

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

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

(25)

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

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)