Random access to grammar-compressed strings

MaRDI QIDQ5365049zbMATH OpenFDO

Authors Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133066

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Recommendations

• Random access to grammar-compressed strings and trees
• Access, rank, and select in grammar-compressed strings
• Finger Search in Grammar-Compressed Strings
• Finger search in grammar-compressed strings
• Data structure lower bounds on random access to grammar-compressed strings

Cited in

(26)

• Bookmarks in grammar-compressed strings
• The complexity of compressed membership problems for finite automata
• Finger search in grammar-compressed strings
• Approximate pattern matching in LZ77-compressed texts
• Compressed automata for dictionary matching
• Tree compression with top trees
• Block graphs in practice
• Fast relative Lempel-Ziv self-index for similar sequences
• Detecting regularities on grammar-compressed strings
• XML compression via directed acyclic graphs
• Compressed matching for feature vectors
• Towards approximate matching in compressed strings: local subsequence recognition
• Access, rank, and select in grammar-compressed strings
• Colored range queries and document retrieval
• On compressing and indexing repetitive sequences
• Finger Search in Grammar-Compressed Strings
• Data structure lower bounds on random access to grammar-compressed strings
• Succinct color searching in one dimension
• Pattern matching on elastic-degenerate text with errors
• Random access to grammar-compressed strings and trees
• Faster compressed suffix trees for repetitive collections
• Dynamic Compressed Strings with Random Access
• Automata, Languages and Programming
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Practical Random Access to SLP-Compressed Texts
• Memoization on shared subtrees accelerates computations on genealogical forests

This page was built for publication: Random access to grammar-compressed strings

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