15 citations · 21 across the 9 of their papers we have counts for
15 papers
Dynamic Grammar-Compressed Self-Index in -Optimal Space
Takaaki Nishimoto, Yasuo Tabei
A compressed self-index stores a string in compressed form while supporting locate queries without decompression. For highly repetitive strings, such as those arising in web crawls…
Dynamic r-index: An Updatable Self-Index in LCP-bounded Time
Takaaki Nishimoto, Yasuo Tabei
A self-index is a compressed data structure that supports locate queries -- reporting all positions where a given pattern occurs in a string while maintaining the string in compres…
Dynamic Suffix Array in Optimal Compressed Space
Takaaki Nishimoto, Yasuo Tabei
Big data, encompassing extensive datasets, has seen rapid expansion, notably with a considerable portion being textual data, including strings and texts. Simple compression methods…
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…
An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
Takaaki Nishimoto, Shunsuke Kanda, Yasuo Tabei
The compression of highly repetitive strings (i.e., strings with many repetitions) has been a central research topic in string processing, and quite a few compression methods for t…
A Separation of and via Thue--Morse Words
Hideo Bannai, Mitsuru Funakoshi, Tomohiro I +3
We prove that for , the size of the smallest bidirectional scheme for the th Thue--Morse word is . Since Kutsukake et al. [SPIRE 2020] show that the…
Optimal-Time Queries on BWT-runs Compressed Indexes
Takaaki Nishimoto, Yasuo Tabei
Indexing highly repetitive strings (i.e., strings with many repetitions) for fast queries has become a central research topic in string processing, because it has a wide variety of…
R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space
Takaaki Nishimoto, Yasuo Tabei
Enumerating characteristic substrings (e.g., maximal repeats, minimal unique substrings, and minimal absent words) in a given string has been an important research topic because th…
Conversion from RLBWT to LZ77
Takaaki Nishimoto, Yasuo Tabei
Converting a compressed format of a string into another compressed format without an explicit decompression is one of the central research topics in string processing. We discuss t…
LZRR: LZ77 Parsing with Right Reference
Takaaki Nishimoto, Yasuo Tabei
Lossless data compression has been widely studied in computer science. One of the most widely used lossless data compressions is Lempel-Zip(LZ) 77 parsing, which achieves a high co…
A compressed dynamic self-index for highly repetitive text collections
Takaaki Nishimoto, Yoshimasa Takabatake, Yasuo Tabei
We present a novel compressed dynamic self-index for highly repetitive text collections. Signature encoding is a compressed dynamic self-index for highly repetitive texts and has a…
Small-space encoding LCE data structure with constant-time queries
Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai +2
The \emph{longest common extension} (\emph{LCE}) problem is to preprocess a given string of length so that the length of the longest common prefix between suffixes of t…
Fully dynamic data structure for LCE queries in compressed space
Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga +2
A Longest Common Extension (LCE) query on a text of length asks for the length of the longest common prefix of suffixes starting at given two positions. We show that the si…
Dynamic index and LZ factorization in compressed space
Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga +2
In this paper, we propose a new \emph{dynamic compressed index} of space for a dynamic text , where is the size of the signature encodi…
Dynamic index, LZ factorization, and LCE queries in compressed space
Takaaki Nishimoto, I Tomohiro, Shunsuke Inenaga +2
In this paper, we present the following results: (1) We propose a new \emph{dynamic compressed index} of space, that supports searching for a pattern in the current text…