9 citations · 29 across the 10 of their papers we have counts for
13 papers
Faster Privacy-Preserving Computation of Edit Distance with Moves
Yohei Yoshimoto, Masaharu Kataoka, Yoshimasa Takabatake +3
We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings and…
Practical Random Access to SLP-Compressed Texts
Travis Gagie, Tomohiro I, Giovanni Manzini +4
Grammar-based compression is a popular and powerful approach to compressing repetitive texts but until recently its relatively poor time-space trade-offs during real-life construct…
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…
Rpair: Rescaling RePair with Rsync
Travis Gagie, Tomohiro I, Giovanni Manzini +3
Data compression is a powerful tool for managing massive but repetitive datasets, especially schemes such as grammar-based compression that support computation over the data withou…
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…
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…
A Faster Implementation of Online Run-Length Burrows-Wheeler Transform
Tatsuya Ohno, Yoshimasa Takabatake, Tomohiro I +1
Run-length encoding Burrows-Wheeler Transformed strings, resulting in Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive strings. We propose a new algorith…
Online Grammar Compression for Frequent Pattern Discovery
Shouhei Fukunaga, Yoshimasa Takabatake, I Tomohiro +1
Various grammar compression algorithms have been proposed in the last decade. A grammar compression is a restricted CFG deriving the string deterministically. An efficient grammar…
siEDM: an efficient string index and search algorithm for edit distance with moves
Yoshimasa Takabatake, Kenta Nakashima, Tetsuji Kuboyama +2
Although several self-indexes for highly repetitive text collections exist, developing an index and search algorithm with editing operations remains a challenge. Edit distance with…
Online Self-Indexed Grammar Compression
Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto
Although several grammar-based self-indexes have been proposed thus far, their applicability is limited to offline settings where whole input texts are prepared, thus requiring to…
Online Pattern Matching for String Edit Distance with Moves
Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto
Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string to the other. Altho…
Improved ESP-index: a practical self-index for highly repetitive texts
Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto
While several self-indexes for highly repetitive texts exist, developing a practical self-index applicable to real world repetitive texts remains a challenge. ESP-index is a gramma…
A Succinct Grammar Compression
Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto
We solve an open problem related to an optimal encoding of a straight line program (SLP), a canonical form of grammar compression deriving a single string deterministically. We sho…