An LMS-based grammar self-index with local consistency properties

DOI10.1007/978-3-030-86692-1_9OpenAlexW3202930113MaRDI QIDQ2146131

Gonzalo Navarro, Alejandro Pacheco, Diego Díaz-Domínguez

Publication date: 15 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86692-1_9

zbMATH Keywords

grammar compressionLMS-substringslocally consistent parsing

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Information storage and retrieval of data (68P20)

Related Items (1)

Sensitivity of string compressors and repetitiveness measures

Uses Software

• Big-BWT

Cites Work

• On compressing and indexing repetitive sequences
• Inducing enhanced suffix arrays for string collections
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Efficient construction of a complete index for pan-genomics read alignment
• Grammar-compressed indexes with logarithmic search time
• Self-Indexed Grammar-Based Compression
• The Smallest Grammar Problem
• A universal algorithm for sequential data compression
• Grammar-based codes: a new class of universal lossless source codes
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Optimal-Time Dictionary-Compressed Indexes
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• At the roots of dictionary compression: string attractors
• Random Access to Grammar-Compressed Strings and Trees
• Orthogonal range searching on the RAM, revisited

This page was built for publication: An LMS-based grammar self-index with local consistency properties