BZPEER

preprint2026arXiv

Space-efficient SLP encoding for $O(\log N)$ -time random access

A Straight-Line Program (SLP) $G$ for a string $T$ is a context-free grammar (CFG) that derives $T$ only, which can be considered as a compressed representation of $T$ . In this paper, we show how to encode $G$ in $n \lceil \lg N \rceil + (n + n') \lceil \lg (n+σ) \rceil + 4n - 2n' + o(n)$ bits to support random access queries of extracting $T[p..q]$ in worst-case $O(\log N + q - p)$ time, where $N$ is the length of $T$ , $σ$ is the alphabet size, $n$ is the number of variables in $G$ and $n' \le n$ is the number of symmetric centroid paths in the DAG representation for $G$ . The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that $O(\log N)$ term cannot be significantly improved in general with $\mathrm{poly}(n)$ -space data structures. We also present alternative encodings that achieve the same random access time with $n \lceil \lg N \rceil + n \lceil \lg (n+σ) \rceil + 5n + n' + o(n)$ or $n \lceil \lg N \rceil + n \lceil \lg (n+σ) \rceil + 5n - n' + σ+ o(n+σ)$ bits of space.

preprint2022arXiv

Computing Longest (Common) Lyndon Subsequences

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 word. We propose algorithms for finding such a subsequence in $O(n^3)$ time with $O(n)$ space, or online in $O(n^3 σ)$ space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length $n$ in $O(n^4 σ)$ time using $O(n^3)$ space.

preprint2022arXiv

Longest (Sub-)Periodic Subsequence

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 the exponents or extending the search allowing the reported subsequence to be subperiodic down to $O(n^3)$ time and $O(n^2)$ words of space.

preprint2022arXiv

Substring Complexities on Run-length Compressed Strings

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, $δ= \max \{ |S_{T}(k)| / k : k \ge 1 \}$ is shown to be a good compressibility measure of highly-repetitive strings. In this paper, given $T$ of length $n$ in the run-length compressed form of size $r$ , we show that $δ$ can be computed in $\mathit{C}_{\mathsf{sort}}(r, n)$ time and $O(r)$ space, where $\mathit{C}_{\mathsf{sort}}(r, n) = O(\min (r \lg\lg r, r \lg_{r} n))$ is the time complexity for sorting $r$ $O(\lg n)$ -bit integers in $O(r)$ space in the Word-RAM model with word size $Ω(\lg n)$ .

preprint2021arXiv

PHONI: Streamed Matching Statistics with Multi-Genome References

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 database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database.

preprint2020arXiv

Practical Random Access to SLP-Compressed Texts

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 construction made it impractical for truly massive datasets such as genomic databases. In a recent paper (SPIRE 2019) we showed how simple pre-processing can dramatically improve those trade-offs, and in this paper we turn our attention to one of the features that make grammar-based compression so attractive: the possibility of supporting fast random access. This is an essential primitive in many algorithms that process grammar-compressed texts without decompressing them and so many theoretical bounds have been published about it, but experimentation has lagged behind. We give a new encoding of grammars that is about as small as the practical state of the art (Maruyama et al., SPIRE 2013) but with significantly faster queries.

preprint2016arXiv

Deterministic sub-linear space LCE data structures with efficient construction

Given a string $S$ of $n$ symbols, a longest common extension query $\mathsf{LCE}(i,j)$ asks for the length of the longest common prefix of the $i$ th and $j$ th suffixes of $S$ . LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015: 65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and query time. In particular, for a parameter $1 \leq τ\leq n$ , their best deterministic solution is a data structure of size $O(n/τ)$ which allows LCE queries to be answered in $O(τ)$ time. However, the construction time for all deterministic versions of their data structure is quadratic in $n$ . In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of $O(τ\min\{\logτ,\log\frac{n}τ\})$ query time using $O(n/τ)$ space, but significantly improve the construction time to $O(nτ)$ .

preprint2016arXiv

Dynamic index and LZ factorization in compressed space

In this paper, we propose a new \emph{dynamic compressed index} of $O(w)$ space for a dynamic text $T$ , where $w = O(\min(z \log N \log^*M, N))$ is the size of the signature encoding of $T$ , $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$ , $N$ is the length of $T$ , and $M \geq 3N$ is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern $P$ in $T$ in $O(|P| f_{\mathcal{A}} + \log w \log |P| \log^* M (\log N + \log |P| \log^* M) + \mathit{occ} \log N)$ time and insertion/deletion of a substring of length $y$ in $O((y+ \log N\log^* M)\log w \log N \log^* M)$ time, where $f_{\mathcal{A}} = O(\min \{ \frac{\log\log M \log\log w}{\log\log\log M}, \sqrt{\frac{\log w}{\log\log w}} \})$ . Also, we propose a new space-efficient LZ77 factorization algorithm for a given text of length $N$ , which runs in $O(N f_{\mathcal{A}} + z \log w \log^3 N (\log^* N)^2)$ time with $O(w)$ working space.

preprint2016arXiv

Fully dynamic data structure for LCE queries in compressed space

A Longest Common Extension (LCE) query on a text $T$ of length $N$ asks for the length of the longest common prefix of suffixes starting at given two positions. We show that the signature encoding $\mathcal{G}$ of size $w = O(\min(z \log N \log^* M, N))$ [Mehlhorn et al., Algorithmica 17(2):183-198, 1997] of $T$ , which can be seen as a compressed representation of $T$ , has a capability to support LCE queries in $O(\log N + \log \ell \log^* M)$ time, where $\ell$ is the answer to the query, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$ , and $M \geq 4N$ is an integer that can be handled in constant time under word RAM model. In compressed space, this is the fastest deterministic LCE data structure in many cases. Moreover, $\mathcal{G}$ can be enhanced to support efficient update operations: After processing $\mathcal{G}$ in $O(w f_{\mathcal{A}})$ time, we can insert/delete any (sub)string of length $y$ into/from an arbitrary position of $T$ in $O((y+ \log N\log^* M) f_{\mathcal{A}})$ time, where $f_{\mathcal{A}} = O(\min \{ \frac{\log\log M \log\log w}{\log\log\log M}, \sqrt{\frac{\log w}{\log\log w}} \})$ . This yields the first fully dynamic LCE data structure. We also present efficient construction algorithms from various types of inputs: We can construct $\mathcal{G}$ in $O(N f_{\mathcal{A}})$ time from uncompressed string $T$ ; in $O(n \log\log n \log N \log^* M)$ time from grammar-compressed string $T$ represented by a straight-line program of size $n$ ; and in $O(z f_{\mathcal{A}} \log N \log^* M)$ time from LZ77-compressed string $T$ with $z$ factors. On top of the above contributions, we show several applications of our data structures which improve previous best known results on grammar-compressed string processing.

preprint2016arXiv

Longest Common Extensions with Recompression

Given two positions $i$ and $j$ in a string $T$ of length $N$ , a longest common extension (LCE) query asks for the length of the longest common prefix between suffixes beginning at $i$ and $j$ . A compressed LCE data structure is a data structure that stores $T$ in a compressed form while supporting fast LCE queries. In this article we show that the recompression technique is a powerful tool for compressed LCE data structures. We present a new compressed LCE data structure of size $O(z \lg (N/z))$ that supports LCE queries in $O(\lg N)$ time, where $z$ is the size of Lempel-Ziv 77 factorization without self-reference of $T$ . Given $T$ as an uncompressed form, we show how to build our data structure in $O(N)$ time and space. Given $T$ as a grammar compressed form, i.e., an straight-line program of size n generating $T$ , we show how to build our data structure in $O(n \lg (N/n))$ time and $O(n + z \lg (N/z))$ space. Our algorithms are deterministic and always return correct answers.

preprint2015arXiv

Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets

We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marked ancestor queries on the suffix tree of the given string. We also show that the same technique can be used to construct the position heap of a set of strings in worst-case linear time, when the set of strings is given as a trie.

preprint2015arXiv

Efficiently Finding All Maximal $α$ -gapped Repeats

For $α\geq 1$ , an $α$ -gapped repeat in a word $w$ is a factor $uvu$ of $w$ such that $|uv|\leq α|u|$ ; the two factors $u$ in such a repeat are called arms, while the factor $v$ is called gap. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right or, respectively, to the left. In this paper we show that the number of maximal $α$ -gapped repeats that may occur in a word is upper bounded by $18αn$ . This allows us to construct an algorithm finding all the maximal $α$ -gapped repeats of a word in $O(αn)$ ; this is optimal, in the worst case, as there are words that have $Θ(αn)$ maximal $α$ -gapped repeats. Our techniques can be extended to get comparable results in the case of $α$ -gapped palindromes, i.e., factors $uvu^\mathrm{T}$ with $|uv|\leq α|u|$ .

preprint2015arXiv

Lempel Ziv Computation In Small Space (LZ-CISS)

For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using $(1+ε) n \lg n + O(n)$ bits (for any positive constant $ε\le 1$ ) working space (including the space for the output) for any text of size \$n\$ over an integer alphabet in $O(n / ε^{2})$ time.

preprint2013arXiv

Computing convolution on grammar-compressed text

The convolution between a text string $S$ of length $N$ and a pattern string $P$ of length $m$ can be computed in $O(N \log m)$ time by FFT. It is known that various types of approximate string matching problems are reducible to convolution. In this paper, we assume that the input text string is given in a compressed form, as a \emph{straight-line program (SLP)}, which is a context free grammar in the Chomsky normal form that derives a single string. Given an SLP $\mathcal{S}$ of size $n$ describing a text $S$ of length $N$ , and an uncompressed pattern $P$ of length $m$ , we present a simple $O(nm \log m)$ -time algorithm to compute the convolution between $S$ and $P$ . We then show that this can be improved to $O(\min\{nm, N-α\} \log m)$ time, where $α\geq 0$ is a value that represents the amount of redundancy that the SLP captures with respect to the length- $m$ substrings. The key of the improvement is our new algorithm that computes the convolution between a trie of size $r$ and a pattern string $P$ of length $m$ in $O(r \log m)$ time.

preprint2013arXiv

Detecting regularities on grammar-compressed strings

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 $n$ that represents a string $s$ of length $N$ , our algorithm compute all runs and squares in $s$ in $O(n^3h)$ time and $O(n^2)$ space, where $h$ is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in $O(n^3h + gnh\log N)$ time and $O(n^2)$ space, where $g$ is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in $O(n^2 h)$ time and $O(nh(n+\log^2 N))$ time, respectively.

preprint2013arXiv

Efficient Lyndon factorization of grammar compressed text

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(n^4 + mn^3h)$ time and $O(n^2)$ space, where $m$ is the size of the Lyndon factorization, $n$ is the size of the SLP, and $h$ is the height of the derivation tree of the SLP. Since the length of the decompressed string can be exponentially large w.r.t. $n, m$ and $h$ , our result is the first polynomial time solution when the string is given as SLP.

preprint2013arXiv

Faster Compact On-Line Lempel-Ziv Factorization

We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in $O(N\log N)$ time and uses only $O(N\logσ)$ bits of working space, where $N$ is the length of the string and $σ$ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either $O(N\log^3N)$ time (Okanohara & Sadakane 2009) or $O(N\log^2N)$ time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size $m$ of a string of length $N$ , computes the Lempel-Ziv factorization on-line, in $O\left(m \cdot \min \left\{\frac{(\log\log m)(\log \log N)}{\log\log\log N}, \sqrt{\frac{\log m}{\log \log m}} \right\}\right)$ time and $O(m\log N)$ bits of space, which is faster and more space efficient when the string is run-length compressible.

Tomohiro I

Research overview

Is this your work?

17 publications

Space-efficient SLP encoding for $O(\log N)$ -time random access

Computing Longest (Common) Lyndon Subsequences

Longest (Sub-)Periodic Subsequence

Substring Complexities on Run-length Compressed Strings

PHONI: Streamed Matching Statistics with Multi-Genome References

Practical Random Access to SLP-Compressed Texts

Deterministic sub-linear space LCE data structures with efficient construction

Dynamic index and LZ factorization in compressed space

Fully dynamic data structure for LCE queries in compressed space

Longest Common Extensions with Recompression

Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets

Efficiently Finding All Maximal $α$ -gapped Repeats

Lempel Ziv Computation In Small Space (LZ-CISS)

Computing convolution on grammar-compressed text

Detecting regularities on grammar-compressed strings

Efficient Lyndon factorization of grammar compressed text

Faster Compact On-Line Lempel-Ziv Factorization

See the researcher in context

Building this map preview

Tomohiro I

Research overview

Is this your work?

17 publications

Space-efficient SLP encoding for O(log⁡N)O(\log N)O(logN)-time random access

Computing Longest (Common) Lyndon Subsequences

Longest (Sub-)Periodic Subsequence

Substring Complexities on Run-length Compressed Strings

PHONI: Streamed Matching Statistics with Multi-Genome References

Practical Random Access to SLP-Compressed Texts

Deterministic sub-linear space LCE data structures with efficient construction

Dynamic index and LZ factorization in compressed space

Fully dynamic data structure for LCE queries in compressed space

Longest Common Extensions with Recompression

Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets

Efficiently Finding All Maximal ααα-gapped Repeats

Lempel Ziv Computation In Small Space (LZ-CISS)

Computing convolution on grammar-compressed text

Detecting regularities on grammar-compressed strings

Efficient Lyndon factorization of grammar compressed text

Faster Compact On-Line Lempel-Ziv Factorization

See the researcher in context

Building this map preview

Space-efficient SLP encoding for $O(\log N)$ -time random access

Efficiently Finding All Maximal $α$ -gapped Repeats