Speeding-up $q$-gram mining on grammar-based compressed texts
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Hideo Bannai, 英夫 坂内, Hideo Bannai, Shunsuke Inenaga, Shunsuke Inenaga, Shunsuke Inenaga, Masayuki Takeda, Masayuki Takeda, Masayuki Takeda · Institutional Repositories DataBase (IRDB) · 2012
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 T 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 = jT j dup(q; T), where dup(q; T) 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(minfjT jdup(q; T); qng), improving our previous O(qn) algorithm when q = Ω(jT j=n). 1