24 citations · 60 across the 10 of their papers we have counts for
6 papers · 1 filter
Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga +2
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string of length has nodes and edges, and the stri…
Online Algorithms for Constructing Linear-size Suffix Trie
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string of length has nodes and edges, and the string la…
MR-RePair: Grammar Compression based on Maximal Repeats
Isamu Furuya, Takuya Takagi, Yuto Nakashima +3
We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePa…
Linear-size CDAWG: new repetition-aware indexing and grammar compression
Takuya Takagi, Keisuke Goto, Yuta Fujishige +2
In this paper, we propose a novel approach to combine \emph{compact directed acyclic word graphs} (CDAWGs) and grammar-based compression. This leads us to an efficient self-index,…
Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane +1
In this paper, we present a new data structure called the packed compact trie (packed c-trie) which stores a set of strings of total length in bi…
Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura +2
We consider construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection of texts, where a new symbol may be a…