Grammar index by induced suffix sorting

DOI10.1007/978-3-030-86692-1_8MaRDI QIDQ2146128zbMATH OpenOpenAlexFDO

Authors Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 15 June 2022

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

zbMATH Keywords

grammar compressioninduced suffix sortinglocality sensitive parsingtext indexing data structure

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Sequentially Indexed Grammars
• scientific article; zbMATH DE number 3483585
• A descriptive characterisation of indexed grammars
• Sorted dependency insertion grammars
• A faster grammar-based self-index
• Grammatical Inference: Algorithms and Applications
• Indexed grammars and unification grammars
• Self-embedding indexed grammars
• The structure of index sets and reduced indexed grammars

Cites work

• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Compressed text indexes, from theory to practice
• Compression with the tudocomp framework
• Deterministic Sparse Suffix Sorting in the Restore Model
• Dynamic index and LZ factorization in compressed space
• Efficient Storage and Retrieval by Content and Address of Static Files
• ESP-index: a compressed index based on edit-sensitive parsing
• Fast Pattern Matching in Strings
• Grammar-based codes: a new class of universal lossless source codes
• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On the sorting-complexity of suffix tree construction
• Optimal-Time Dictionary-Compressed Indexes
• Self-indexed grammar-based compression
• siEDM: an efficient string index and search algorithm for edit distance with moves
• Suffix Arrays: A New Method for On-Line String Searches
• The string edit distance matching problem with moves
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Universal codeword sets and representations of the integers

Cited in

(1)

• Sensitivity of string compressors and repetitiveness measures

Describes a project that uses

Uses Software

• siEDM
• r-index

This page was built for publication: Grammar index by induced suffix sorting

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