Sensitivity of Repetitiveness Measures to String Reversal

In many fields of science and industry, there exist huge data collections. Many of these collections are highly repetitive, in the sense that the documents that make them up are highly similar to each other. Examples include the 1000 Human Genomes Project [8] in bioinformatics and the Software Heritage Repository [11]. Repetitiveness measures [32] were introduced to quantify the degree of compressibility of highly repetitive string collections, as other standard techniques based on Shannon’s entropy fail to capture repetitiveness [26].

Some repetitiveness measures abstract the output size of existing compressors, like the size $z$ of the Lempel-Ziv 77 parsing (LZ) [29], the size $g$ of the smallest straight-line program (SLP) generating the string [24], and the number $r$ of equal-symbol runs in the Burrows–Wheeler Transform (BWT) [6]. Other measures are based purely on combinatorial properties of the strings, like the substring complexity $\delta$ [40] and the size $\gamma$ of the smallest string attractor [21].

A fundamental question in this context is what makes a repetitiveness measure $\mu (w)$ better than another. One important aspect is reachability: whether it is possible to represent all strings within $O(\mu (w))$ space. Another important aspect is space efficiency: assuming that $\mu$ is reachable, how small $\mu (w)$ can be on highly repetitive strings. There is also indexability: what queries on the uncompressed string can be answered efficiently using $O(\mu )$ space.

Recently, another aspect of repetitiveness measures, which we call robustness, has gained attention. A measure is robust against a string operation if it does not increase much after applying that operation to any string. We are interested in quantifying how much a given measure can increase after applying a string operation in worst-case scenarios. This quantity is called sensitivity [1]. Questions about the sensitivity of a measure are especially important in dynamic domains where the data can change over time, and finding answers to them can be useful, for instance, to understand how to update the measure after applying such a string operation. Akagi et al. [1] studied how much repetitiveness measures can change after applying to the string single character edit operations. There are many other works dealing with similar problems for different combinations of string operation and repetitiveness measures [5, 9, 10, 12, 15, 16, 18, 31, 35, 36, 37, 38].

In this work we focus on studying the fundamental string reversal operation, which takes a string $w[1]\mathrm{\cdots }w[n]$ and outputs the string $w[n]\mathrm{\cdots }w[1]$. We first review known results on the impact of string reversal on repetitiveness measures, and then present our contributions. Table 1 summarizes both the prior results and our contributions.

On the one hand, there are measures of repetitiveness that are fully symmetric, that is, reversing the string does not change the value of the measure at all. This is a desirable property, as arguably, mirroring the string does not change its intrinsic repetitiveness. This class includes the measures $\delta$ and $\gamma$, the size $\nu$ of the smallest NU-system [38], the size $b$ of the smallest bidirectional macro scheme [42]; and the size $g,g_{rl},g_{it}$ and $c$ of the smallest straight-line program, run-length straight-line program [39], iterated straight-line program [35], and collage-system [23], respectively. A weaker version of symmetry is exhibited by the size $\chi$ of the smallest suffixient set, for which it was recently proved that $\chi (w^R)/\chi (w)\le 2$ [37], though $\chi (w^R)-\chi (w)$ can be as large as $\mathrm{\Omega }(n)$ [37].

At the other extreme, there are measures widely used in practice – such as the number $r$ of runs in the RLBWT – that are very sensitive to reversal. Giuliani et al. [15] showed that in an infinite family of words, after reversing the string, the measure $r$ can increase from $O(1)$ to $\mathrm{\Omega }(\log n)$. An equivalent result was obtained by Biagi et al. [5] regarding the number $r_B$ of runs in the run-length Bijective Burrows-Wheeler Transform (BBWT) [14, 4]. Moreover, the size $e$ of the compact directed acyclic word graph (CDAWG) of a string can increase by a $\mathrm{\Omega }(\sqrt{n})$ multiplicative factor when reversing the string [17]. For the additive case, the increase can be up to $\mathrm{\Omega }(n)$; this proof is deferred to the full version.

For some other measures, not much is known. For LZ parsing and some of its variants, it has been conjectured that even though the number of phrases of the parses can change after reversing the string, the ratio $z(w^R)/z(w)$ is bounded by a constant. For the size $v$ of the lex-parse of the string, the conjecture is the opposite, namely that $v(w^R)/v(w)$ can be $\omega (1)$.

In this context, our contributions are as follows:

1. 1.

   In Section 3, we show that the number $r$ (resp. $r_B$) of runs of the RLBWT (resp. RLBBWT) can increase by $\mathrm{\Theta }(n)$ after reversing the string. This improves the currently known $\mathrm{\Omega }(\log n)$ lower bound for the additive increase on these measures under string reversal [5, 15].

2. 2.

   In Section 4, we show that the number $z$ (resp. $z_{no}$, resp. $z_e$) of phrases of the Lempel-Ziv parsing (resp. LZ without overlaps, resp. LZ-end) can increase by $\mathrm{\Theta }(n)$ when applying the reverse operation. This improves the currently known $\mathrm{\Omega }(\sqrt{n})$ lower bound for the additive increase on $z$ [9]. Moreover, we show a family where $z(w^R)/z(w)$ approaches $3$ as $|w|$ goes to infinity.

3. 3.

   Finally, in Section 5, we show that the number $v$ of phrases in the lex-parse of a string can grow by a $\mathrm{\Omega }(\log n)$ multiplicative factor after applying the reverse operation, and this is asymptotically tight. Moreover, we show a string family where after reversing the string, the additive increase on the measure $v$ is $\mathrm{\Theta }(n)$.

We conclude in Section 6 with conclusions and future directions for research.

We denote $[i,j]=\{i,i+1,\mathrm{\dots },j\}\subseteq \mathbb{Z}$ if $i\le j$, and $\mathrm{\varnothing }$ otherwise. An ordered alphabet $\mathrm{\Sigma }=\{a_1,a_2,\mathrm{\dots },a_{\sigma }\}$ is a finite set of symbols equipped with an order relation such that . A string $w[1\mathrm{\dots }n]=w[1]\mathrm{\cdots }w[n]$ is a finite sequence of symbols in $\mathrm{\Sigma }$. The length of $w$ is denoted by $|w|=n$. The unique string of length $0$, called the empty string, is denoted by $\epsilon$. The set of all strings is ${\mathrm{\Sigma }}^{\ast }$, and we let ${\mathrm{\Sigma }}^{+}={\mathrm{\Sigma }}^{\ast }\setminus \{\epsilon \}$.

For strings $x=x[1]\mathrm{\cdots }x[n]$ and $y=y[1]\mathrm{\cdots }y[m]$, their concatenation is $x\cdot y\equiv xy=x[1]\mathrm{\cdots }x[n]y[1]\mathrm{\cdots }y[m]$. By ${\prod }_{i=1}^k{w}_i$ we denote the concatenation of the strings $w_1,w_2,\mathrm{\dots },w_k$ in that order. We also let $w^k={\prod }_{i=1}^{k}w$. For a string $w$, a sequence of non-empty strings ${(x_k)}_{k=1}^m=(x_1,\mathrm{\dots },x_m)$ is referred to as a factorization (or parsing) of $w$ if $w={\prod }_{i=1}^m{x}_i$; each $x_k$ is called a phrase (or factor). The run-length encoding of a string $w$ is $\mathrm{𝚛𝚕𝚎}(w)=(a_1,p_1),\mathrm{\dots },(a_m,p_m)$ where $a_i\ne a_{i+1}$ for $i\in [1,m-1]$, $p_i\ge 1$ for all $i$, and $w={\prod }_{i=1}^m{a}_i^{p_i}$. For a string $w=xyz$, the string $x$ (resp. $y$, resp. $z$) is called a prefix (resp. substring, resp. suffix) of $w$. A substring (resp. prefix, resp. suffix) is proper if it is different from $w$, and non-trivial if in addition it is different from $\epsilon$. We use the notation $w[i\mathrm{\dots }j]$ to denote the string $w[i]\mathrm{\cdots }w[j]$ when $1\le i\le j\le n$ and $\epsilon$ otherwise. We denote $S_w(k)$ the set of substrings of length $k$ appearing in $w$.

The lexicographic order on ${\mathrm{\Sigma }}^{\ast }$ is defined recursively by for every $x\in {\mathrm{\Sigma }}^{+}$, and for $a,b\in \mathrm{\Sigma }$ and $u,v\in {\mathrm{\Sigma }}^{\ast }$, by if either , or $a=b$ and . The $\omega$-order is defined as iff , where $x^{\omega }$ is the infinite periodic string with period $x$.

The suffix array (SA) of a string $w$ of length $n$ is an array $\mathrm{𝑆𝐴}[1\mathrm{\dots }n]$ such that $\mathrm{𝑆𝐴}[i]$ is the starting position of the $i^{\text{th}}$ lexicographically smallest suffix of $w$. The inverse suffix array (ISA) of $w$ is the array $\mathrm{𝐼𝑆𝐴}[1\mathrm{\dots }n]$ defined by $\mathrm{𝐼𝑆𝐴}[\mathrm{𝑆𝐴}[i]]=i$ for $i\in [1,n]$. The longest common prefix array (LCP) of $w$ is an array $\mathrm{𝐿𝐶𝑃}[1\mathrm{\dots }n]$ where $\mathrm{𝐿𝐶𝑃}[i]$ stores the length of the longest common prefix of the suffixes $w[\mathrm{𝑆𝐴}[i-1]\mathrm{\dots }n]$ and $w[\mathrm{𝑆𝐴}[i]\mathrm{\dots }n]$ for $i\in [2,n]$, and $\mathrm{𝐿𝐶𝑃}[1]=0$.

A rotation of $w[1\mathrm{\dots }n]$ is any string of the form $w[i\mathrm{\dots }n]w[1\mathrm{\dots }i-1]$ for $i\in [1,n]$. Let $ℛ(w)=\{w_1,w_2,\mathrm{\dots },w_n\}$ be the lexicographically sorted multiset of rotations of $w$. The Burrows-Wheeler transform (BWT) of $w$ is the string $\mathrm{𝙱𝚆𝚃}(w)=w_1[n]w_2[n]\mathrm{\cdots }{w}_n[n]$. Moreover, let ${\mathrm{𝙱𝚆𝚃}}_x(w)$ denote the substring of $\mathrm{𝙱𝚆𝚃}(w)$ induced by the rotations having string $x$ as a prefix. That is, let $[\mathrm{𝑙𝑏},\mathrm{𝑢𝑏}]$ be the maximal range such that $w_i[1\mathrm{\dots }|x|]=x$ for all $i\in [\mathrm{𝑙𝑏},\mathrm{𝑢𝑏}]$; then ${\mathrm{𝙱𝚆𝚃}}_x(w)=w_{\mathrm{𝑙𝑏}}[n]\mathrm{\cdots }{w}_{\mathrm{𝑢𝑏}}[n]$. The BWT-matrix of $w$ is a 2D array containing in the $i^{\text{th}}$ row the rotation $w_i$ for $i\in [1,n]$; its last column coincides with $\mathrm{𝙱𝚆𝚃}(w)$.

A Lyndon word is any string $w$ that is smaller than any of its other rotations, or alternatively, smaller than any of its proper suffixes. The Lyndon factorization of a string $w$ is the unique sequence $\mathrm{𝙻𝙵}(w)=x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ satisfying that $w={\prod }_{i=1}^{\mathrm{\ell }}{x}_i$, each $x_i$ is Lyndon, and $x_i\ge x_{i+1}$ for $i\in [1,\mathrm{\ell }-1]$.

In this section, we show that under string reversal, the additive sensitivity of $r$, $r_{\text{\$}}$, and $r_B$ are all $\mathrm{\Omega }(n)$. This substantially improves the previous $\mathrm{\Omega }(\log n)$ lower-bounds on the additive sensitivity, which can be derived from the results of Giuliani et al. [15] and Biagi et al. [5] on the multiplicative sensitivity of $r$ and $r_B$.

In the following proofs, we rely on an infinite family of strings defined as follows.