2 citations · 3 across the 4 of their papers we have counts for
6 papers · 1 filter
Re-Pair In Small Space
Dominik Köppl, Tomohiro I, Isamu Furuya +3
Re-Pair is a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it…
RePair in Compressed Space and Time
Kensuke Sakai, Tatsuya Ohno, Keisuke Goto +3
Given a string of length , the goal of grammar compression is to construct a small context-free grammar generating only . Among existing grammar compression methods, RePa…
Refining the -index
Hideo Bannai, Travis Gagie, Tomohiro I
Gagie, Navarro and Prezza's -index (SODA, 2018) promises to speed up DNA alignment and variation calling by allowing us to index entire genomic databases, provided certain obsta…
Lempel Ziv Computation In Small Space (LZ-CISS)
Johannes Fischer, Tomohiro I, Dominik Köppl
For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using bits (for any positive constant …
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…