Pattern Matching on Run-Length Grammar-Compressed Strings in Linear Time

Pattern matching is the problem determining whether a given pattern $P$ occurs in a given text $T$. It is one of the most fundamental problems in computer science, with applications in various fields such as text processing, signal processing, database searching, and bioinformatics. There are many algorithms for solving the pattern matching problem [5, 23].

Nowadays, datasets are often stored in a compressed form, and it is impractical to decompress the data each time to find a pattern in it. Thus, pattern matching on compressed data without decompression has attracted much attention. The problem of compressed pattern matching [29] is, given a pattern $P$ and a compressed representation $c(T)$ of a text $T$, to determine whether $P$ occurs in $T$ without decompressing it. The complexity of matching algorithms is mainly measured with respect to $m=|P|$ and $g=|c(T)|$, rather than $n=|T|$.

Since the pioneering work of Amir and Benson [1], many compressed pattern matching algorithms have been proposed for various compression methods, depending on the specific properties of the methods [2, 19, 4]. Among them, Gawrychowski [8] showed an algorithm for Lempel-Ziv compression (commonly known as LZ77) that runs in $O(g\log (n/g)+m)$. Gawrychowski [9] also showed $O(g+m)$ time algorithm for Lempel-Ziv-Welch (LZW) compression. Recently, as a landmark, Ganardi and Gawrychowski [6] successfully developed an algorithm for straight-line programs (SLPs) that runs in $O(g+m)$ time. SLP is a context-free grammar that generates exactly one string, which is extensively employed to generalize various grammar-based compression techniques [12, 28, 32, 21, 10, 3].

The complexity of pattern matching on compressed data is inherently linked to the compressibility of the data itself, as the size $g$ is influenced by the specific compression algorithm employed. Substring complexity $\delta$ due to Kociumaka et al. [17] serves as a measure of the compressibility of highly repetitive strings, enabling the evaluation of the compression performance of various methods. They showed that LZ77 can represent any text using $O(\delta \log (n/\delta ))$ space, which is asymptotically optimal with respect to $\delta$. In contrast, an SLP requires $O(\delta {\log }^2(n/\delta ))$ space. LZ77 achieves high compression ratios compared to other methods and is widely used in practical applications such as zip. However, processing data directly in its LZ77-compressed form is challenging. Even accessing the $i$-th character of the text is difficult, and solving compressed pattern matching in linear time is not feasible [8]. The difficulty of handling LZ77-compressed data is evident from the fact that the matching algorithm shown in [8] begins by converting LZ77-compressed data into an SLP.

Nishimoto et al. [26] enhanced SLPs with “run-length rules” of the form $A\to B^k$ to handle repetitions more efficiently. Run-Length Straight-Line Programs (RLSLPs), like LZ77, can represent any text using $O(\delta \log (n/\delta ))$ space. Furthermore, RLSLPs preserve the simplicity and usability characteristic of grammar-based compression algorithms. For example, in RLSLPs, a substring of length $l$ at any position in the text can be accessed in $O(l+\log n)$ time [17], and longest common extension (LCE) queries can be answered in $O(\log n)$ time [13]. Additionally, RLSLPs are used in applications such as constructing suffix arrays [13] and indexes [16] within $O(\delta \log (n/\delta ))$ space. Despite their various applications, no linear-time matching algorithm for RLSLPs has been proposed.

In this paper, we propose a linear-time compressed pattern matching algorithm for strings compressed by RLSLPs, as stated in the following theorem.

In the linear-time algorithm for compressed pattern matching on SLPs [6], it is crucial to represent substrings of the text where the pattern may occur as a concatenation of a constant number of substrings of the pattern. We will adopt this idea to our algorithm for RLSLPs. The challenge lies in representing substrings of the text as concatenations of substrings of the pattern, even when a rule of the form $A\to B^k$ $(k\ge 3)$ is present, which does not exist in SLPs. To address this, handling repetitions of substrings within the pattern is essential. A cover suffix tree [27] is a data structure that extends a suffix tree by adding nodes corresponding to substrings in a string whose squares are substrings of the string. However, for our problem, handling only squares, i.e., substrings that repeat twice, is insufficient. Instead, we need to determine the exact number of times a given substring repeats in a string. We address this issue by introducing a new data structure, an extension of the cover suffix tree, that can handle all repetitions within a string.

In the whole paper we assume the standard word RAM model, which operates on $𝗐$-bit words, where $𝗐\ge \log n$ and $𝗐\ge \log m$, with the standard arithmetic (excluding integer division) and bitwise operations.

Let $\mathrm{\Sigma }$ be a finite alphabet. A string of length $n$ is a finite sequence of $n$ symbols in $\mathrm{\Sigma }$. For a string $s=a_1\mathrm{\dots }{a}_n$, we write $s[i]=a_i$ for the $i$-th character of $s$. The length of $s$ is denoted by $|s|$. A string of length $0$ is called the empty string and is denoted by $\epsilon$. The concatenation of two strings $s$ and $t$ is denoted by $s\cdot t$ or $st$. For a string $s$, we define $s^1=s$ and $s^k=s\cdot s^{k-1}$ for any integer $k>1$. A string of the form $s^k$ for any positive integer $k\ge 1$ is called a repetition of $s$ and particularly $s^2$ is referred to as the square of $s$. A string $s$ is primitive if $s$ cannot be represented as $u^k$ for any string $u$ and integer $k>1$. A string $u$ is a root of $u^k(k\ge 1)$, and if $u$ is primitive, $u$ is the primitive root of $u^k$. A substring of a string $s$ starting at position $i$ and ending at position $j$ is denoted by $s[i..j]$. Especially, a substring $s[1..j]$ is called a prefix, and a substring $s[i..|s|]$ is called a suffix of $s$. Proper prefixes and suffixes of $s$ are those different from $s$. The suffix $s[i..|s|]$ is also denoted by $s[i..]$. If $i>j$ then $s[i..j]$ is the empty string. Let $\mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(s)$, $\mathrm{𝑃𝑟𝑒𝑓}(s)$ and $\mathrm{𝑆𝑢𝑓𝑓}(s)$ be the sets of all substrings, prefixes and suffixes of $s$, respectively. We say that a string $u$ occurs in a string $s$ at position $(i,j)$ if $u=s[i..j]$. For a string $s$ and an integer $k$ (), the $k$th-rotation of $s$ is $\mathrm{𝑟𝑜𝑡}(s,k)=s[k+1..|s|]s[1..k]$. A period of a string $u$ is a positive integer $p$ such that $u[i]=u[i+p]$ for all $i$ with $1\le i\le |u|-p$. A substring $u[i..j]$ is a run in $u$ if for its smallest period $p$, (1) $2p\le j-i+1$, (2) $i=1$ or $u[i-1]\ne u[i-1+p]$, and (3) $j=|u|$ or $u[j+1]\ne u[j+1-p]$. A run is specified by the pair of its position $(i,j)$ and smallest period $p$. If $u^k\in \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(s)$ and $u^{k+1}\notin \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(s)$, $u^k$ and $k$ are called the maximum repetition and the maximum repetition count of $u$ in $s$, respectively.

A straight-line program (SLP) is a context-free grammar describing exactly one string. Without loss of generality, we assume the grammar is in Chomsky normal form, i.e., each rule is of the form $A\to BC$ or $A\to a$ where $A,B,C$ are nonterminals and $a$ is a terminal. For any rule $A\to BC$, $A$ does not appear in the derivation of $B$ nor $C$. A run-length straight-line program (RLSLP) [26] is an extended SLP which can also have rules of the form $A\to B^k$ where $k\ge 3$. We call rules of the forms $A\to BC$ and $A\to B^k$ binary rules and run-length rules, respectively. The terminal string derived from a nonterminal $A$ is denoted by $\tilde{A}$.

The size of an SLP and an RLSLP is the number of nonterminals in the grammars. Any SLP or RLSLP of size $g$ describing a string of length $n$ can be converted in $O(g)$ time to an equivalent SLP or RLSLP of size $O(g)$ whose derivation tree has height $O(\log n)$ [7, 24].

This section describes an overview of Ganardi and Gawrychowski’s [6] compressed pattern matching algorithm on SLP and the challenges in extending it to RLSLP.

Consider an SLP $𝒢$ of size $g$ for a text $T$ of length $n$ and a pattern $P$ of length $m\ge 2$. For each nonterminal $A$ of $𝒢$, let ${\mathrm{𝗉𝗋𝖾𝖿𝗂𝗑}}_P(A)$ be the longest element of $\mathrm{𝑃𝑟𝑒𝑓}(\tilde{A})\cap \mathrm{𝑆𝑢𝑓𝑓}(P)$ and ${\mathrm{𝗌𝗎𝖿𝖿𝗂𝗑}}_P(A)$ be the longest element of $\mathrm{𝑆𝑢𝑓𝑓}(\tilde{A})\cap \mathrm{𝑃𝑟𝑒𝑓}(P)$.

We can verify that $P$ occurs in $T$ if and only if there exists a rule $A\to BC$ such that $P$ occurs in ${\mathrm{𝗌𝗎𝖿𝖿𝗂𝗑}}_P(B)\cdot {\mathrm{𝗉𝗋𝖾𝖿𝗂𝗑}}_P(C)$. This fact has often been used to solve the compressed pattern matching problems efficiently [4, 14, 9, 8], where those strings are represented and processed as positions on $P$. However, no linear-time algorithm is known that computes ${\mathrm{𝗉𝗋𝖾𝖿𝗂𝗑}}_P(A)$ and ${\mathrm{𝗌𝗎𝖿𝖿𝗂𝗑}}_P(A)$ for all nonterminals $A$ in an arbitrary SLP. To achieve a linear-time solution for SLP-compressed pattern matching, Ganardi and Gawrychowski [6] invented a brilliant idea to compute approximations of them, which we call PSI-information (Prefix-Suffix-Infix information) in this paper. A PSI-information is a tuple consisting of either four substrings or a single substring of $P$.

They showed the following algorithm that computes some ${\psi }_A\in \mathrm{\Psi }(A)$ for each rule $A\to BC$ recursively, assuming that ${\psi }_B\in \mathrm{\Psi }(B)$ and ${\psi }_C\in \mathrm{\Psi }(C)$ are already computed. Depending on the types of ${\psi }_B$ and ${\psi }_C$, there are four cases.

Case 1

${\psi }_B=(\tilde{B})$ and ${\psi }_C=(\tilde{C})$:
Let ${\psi }_A:=(\tilde{B}\cdot \tilde{C})$ if $\tilde{B}\cdot \tilde{C}\in \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(P)$. Otherwise, let ${\psi }_A:=(\tilde{B},\tilde{C},\tilde{B},\tilde{C})$.

Case 2

${\psi }_B=(x,y,u,v)$ and ${\psi }_C=(\tilde{C})$:
Let ${\psi }_A:=(x,y,u,v\cdot \tilde{C})$ if $v\cdot \tilde{C}\in \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(P)$. Otherwise, let ${\psi }_A:=(x,y,v,\tilde{C})$.

Case 3

${\psi }_B=(\tilde{B})$ and ${\psi }_C=(x,y,u,v)$:
Let ${\psi }_A:=(\tilde{B}\cdot x,y,u,v)$ if $\tilde{B}\cdot x\in \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(P)$. Otherwise, let ${\psi }_A:=(\tilde{B},x,u,v)$.

Case 4

${\psi }_B=(x_B,y_B,u_B,v_B)$ and ${\psi }_C=(x_C,y_C,u_C,v_C)$:
Let ${\psi }_A:=(x_B,y_B,u_C,v_C)$.

In every case, the computation is reduced to at most one call of the scq, defined below.

Substring concatenation query

(scq): Given two substrings $u$ and $v$ of $P$ represented by their positions, return a position of $uv$ in $P$ if $uv\in \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(P)$; otherwise, return “No”.

For scqs, it is not known whether we can answer for any single query in $O(1)$ time with $O(m)$-time preprocessing. However, they showed the following alternative solution for batched queries, that is a key to the linear-time pattern matching algorithm.

Let $L_c$ be the set of nonterminals whose derivation tree is of height $c$. PSI-information for nonterminals is computed in the order of $L_1,L_2,\mathrm{\cdots }$, in a batched style. From Lemma 6, PSI-information for all $A\in L_c$ can be computed in $O(|L_c|+m/𝗐)$ time for each $c\ge 1$.

Another key element to support the linear-time algorithm is balancing SLPs to ensure that the height of the derivation tree is $O(\log n)$, due to Ganardi et al. [7]. With this technique, the total time complexity of the algorithm is bounded by $O(g+m)$, as we will trace it in the proof of Lemma 27.

We now turn our attention to extend the algorithm to RLSLPs. Concerning the height of the derivation trees, Navarro et al. [24] showed that any RLSLP can be balanced in linear time without increasing its asymptotic size. Thus, the crucial issue to realize a linear time RLSLP-compressed pattern matching algorithm is to establish the counterparts of Lemmas 7 and 8 for the run-length rules. Those will appear in Section 5 as Lemmas 28 and 26. Of course, we do not take the naive and computationally expensive solution that breaks down a run-length rule $A\to B^k$ into $O(\log k)$ binary rules and applies Ganardi and Gawrychowski’s technique. The following two types of queries will play important roles to achieve our goals just like Lemmas 7 and 8 are based on scqs.

Maximum repetition query

(mrq): Given a nonempty substring $v$ of $P$ represented by a position, answer one of the positions of its maximum repetition $v^k$ and the maximum repetition count $k$.

Primitive root query

(prq): Given a nonempty substring of $P$ represented by a position, answer one of the positions of its primitive root.

If we can answer mrqs efficiently, we can efficiently compute PSI-information of $A$ from that of $B$ for run-length rules $A\to B^k$.

The longest common prefix $\mathrm{𝑙𝑐𝑝}(x,y)$ of strings $x,y$ is $x[1..k]$ for $k=\max \{k\mid x[1..k]=y[1..k]\}$. The suffix tree of $P$ is defined as follows.

Note that whereas the mathematical definition above is given with strings, node names and edge labels are represented as occurrence positions of those in $P$. This paper often uses strings for readability where the actual computation is done on positions, unless confusion arises. We assume one can access in constant time the node $P[i..]\$$ for any $i\le m$ and the parent of an arbitrary node. The suffix tree can be constructed in $O(m)$ time [30]. Every substring of $P$ that is not an explicit node of the suffix tree is called an implicit node. An implicit node $u\in S\setminus V$ is a conceptual node that exists between two explicit nodes and specified as $(uv,|v|)\in V\times \mathbb{N}$ where $uv$ is the shortest extension of $u$ in $V$. A node is either an explicit node or an implicit node.

We extend suffix trees by adding more explicit nodes.

We use an extended suffix tree to store the answers to the mrqs and prqs on respective nodes. We promote implicit nodes $v$ to explicit nodes only if the answers to the queries on $v$ are nontrivial, in the sense that either the primitive root of $v$ is not $v$, or the maximum repetition of $v$ is not $v$. In the trivial case, the answers to mrqs and prqs can be the queried positions themselves, with the maximum repetition count $1$. Let ${\mathrm{\Gamma }}_{\ast }\subseteq \mathrm{𝑆𝑢𝑏𝑠𝑡𝑟}(P)$ be the set of nonempty strings for which the mrq or the prq is nontrivial:

The goal of this section is to construct $\mathrm{𝑅𝐸𝑆𝑇}(P,{\mathrm{\Gamma }}_{\ast })$, defined as follows.

That is, the answer to the mrq on $x$ is $\mathrm{MaxRep}(x)$ and $\mathrm{RepCount}(x)$ and the one to the prq on $x$ is $\mathrm{PrimRoot}(x)$.

The suffix tree $ST(P)$ and the repetition-informed suffix tree $\mathrm{𝑅𝐸𝑆𝑇}(P,{\mathrm{\Gamma }}_{\ast })$ extended with ${\mathrm{\Gamma }}_{\ast }$ for $P=aabcbcbcbc$ are shown in Figure 1. Although values $\mathrm{MaxRep}(x)$ and $\mathrm{PrimRoot}(x)$ are positions on $P$, for intuitive understandability, Figure 1 presents them as links from $x$ to the nodes corresponding to those positions. We remark that $\mathrm{RepCount}(x)$ can be computed from $\mathrm{MaxRep}(x)$ and $|x|$. However, under the assumptions of the computer model, integer division cannot be done in constant time. So, we will compute the values in the preprocessing step and let $\mathrm{𝑅𝐸𝑆𝑇}(P,{\mathrm{\Gamma }}_{\ast })$ remember them.