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

DOI10.1007/978-3-030-86692-1_9MaRDI QIDQ2146131zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Self-embedding indexed grammars
• A faster grammar-based self-index
• A descriptive characterisation of indexed grammars
• scientific article; zbMATH DE number 3483585
• A local search algorithm for grammatical inference
• Indexed grammars and unification grammars
• scientific article; zbMATH DE number 3924162
• Sequentially Indexed Grammars
• scientific article; zbMATH DE number 1904851
• A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars

Cites work

• A universal algorithm for sequential data compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• At the roots of dictionary compression: string attractors
• Efficient construction of a complete index for pan-genomics read alignment
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Grammar-based codes: a new class of universal lossless source codes
• Grammar-compressed indexes with logarithmic search time
• Inducing enhanced suffix arrays for string collections
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On compressing and indexing repetitive sequences
• Optimal-Time Dictionary-Compressed Indexes
• Orthogonal range searching on the RAM, revisited
• Random access to grammar-compressed strings and trees
• Self-indexed grammar-based compression
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• The Smallest Grammar Problem

Cited in

(2)

• Sensitivity of string compressors and repetitiveness measures
• Computing MEMs and relatives on repetitive text collections

Describes a project that uses

Uses Software

• Big-BWT

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2146131)