Better Indexing for Rectangular Pattern Matching

We revisit the complexity of indexing a two-dimensional text for the general case of rectangular patterns. We observe that, in fact, the abstract notion of an index, as defined by Giancarlo [11], is somewhat restricted: he defines what it means for one pattern to be a prefix of another, and then requires that the index has a form of a compacted tree, with every node corresponding to some pattern occurring in the text, and the parent of each node corresponding to its prefix. This is consistent with the notion of one-dimensional suffix trees, but suffix trees are not the only known indexing structures. For example, suffix arrays [20] use $𝒪(n)$ space and allow retrieving the occurrences in $𝒪(m+\log n+k)$ time, even though they are not based on storing a compacted trie (although they are of course related to suffix arrays). We show that a very simple idea allows us to obtain the following result.

In the above theorem we assume the standard word RAM model with words of logarithmic (in the size of the input) length. Basic arithmetic operations on such words (and indirect addressing) are assumed to take constant time. Each character is assumed to fit in a single machine word. We measure the size of our data structures in the number of words.

A (one-dimensional) string is a sequence of characters. We index positions in a string starting from 1. For a string $S$ of length $n$, we write $S[i]$ to denote its $i$-th character and $S[i..j]$ to denote the substring spanning positions $i$ through $j$, inclusive. If only one endpoint is provided, we interpret the interval as a prefix or suffix: $S[..i]:=S[1..i]$ is the prefix of length $i$; $S[i..]:=S[i..n]$ is the suffix starting at position $i$.

We define two-dimensional strings as rectangular arrays of characters. We refer to the total number of characters in a two-dimensional string as its size. Rows and columns are indexed starting from 1. For a two-dimensional string $S$ we write $S[i]$ to denote its $i$-th row, interpreted as a one-dimensional string. Consequently, $S[i][j]$ denotes the character in the $i$-th row and $j$-th column.

In our algorithm, we reduce two-dimensional indexing to a collection of problems concerning one-dimensional strings. This is done by treating fixed-length fragments of rows of the two-dimensional text as atomic symbols, which we refer to as meta-characters. Formally, for a two-dimensional string $S$ and a fixed width $w$, a meta-character is a substring of the form $S[i][j..j+w-1]$. To effectively operate on such meta-characters, we will represent each of them by an integer from $[\mathrm{poly}(n)]$ that fits inside a single machine word¹¹1It is in fact enough that it fits in a constant number of machine words., called the identifier. The identifiers of two meta-characters will be different if and only if the meta-characters themselves are different.

We use the standard compacted trie, also known as a compressed trie or Patricia trie, for storing a set of strings. The strings consist of either characters or meta-characters. In either case, we assume that the symbols fit in a single machine word. A compacted trie built for a set of $k$ strings is of size $𝒪(k)$, as we collapse maximal paths consisting of nodes with exactly one child into a single edge, thus the number of inner nodes is strictly smaller than the number of leaves. The remaining nodes are called explicit, while the dissolved nodes are called implicit.

We will need a few data structures. The first is called a deterministic dictionary.

The second is a range reporting structure (we note that other trade-offs between the space and reporting time are possible, but we state only one of them to avoid clutter).

Finally, we need to implement prefix search on a compacted trie. That is, given a query string, we traverse the trie to determine whether it occurs as a prefix of any stored string. If so, we return the corresponding node (which may be implicit); otherwise, we report that no such prefix match exists.

To implement prefix search, we start at the root and descend following the appropriate edge. This requires storing all the edges outgoing from an explicit node in a dictionary structure, which we implement with Theorem 2. Since the total degree over all explicit nodes is $𝒪(k)$, the combined space used by all dictionaries is $𝒪(k)$. For implicit nodes, we only verify whether the subsequent characters of the query string are the same as on the edge, using constant-time read-only random access to one of the stored strings. Then, the time per each character of the query string is constant, so $𝒪(m)$ overall. $◀$

The construction follows the classical Karp-Miller-Rosenberg (KMR) approach [17], and is based on assigning integer identifiers to all fragments of the form $T[i][j..j+2^k-1]$, for all $k$ such that $2^k\le W$. For each such fragment, we define its identifier as the lexicographic rank of its substring among all distinct substrings of the same length, and store this value. Then, the identifier of $T[i][j..j+w-1]$ consists of the identifiers of two overlapping fragments of length $2^{\lfloor \log w\rfloor }$ that together cover the whole $T[i][j..j+w-1]$. Since there are $𝒪(n)$ fragments per length and $𝒪(\log W)$ relevant lengths, the total space required is $𝒪(n\log n)$.

To encode a pattern row $P[i]$ of width $w$, we represent the corresponding meta-character by the pair of identifiers of its prefix and suffix of length $2^k$, where $k=\lfloor \log w\rfloor$. To support this, during text preprocessing, we collect all distinct substrings $T[i][j..j+2^k-1]$ and store them in a compacted trie, where each leaf is labeled with the lexicographic rank among all substrings of $T$ of length $2^k$. We build a separate compacted trie for each relevant value of $k$; since each trie requires $𝒪(n)$ space and there are $𝒪(\log W)$ values of $k$, the total space used by all the compacted tries is $𝒪(n\log n)$. At query time, we extract the $2^k$-length prefix and suffix of $P[i]$ and search for them in the corresponding compacted trie to obtain their identifiers. If either substring is not found, we report that the pattern does not occur in the text. Otherwise, in $𝒪(m)$ time we obtain the sought identifier for each row of the pattern.

To complete the reduction, we must identify all occurrences of the one-dimensional meta-character pattern within the two-dimensional text. To that end, we consider all windows of $w$ consecutive columns. Each such $w$-column strip defines a one-dimensional text of length $H$, where the $j$-th character is a meta-character corresponding to the block of $w$ consecutive characters in the $j$-th row of the strip. Formally, to define the one-dimensional texts corresponding to each $w$-column strip, we fix a horizontal offset $i\in \{1,\mathrm{\dots },W-w+1\}$ and define a one-dimensional text of length $H$ consisting of the meta-characters $T[j][i..i+w-1]$ for all positions $j\in \{1,\mathrm{\dots },H\}$. This gives a collection of $W-w+1$ one-dimensional texts over the same meta-character alphabet. Each occurrence of the meta-character pattern in one of these one-dimensional texts corresponds one-to-one to a two-dimensional occurrence of the original pattern in the text.

In each of these one-dimensional instances, the derived meta-character pattern has length $h\ge w$. We exploit this assumption when designing a (simple) indexing structure in Section 4.

We could apply Lemma 5 for each width $w\in \{1,\mathrm{\dots },W\}$ to handle patterns of width $w$ and height $h\ge w$. The total additional space is bounded by ${\sum }_{w=1}^W𝒪(n/w)=𝒪(n\log n)$, matching the requirements of Theorem 1. However, when $h$ is smaller than ${\log }^{\epsilon }n$, it holds that $w{\log }^{\epsilon }n$ in the query time is larger than $m$. We thus handle the case of small $w$ separately as follows.

We store all suffixes of all input texts, each terminated with a distinct delimiter, in a compacted trie implemented with Lemma 4. The total number of suffixes is $𝒪(n)$, so the total required space is $𝒪(n)$. Querying for a pattern of length $h$ is implemented by performing a prefix search for the pattern in the trie and reporting all leaves in the corresponding subtree. $◀$

We apply Lemma 6 for every width $w\le \log n$, and otherwise use Lemma 5. The total space is still $𝒪(n\log n)$. To bound the query time, we observe that whenever we use Lemma 6 the query time is $𝒪(h+k)=𝒪(m+k)$, and whenever we use Lemma 5 we can assume $w>\log n$ so the query time is $𝒪(hw+(w+k){\log }^{ϵ}n)=𝒪(m+k{\log }^{ϵ}n)$.

We assume that the input texts allow constant-time read-only random access to the individual characters, and each of them fits in a single machine word. Throughout this section, we fix a parameter $w$, corresponding to the lower bound on the length of the pattern. Texts shorter than $w$ can be discarded, as they cannot contain an occurrence of a pattern of length $h\ge w$.

For each text $T$, we define a collection of cuts: positions between characters spaced at regular intervals of length $w$. Formally, we insert a cut at every position $i$ such that $i\equiv 0(modw)$, including $i=0$. Each cut partitions $T$ into a prefix $T_1=T[..i]$ and a suffix $T_2=T[i+1..]$, where either may be empty. We associate the cut with the pair $(T_1,T_2)$, which serves as its representation. We organize the collection of cuts using a two-dimensional range reporting structure. Let ${𝒯}_1$ denote the set of all prefixes $T_1$ reversed, and let ${𝒯}_2$ denote the set of all suffixes $T_2$ extracted from the cuts. We build two compacted tries:

• $\mathrm{■}$

  ${𝒮}_1$, storing the strings in ${𝒯}_1$,

• $\mathrm{■}$

  ${𝒮}_2$, storing the strings in ${𝒯}_2$.

To ensure that each string from ${𝒯}_1$ and from ${𝒯}_2$ corresponds to a unique leaf in the respective trie, we conceptually prepend and append a distinct delimiter character to each prefix and suffix, respectively.

Next, we assign a pre-order number to each leaf of ${𝒮}_1$ and ${𝒮}_2$ via a depth-first traversal. Each cut then defines a point $(x,y)\in {\mathbb{Z}}^2$, where:

• $\mathrm{■}$

  $x$ is the pre-order number of the leaf in ${𝒮}_1$ corresponding to the reversal of $T_1$,

• $\mathrm{■}$

  $y$ is the pre-order number of the leaf in ${𝒮}_2$ corresponding to $T_2$.

This yields a collection of $𝒪(n/w)$ such points, one per cut. We store these points in an instance of Theorem 3.

Given a pattern $P$ of length $h\ge w$, our goal is to report all of its occurrences in the input texts. Since the pattern has length at least $w$, any occurrence must span at least one cut position from the collection defined for the texts. We iterate over all positions at which such a cut could intersect an occurrence of the pattern. We refer to each such position within the pattern as an anchor, and consider only the first $w$ possible anchors, to ensure that every occurrence of $P$ is reported exactly once.

Specifically, we consider all positions $j\in \{0,1,\mathrm{\dots },w-1\}$ where the pattern may be anchored. Each such position induces a partition of $P$ into a prefix $P_1=P[..j]$ and a suffix $P_2=P[j+1..]$. The task is to find and report all cuts in the texts that partition some text into $(T_1,T_2)$ such that $P_1$ is a suffix of $T_1$ and $P_2$ is a prefix of $T_2$. This is implemented as follows. First, we extract the corresponding prefix-suffix pair $(P_1,P_2)$ from the pattern. We then locate the (possibly implicit) node $v_1$ in ${𝒮}_1$ corresponding to the reversal of $P_1$, and the node $v_2$ in ${𝒮}_2$ corresponding to $P_2$. If either node does not exist, the current position cannot yield any occurrences and is skipped. Otherwise, let $[{\mathrm{\ell }}_1,r_1]$ and $[{\mathrm{\ell }}_2,r_2]$ be the ranges of pre-order numbers of leaves in the subtrees of $v_1$ and $v_2$, respectively.

The problem now reduces to a two-dimensional orthogonal range reporting query: report all stored points $(x,y)$ that lie within the rectangle $[{\mathrm{\ell }}_1,r_1]\times [{\mathrm{\ell }}_2,r_2]$. Each reported point corresponds to a valid cut that certifies an occurrence of the pattern. Querying the instance of Theorem 3 yields the query bound claimed in Lemma 5.