Dynamic index and LZ factorization in compressed space

DOI10.1016/j.dam.2019.01.014zbMath1434.68133arXiv1605.09558OpenAlexW2963012630WikidataQ128393012 ScholiaQ128393012MaRDI QIDQ2295634

Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Tomohiro I.

Publication date: 14 February 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

compressed data structuresdynamic data structuresLZ77 factorizationdynamic indexdynamic texts

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Related Items (6)

Grammar index by induced suffix sorting ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ A Self-index on Block Trees ⋮ Top tree compression of tries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Position heaps: a simple and dynamic text indexing data structure
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• LZ77 computation based on the run-length encoded BWT
• Lempel-Ziv factorization powered by space efficient suffix trees
• Dynamic extended suffix arrays
• Optimal bounds for the predecessor problem and related problems
• Efficient external memory structures for range-aggregate queries
• Compressed indexing with signature grammars
• Approximate pattern matching in LZ77-compressed texts
• ESP-index: a compressed index based on edit-sensitive parsing
• A Faster Grammar-Based Self-index
• Composite Repetition-Aware Data Structures
• Self-Indexed Grammar-Based Compression
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Range Predecessor and Lempel-Ziv Parsing
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• At the roots of dictionary compression: string attractors
• LZ77-Based Self-indexing with Faster Pattern Matching

This page was built for publication: Dynamic index and LZ factorization in compressed space