A succinct grammar compression

DOI10.1007/978-3-642-38905-4_23MaRDI QIDQ4928576zbMATH OpenOpenAlexFDO

Authors Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Abstract: We solve an open problem related to an optimal encoding of a straight line program (SLP), a canonical form of grammar compression deriving a single string deterministically. We show that an information-theoretic lower bound for representing an SLP with n symbols requires at least 2n+logn!+o(n) bits. We then present a succinct representation of an SLP; this representation is asymptotically equivalent to the lower bound. The space is at most 2n log {rho}(1 + o(1)) bits for rho leq 2sqrt{n}, while supporting random access to any production rule of an SLP in O(log log n) time. In addition, we present a novel dynamic data structure associating a digram with a unique symbol. Such a data structure is called a naming function and has been implemented using a hash table that has a space-time tradeoff. Thus, the memory space is mainly occupied by the hash table during the development of production rules. Alternatively, we build a dynamic data structure for the naming function by leveraging the idea behind the wavelet tree. The space is strictly bounded by 2n log n(1 + o(1)) bits, while supporting O(log n) query and update time.

Recommendations

• A space-optimal grammar compression
• Self-indexed Text Compression Using Straight-Line Programs
• String Processing and Information Retrieval
• Self-indexed grammar-based compression
• Access, rank, and select in grammar-compressed strings

Cited in

(9)

• siEDM: an efficient string index and search algorithm for edit distance with moves
• Grammar compressed sequences with rank/select support
• Self-indexed Text Compression Using Straight-Line Programs
• Using static suffix array in dynamic application: case of text compression by longest first substitution
• A space-optimal grammar compression
• Faster compressed suffix trees for repetitive collections
• Fully-Online Grammar Compression
• Space-efficient SLP encoding for O( N)-time random access
• Re^2Pair: increasing the scalability of repair by decreasing memory usage

This page was built for publication: A succinct grammar compression

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