Speeding up q-gram mining on grammar-based compressed texts

DOI10.1007/978-3-642-31265-6_18MaRDI QIDQ2904495zbMATH OpenOpenAlexFDO

Authors Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Publication date 14 August 2012

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: We present an efficient algorithm for calculating $q$-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP $mathcalT$ of size $n$ that represents string $T$, the algorithm computes the occurrence frequencies of all $q$-grams in $T$, by reducing the problem to the weighted $q$-gram frequencies problem on a trie-like structure of size $m=|T|-mathitdup(q,mathcalT)$, where $mathitdup(q,mathcalT)$ is a quantity that represents the amount of redundancy that the SLP captures with respect to $q$-grams. The reduced problem can be solved in linear time. Since $m=O(qn)$, the running time of our algorithm is $O(min|T|-mathitdup(q,mathcalT),qn)$, improving our previous $O(qn)$ algorithm when $q=Omega(|T|/n)$.

Recommendations

• Fast \(q\)-gram mining on SLP compressed strings
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts
• Compact \(q\)-gram profiling of compressed strings
• Compact q-gram profiling of compressed strings
• Efficient LZ78 factorization of grammar compressed text

Cited in

(5)

• Compact q-gram profiling of compressed strings
• Compact \(q\)-gram profiling of compressed strings
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• Fast \(q\)-gram mining on SLP compressed strings
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts

This page was built for publication: Speeding up \(q\)-gram mining on grammar-based compressed texts

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