Two-Dimensional Longest Common Extension Queries in Compact Space

We denote the interval $i$, $i+1$, $\mathrm{\dots }$, $j$ with $[i..j]$ and the interval $i$, $i+1$, $\mathrm{\dots }$, $j-1$, with $[i..j)$. For a string $S$ of length $n$ we use $S[i]$ to refer to $i^{th}$ character, $i\in [0..n)$. We use $S_1\cdot S_2$ to denote the concatenation of two strings $S_1$ and $S_2$. For notation, $S[i..j]=S[i]\cdot S[i+1]\cdot \mathrm{\dots }\cdot S[j]$, $S[i..j)=S[i]\cdot S[i+1]\mathrm{\cdots }\mathrm{\dots }\cdot S[j-1]$, and $S[i..]=S[i..n)$. Arrays and strings are zero-indexed throughout this work.

For a single string $S[0..n)$ and $i,j\in [0..n)$, $\mathrm{LCE}(i,j)$ is defined as the length of the longest common prefix of $S[i..]$ and $S[j..]$. In the case of two strings, $S_1[0..n_1)$ and $S_2[0..n_2)$, we overload the notation so that for $i\in [0..n_1)$, $j\in [0..n_2)$, $\mathrm{LCE}(i,j)$ is the length of the longest common prefix of $S_1[i..]$ and $S_2[j..]$. For a given string $S$, the suffix tree [34] is a compact trie of all suffixes of $S$ with leaves ordered according to the lexicographic rank of the corresponding suffixes. The classical suffix tree takes $𝒪(n)$ words of space and can be constructed in $𝒪(n)$ time for polynomially sized integer alphabets [9]. The suffix array $\mathrm{SA}[0..n)$ of a string $S[0..n)$ is the unique array such that $S[\mathrm{SA}[i]..]$ is the $i^{th}$ smallest suffix lexicographically. The inverse suffix array $\mathrm{ISA}[0..n)$ is the unique array such that $\mathrm{ISA}[\mathrm{SA}[i]]=i$, or equivalently, $\mathrm{ISA}[i]$ gives the lexicographic rank of $S[i..]$. The suffix tree can answer $\mathrm{LCE}$ queries in $𝒪(1)$ time. We call a compact trie with lexicographically ordered leaves for a subset of suffixes a sparse suffix tree. Observe that the number of nodes in a sparse suffix tree remains proportional to the number of suffixes it is built from.

We will utilize the following result by Kempa and Kociumaka, which provides an $\mathrm{LCE}$ data structure smaller than a classical suffix tree.

The next result by Bille et al. allows for a trade-off between space and query time. We will utilize it in Section 2.2.

A $d$-cover of an interval $[0..n)$ is a subset of positions, denoted by $𝒞$, such that for any $x\in [0..n-d)$ and $y\in [0..n-d)$ there exists $h\in [0..d)$ where $x+h,y+h\in 𝒞$. It was shown by Burkhardt and Kärkkäinen that there exists a $d$-cover of size $𝒪(n/\sqrt{d})$ that can be computed in $𝒪(n/\sqrt{d})$ time [4]. $d$-Covers have been used previously for LCE queries in the 1D case by Gawrychowski et al. [15] and Bille et al. [2]. Since we need a small data structure that lets us find an $h$ value as described above in constant time, we briefly outline the construction given in [4].

A difference cover modulo $d$ is a subset $𝒟\subseteq \{0,1,\mathrm{\dots },d-1\}$ where for all $w\in \{0,1,\mathrm{\dots },d-1\}$ there exist $u,v\in 𝒟$ such that $w\equiv u-vmodd$. Colbourn and Ling showed there exists $𝒟$ such that $|𝒟|=\mathrm{\Theta }(\sqrt{d})$ [8]. A $d$-cover $𝒞$ is constructed from a difference cover $𝒟$ as follows: For $j\in [0..n)$, if $(jmodd)\in 𝒟$, then $j$ is added to $𝒞$. We also build a look-up table $A$ of size $d$ such that for all $i\in \{0,1,\mathrm{\dots },d-1\}$ both $A[i]$ and $(A[i]+i)modd$ are in $𝒟$. This is always possible, thanks to the definition of the difference cover. See Figure 1.

We maintain the $𝒪(d)$ space look-up table $A$ as described above. We assume without loss of generality, $y\ge x$. Let $h≔(A[(y-x)modd]-x)modd$. Observe that

Hence, $(x+hmodd)\in 𝒟$ and $x+h\in 𝒞$. Also,

Hence, $(y+hmodd)\in 𝒟$ and $y+h\in 𝒞$. $◀$

We utilize the generalization of suffix trees to 2D texts presented by Giancarlo [16]. This suffix tree is created from the Lstrings of the 2D text $T$. LStrings are over an alphabet ${\cup }_{i=1}^n{\mathrm{\Sigma }}^{2i-1}$. For a position $(i,j)\in {[0..n)}^2$ the suffix $T[i..][j..]$ is $a_0\cdot a_1\cdot \mathrm{\dots }\cdot a_l$ where $l=n-\max (i,j)$ and $a_0=T[i][j]$ and $a_k=T[i+k][j..j+k)\cdot T[i..i+k][j+k]$ for $k>0$. See Figure 2. The characters are maintained implicitly as references to $T$, resulting in the 2D suffix tree over all suffixes $T[i..][j..]$, $(i,j)\in {[0,n)}^2$ occuping $𝒪(n^2)$ words of space. Once constructed, the 2D suffix tree allows us to find the $\mathrm{LCE}$ of two positions in $𝒪(1)$ time through a lowest common ancestor ($\mathrm{LCA}$) query. The 2D suffix tree also enables pattern matching in optimal $𝒪(m^2+occ)$ time.

The order between characters $a$ and $a^{\prime }$ of Lstrings is defined as the lexicographic order induced by the base alphabet $\mathrm{\Sigma }$. The lexicographic order of two Lstrings (and corresponding submatrices) is induced by the order of their characters. We additionally assume that the bottom row and rightmost column of $T$ consist of only a $\$$ symbol, which is the smallest in the alphabet order and occurs nowhere else in $T$.

The suffix array $\mathrm{SA}[0..n^2)$ of a 2D text $T[0..n)[0..n)$ is an array containing 2D points such that if $(i,j)=\mathrm{SA}[h]$, then $T[i..][j..]$ is the $h^{th}$ smallest suffix lexicographically. The inverse suffix array maps each $(i,j)\in {[0..n)}^2$ to its position in $\mathrm{SA}$, i.e. $\mathrm{ISA}[\mathrm{SA}[h]]=h$.

The $\delta$ measure is a well-studied compressibility measure for 1D texts [7, 20, 24, 25, 30]. It is defined as $\delta (T)={\max }_{1\le t\le n}{d}_t(T)/t$ where $d_t(T)$ denotes the number of distinct length $t$ substrings of $T[0,n)$.

Carfagna and Manzini recently generalized the $\delta$ measure to 2D texts [5, 6]. Letting $d_t(T)$ denote the number of distinct $t\times t$ submatrices of $T[0..n)[0..n)$, ${\delta }_{2D}(T)={\max }_{1\le t\le n}{d}_t(T)/t^2$. Observe that ${\delta }_{2D}(T)$ can range between $1$, e.g., in case where all elements of $T$ are the same character, and $n^2$, i.e., the case where all elements of $T$ are distinct. Carfagna and Manzini showed that the 2D block tree data structure of Brisaboa, et al. [3] occupies $𝒪(({\delta }_{2D}(T)+\sqrt{n{\delta }_{2D}(T)})\log \frac{n\log \sigma }{\sqrt{{\delta }_{2D}}\log n})$ words of space and provides access to any entry of $T$ in $𝒪(1+\log \frac{n\log \sigma }{\sqrt{{\delta }_{2D}}\log n})$ time. A further generalization of the $\delta$ measure to 2D allowing for non-square matrices was introduced by Romana et al. and related to other potential 2D compressibility measures [31]. In this work, we will only consider the ${\delta }_{2D}$ measure based on square submatrices. We hereafter refer to ${\delta }_{2D}$ as $\delta$ and omit the text $T$ when it is clear from context.

In addition to the previous components, we maintain the structure from Lemma 7 over the text obtained by concatenating $R_{i,t}$ for $i\in [0..n)$ and $t=1,2,4,8,\mathrm{\dots },\min (n-i,2^{\lceil \log d\rceil })$. We also maintain the structure from Lemma 7 over the text obtained by concatenating $C_{j,t}$ for $j\in [0..n)$ and $t=1,2,4,8,\mathrm{\dots },\min (n-j,2^{\lceil \log d\rceil })$. We leave the parameter $\tau$ appearing in Lemma 7 to be optimized later.

Given an $\mathrm{LCE}$ query $(i_1,j_1)$, $(i_2,j_2)$, we first find an $h\in [0..d)$ such that $(i_1+h,j_1+h)$ and $(i_2+h,j_2+h)$ are sampled positions. We then decompose the interval $[i_1..i_1+h)$ and $[j_1..j_1+h)$ into $𝒪(\log d)$ slabs that have lengths that are powers of two. We perform an $\mathrm{LCE}$ query for each corresponding slab for both rows and columns. A minimum is taken over all these $\mathrm{LCE}$ values and $h+\mathrm{LCE}((i_1+h,j_1+h),(i_2+h,j_2+h))$. Denote this minimum with $m$. There are two possible cases.

• $\mathrm{■}$

  $m>h$. See Figure 4(a). In this case, $m$ is reported as the result.

• $\mathrm{■}$

  $m\le h$. See Figure 4(b). In this case, we still need to find the largest value $y$ such that the minimum $\mathrm{LCE}$ of the slabs covering $C_{j_1}[i_1..]$, $\mathrm{\dots }$, $C_{j_1+y}[i_1..]$ (with slabs covering $C_{j_2}[i_2..]$,$\mathrm{\dots }$, $C_{j_2+y}[i_2..]$, respectively) and $R_{i_1}[j_1..]$, $\mathrm{\dots }$, $R_{i_1+y}[j_1]$ (with slabs covering $R_{i_2}[j_2..]$, $\mathrm{\dots }$, $R_{i_2+y}[j_2..]$, respectively) is at least $y$. To accomplish this, we perform a modified binary search while keeping track of the minimum $\mathrm{LCE}$ values for both the column and row slabs. The only difference compared to standard binary search is that rather than always dividing the current range under consideration in half, we consider the power of two closest to half the size of the current range. This is done to ensure that we always use slabs for which we have prepared $\mathrm{LCE}$ data structures.

Letting $T(l)$ be the number of $\mathrm{LCE}$ queries on slabs for the binary search on a range of length $l$, the resulting recurrence is

Hence, $T(h)=𝒪(\log d)$. We now fix $\tau ={\log }_{\sigma }n\cdot \log {\log }_{\sigma }n$. Since each $\mathrm{LCE}$ query on a slab takes $𝒪(\tau )$ time, the overall query time is $\tau \cdot \log d=𝒪({\log }_{\sigma }n\cdot {(\log {\log }_{\sigma }n)}^2)$, where we used that $d=\mathrm{\Theta }({\log }_{\sigma }^{2}n)$. The total added space relative to the previous solution is $𝒪(\log d\cdot n^2/\tau )$ words. Using our definitions of $d$ and $\tau$, the space remains $𝒪(n^2\log \sigma )$ bits.

Let $x$ be a parameter to be defined later. In addition to the previously defined diagonal sample positions, we now define sample positions for the rows and columns using an $x$-cover, denoted by $𝒳$. We maintain the structure in Lemma 7 (with parameter $\tau$ left open for optimizing later) over the text obtained by concatenating slabs $R_{i,t}$ for $t=1,2,4,8,\mathrm{\dots },\min (n-i,2^{\lceil \log d\rceil })$, whenever $i\in 𝒳$. We do the same for slabs $R_{i,t}$ for $t=1,2,4,8,\mathrm{\dots },\min (2^{\lceil \log d\rceil })$ whenever $i+t-1\in 𝒳$ and $i\ge 0$. Similarly, we maintain the structure from Lemma 7 for the concatenation of $C_{j,t}$ for $t=1,2,4,8,\mathrm{\dots },\min (2^{\lceil \log d\rceil })$ for $j\in 𝒳$. We do the same for $C_{j,t}$ for $t=1,2,4,8,\mathrm{\dots },\min (2^{\lceil \log d\rceil })$ whenever $j+t-1\in 𝒳$ and $j\ge 0$. Note that these slabs do not need to be explicitly constructed and can be simulated directly using the input text.

Given a query $(i_1,j_1)$, $(i_2,j_2)$, we first find $h\in [0..d)$ such that $(i_1+h,j_1+h)$ and $(i_2+h,j_2+h)$ are diagonal sample positions. Let find $y\in [0..x)$ such that $i_1+y$ and $i_2+y$ are in $𝒳$. We find the $\mathrm{LCE}$s of columns $C_{i_1}[j_1..]$, $\mathrm{\dots }$, $C_{i_1+y-1}[j_1..]$ with $C_{i_2}[j_2..]$, $\mathrm{\dots }$, $C_{i_2+y-1}[j_2..]$, respectively. We next find $y^{\prime }\in [0..x)$ such that $i_1+h-1-y^{\prime }$ and $i_2+h-1-y^{\prime }$ are in $𝒳$. We then find the $\mathrm{LCE}$s of columns $C_{i_1+h-y^{\prime }}[j_1..]$, $\mathrm{\dots }$ $C_{i_1+h-1}[j_1..]$, with $C_{i_2+h-y^{\prime }}[j_2..]$, $\mathrm{\dots }$, $C_{i_2+h-1}[j_2..]$, respectively. We then take the largest power of two, say $2^a$, such that $i_1+y+2^a\le i_1+h-1-y^{\prime }$, and obtain the $\mathrm{LCE}$ of the slab $C_{i_1+y,2^a}[j_1..]$ with $C_{i_2+y,2^a}[j_2..]$. We also obtain the $\mathrm{LCE}$ of the slabs $C_{i_1+h-y^{\prime }-2^a,2^a}[j_1..]$ and $C_{i_2+h-y^{\prime }-2^a,2^a}[j_2..]$. We perform a symmetric procedure on the rows. A minimum is taken among all of these $\mathrm{LCE}$ values as well as $h+\mathrm{LCE}((i_1+h,j_1+h),(i_2+h,j_2+h))$. Let $m$ denote this minimum. We consider two cases like in Section 2.2.

• $\mathrm{■}$

  $m>h$. In this case, $m$ is reported as the result.

• $\mathrm{■}$

  $m\le h$. As in Section 2.2, we want to output the largest value $y$ such that the minimum $\mathrm{LCE}$ of the slabs covering $C_{j_1}[i_1..]$, $\mathrm{\dots }$, $C_{j_1+y}[i_1..]$ (with $\mathrm{LCE}$ relative to slabs covering $C_{j_2}[i_2..]$,$\mathrm{\dots }$, $C_{j_2+y}[i_2..]$) and $R_{i_1}[j_1..]$, $\mathrm{\dots }$, $R_{i_1+y}[j_1]$ (with $\mathrm{LCE}$ relative to slabs covering $R_{i_2}[j_2..]$, $\mathrm{\dots }$, $R_{i_2+y}[j_2..]$) is at least $y$. The modification to the binary search algorithm from Section 2.2 is that we intermix at most $x$ single row/column evaluations to reach the next position in $𝒳$. After this position in $𝒳$ is reached, the power of two that most evenly splits the remaining range can be used.

We claim that answering a query requires $𝒪(x\cdot \log d)$ number of LCE queries for single rows/columns and $𝒪(\log d)$ number of LCE queries on slabs. To see this, let $S(l)$ be the number of single row/column $\mathrm{LCE}$ queries on a range of length $l$, and $T(l)$ be the number of slab $\mathrm{LCE}$ queries. Then we have

Hence, $S(h)=𝒪(x\log d)$ and $T(h)=𝒪(\log d)$. Each single row/column $\mathrm{LCE}$ query takes $𝒪(1)$ time and each $\mathrm{LCE}$ query on a slab takes $𝒪(\tau )$ time. As a result, the total query time is $𝒪(x\cdot \log d+\log d\cdot \tau )$. To optimize, we keep $d=\mathrm{\Theta }({\log }_{\sigma }^{2}n)$ and now fix $x=\tau =({\log }_{\sigma }^{2/3}n\cdot {(\log {\log }_{\sigma }n)}^{2/3})$ and obtain the query time of $𝒪({\log }_{\sigma }^{2/3}n\cdot {(\log {\log }_{\sigma }n)}^{5/3})$.

The (extra) space is $𝒪(\log d\cdot n^2/(\sqrt{x}\cdot \tau ))$ words. This is because we take $𝒪(\log d)$ larger slabs for each column/row sample position, creating an overall string of length $𝒪(\log d\cdot n^2/\sqrt{x})$. The $\mathrm{LCE}$ structure from Lemma 7, then occupies $𝒪(\log d\cdot n^2/(\sqrt{x}\cdot \tau ))$ words. With the above choice of $x$ and $\tau$, the total space is $𝒪(n^2\log \sigma )$ bits. This completes the proof of Theorem 1.

We first construct a 2D suffix tree of $T$ truncated at a string depth of $2\tau$. Call this ${𝒯}_{\le 2\tau }$. We use ${\mathrm{\ell }}_1$, ${\mathrm{\ell }}_2$, $\mathrm{\dots }$ to denote the leaves of ${𝒯}_{\le 2\tau }$.

We next define the macro-matrix. The elements of a macro-matrix are essentially meta symbols, where two meta-symbols are the same if and only if the corresponding $2\tau \times 2\tau$ square substrings are identical. Formally, the macro-matrix $M$ is the matrix obtained as follows: for $i,j\in [0..n)$,

• $\mathrm{■}$

  if there exists a $2\tau \times 2\tau$ matrix with upper left corner $(i,j)$, i.e., $i,j\le n-2\tau$, then we make $M[i][j]=\mathrm{\ell }$ where $\mathrm{\ell }$ is a pointer to the leaf of ${𝒯}_{\le 2\tau }$ corresponding to $T[i..i+2\tau -1][j..j+2\tau -1]$;

• $\mathrm{■}$

  if $i>n-2\tau$ or $j>n-2\tau$, then let $M[i][j]=\mathrm{\ell }$ where $\mathrm{\ell }$ is a pointer to the leaf in ${𝒯}_{\le 2\tau }$ corresponding to the $(n-\max (i,j))\times (n-\max (i,j))$ matrix with upper left corner $(i,j)$.

See Figure 5. We then construct the 2D block tree of $M$, denoted as $\mathrm{𝖡𝖳}(M)$.

We define sample positions based on a $\tau$-cover $𝒞$ of $[0..n)$. These consist of sample positions for the rows,

for the columns,

and for the diagonals,

Let ${𝒞}^{\prime }={𝒞}_R\cup {𝒞}_C\cup {𝒞}_D$. Observe that $|{𝒞}^{\prime }|=\mathrm{\Theta }(n^2/\sqrt{\tau })$. We build a sparse suffix tree over the suffixes starting at sampled positions in ${𝒞}^{\prime }$, denoted as ${𝒯}_s$. We also maintain the lookup data structure from Lemma 8. As before, this allows us to find in $𝒪(1)$ time equally far sampled positions at most $\tau$ away from the queried positions in each row, column, and diagonal.