Time-space trade-offs for Lempel-Ziv compressed indexing

DOI10.1016/j.tcs.2017.12.021zbMath1386.68057arXiv1706.10094OpenAlexW2724271711MaRDI QIDQ1694685

Hjalte Wedel Vildhøj, Philip Bille, Inge Li Gørtz, Mikko Berggren Ettienne

Publication date: 6 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

pattern matchingprefix searchLZ77compressed indexing

Mathematics Subject Classification ID

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

Related Items (9)

Document listing on repetitive collections with guaranteed performance ⋮ Grammar-compressed indexes with logarithmic search time ⋮ String Indexing with Compressed Patterns ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Block trees ⋮ Universal compressed text indexing ⋮ Top tree compression of tries

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing and indexing repetitive sequences
• String matching in Lempel-Ziv compressed strings
• Lempel-Ziv index for \(q\)-grams
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Orthogonal Range Searching for Text Indexing
• Indexing Highly Repetitive Collections
• A Faster Grammar-Based Self-index
• Time-Space Trade-Offs for Longest Common Extensions
• Composite Repetition-Aware Data Structures
• Compressed representations of sequences and full-text indexes
• Real-Time Streaming String-Matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Indexing compressed text
• The Smallest Grammar Problem
• Fast Prefix Search in Little Space, with Applications
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Efficient randomized pattern-matching algorithms
• A universal algorithm for sequential data compression
• Exact and Approximate Pattern Matching in the Streaming Model
• Orthogonal range searching on the RAM, revisited
• LZ77-Based Self-indexing with Faster Pattern Matching

This page was built for publication: Time-space trade-offs for Lempel-Ziv compressed indexing