Space-efficient construction of compressed indexes in deterministic linear time

DOI10.1137/1.9781611974782.26zbMATH Open1410.68102arXiv1607.04346OpenAlexW2514119406MaRDI QIDQ4575763FDOQ4575763

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)

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.

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

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

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)

Cited In (21)

• Fast compressed self-indexes with deterministic linear-time construction
• Optimal indexes for sparse bit vectors
• Title not available (Why is that?)
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• External memory BWT and LCP computation for sequence collections with applications
• Lightweight merging of compressed indices based on BWT variants
• A simple algorithm for computing the document array
• 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
• Title not available (Why is that?)
• 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)