5 citations · 9 across the 6 of their papers we have counts for
7 papers · 1 filter
Detecting regularities on grammar-compressed strings
Tomohiro I, Wataru Matsubara, Kouji Shimohira +5
We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size that represents a s…
Efficient Lyndon factorization of grammar compressed text
Tomohiro I, Yuto Nakashima, Shunsuke Inenaga +2
We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in $O…
Computing convolution on grammar-compressed text
Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga +2
The convolution between a text string of length and a pattern string of length can be computed in time by FFT. It is known that various types of appro…
Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga +1
Length- substrings, or -grams, can represent important characteristics of text data, and determining the frequencies of all -grams contained in the data is an important pr…
Computing q-gram Frequencies on Collage Systems
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga +1
Collage systems are a general framework for representing outputs of various text compression algorithms. We consider the all -gram frequency problem on compressed string represe…
Restructuring Compressed Texts without Explicit Decompression
Keisuke Goto, Shirou Maruyama, Shunsuke Inenaga +3
We consider the problem of {\em restructuring} compressed texts without explicit decompression. We present algorithms which allow conversions from compressed representations of a s…