Grammar index by induced suffix sorting

DOI10.1007/978-3-030-86692-1_8OpenAlexW3203691570MaRDI QIDQ2146128

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

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

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

Related Items (1)

Sensitivity of string compressors and repetitiveness measures

Uses Software

• siEDM
• r-index

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• siEDM: an efficient string index and search algorithm for edit distance with moves
• Dynamic index and LZ factorization in compressed space
• ESP-index: a compressed index based on edit-sensitive parsing
• The string edit distance matching problem with moves
• Suffix Arrays: A New Method for On-Line String Searches
• Self-Indexed Grammar-Based Compression
• Universal codeword sets and representations of the integers
• Fast Pattern Matching in Strings
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Efficient Storage and Retrieval by Content and Address of Static Files
• Grammar-based codes: a new class of universal lossless source codes
• Optimal-Time Dictionary-Compressed Indexes
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Compressed text indexes
• On the sorting-complexity of suffix tree construction
• Deterministic Sparse Suffix Sorting in the Restore Model

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