Compact q-gram profiling of compressed strings

DOI10.1007/978-3-642-38905-4_8MaRDI QIDQ4928561zbMATH OpenOpenAlexWikidataFDO

Authors Philip Bille, Patrick Hagge Cording, Inge Li Gørtz

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.5373

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) Algorithms on strings (68W32)

Abstract: We consider the problem of computing the q-gram profile of a string str of size $N$ compressed by a context-free grammar with $n$ production rules. We present an algorithm that runs in $O(N-alpha)$ expected time and uses $O(n+q+kq)$ space, where $N-alphaleqqn$ is the exact number of characters decompressed by the algorithm and $kqleqN-alpha$ is the number of distinct q-grams in $str$. This simultaneously matches the current best known time bound and improves the best known space bound. Our space bound is asymptotically optimal in the sense that any algorithm storing the grammar and the q-gram profile must use $Omega(n+q+kq)$ space. To achieve this we introduce the q-gram graph that space-efficiently captures the structure of a string with respect to its q-grams, and show how to construct it from a grammar.

Recommendations

• Compact q-gram profiling of compressed strings
• Speeding up q-gram mining on grammar-based compressed texts
• Fast \(q\)-gram mining on SLP compressed strings
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts
• Access, rank, and select in grammar-compressed strings

Cited in

(5)

• Fast \(q\)-gram mining on SLP compressed strings
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts
• Speeding up q-gram mining on grammar-based compressed texts
• Compact q-gram profiling of compressed strings
• At the roots of dictionary compression: string attractors

This page was built for publication: Compact \(q\)-gram profiling of compressed strings

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