I. Tomohiro

activity

20132022

most citedComputing convolution on grammar-compressed text

2 citations · 4 across the 5 of their papers we have counts for

collaborators

Showing cs.DSShow all

8 papers · 1 filter

cs.DS2022

Substring Complexities on Run-length Compressed Strings

Akiyoshi Kawamoto, Tomohiro I

Let $S_{T} (k)$ denote the set of distinct substrings of length $k$ in a string $T$ , then the $k$ -th substring complexity is defined by its cardinality $∣ S_{T} (k) ∣$ . Recently, $δ= \…

cs.DS2022★ 1 cited

Longest (Sub-)Periodic Subsequence

Hideo Bannai, Tomohiro I, Dominik Köppl

We present an algorithm computing the longest periodic subsequence of a string of length $n$ in $O (n^{7})$ time with $O (n^{4})$ words of space. We obtain improvements when restricting…

cs.DS2022

Computing Longest (Common) Lyndon Subsequences

Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2

Given a string $T$ with length $n$ whose characters are drawn from an ordered alphabet of size $σ$ , its longest Lyndon subsequence is a longest subsequence of $T$ that is a Lyndon…

cs.DS2021★ 1 cited

Load-Balancing Succinct B Trees

Tomohiro I, Dominik Köppl

We propose a B tree representation storing $n$ keys, each of $k$ bits, in either (a) $nk + O (nk / l g n)$ bits or (b) $nk + O (nk l g l g n / l g n)$ bits of space supporting all B t…

cs.DS2020

PHONI: Streamed Matching Statistics with Multi-Genome References

Christina Boucher, Travis Gagie, Tomohiro I +6

Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic data…

cs.DS2019

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…