2012/01/01 by Keisuke Goto, Hideo Bannai, Shunsuke Inenaga +1 · 6 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Compressed sensing #Data compression #Efficient algorithm #Line (geometry) #Redundancy (engineering) #String (physics) #Time complexity #cs.DS #semigroups and automata theory
paper · pdf · doi:10.1007/978-3-642-31265-6_18
published in Lecture notes in computer science, 220-231 (Springer Science+Business Media)
openalex publication_date 2012/01/01 · arxiv created 2012/02/15 · arxiv updated 2013/05/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 = |T|-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(min\|T|-dup(q,T),qn\), improving our previous O(qn) algorithm when q = Ω(|T|/n).