A Faster Grammar-Based Self-index

DOI10.1007/978-3-642-28332-1_21zbMath1351.68089arXiv1109.3954OpenAlexW2141931308MaRDI QIDQ2890196

Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, Simon J. Puglisi, Travis Gagie

Publication date: 8 June 2012

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (21)

Document listing on repetitive collections with guaranteed performance ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ Fingerprints in compressed strings ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Universal compressed text indexing ⋮ On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation ⋮ A Self-index on Block Trees ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Dynamic index and LZ factorization in compressed space ⋮ Top tree compression of tries ⋮ Finger search in grammar-compressed strings ⋮ A Space-Optimal Grammar Compression. ⋮ LZ-End Parsing in Linear Time ⋮ Orthogonal Range Searching for Text Indexing ⋮ Approximate pattern matching in LZ77-compressed texts ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Faster Compressed Suffix Trees for Repetitive Collections

This page was built for publication: A Faster Grammar-Based Self-index