Optimal-Time Contextual Pattern Matching in Compressed Space
Gonzalo Navarro and Francisco Olivares · 2026
Read Optimal-Time Contextual Pattern Matching in Compressed Space by Gonzalo Navarro and Francisco Olivares (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31030.txt.
Introduction
Navarro and Olivares take up contextual pattern matching, a search task suited to giant repetitive collections like genome sets and versioned documents. Instead of listing every occurrence of a pattern, the search returns one position for each distinct context, where the context is a fixed number of symbols on either side of the match. Listing identical repeated occurrences one by one wastes effort, so distinct contexts are what users usually want.
Known solutions run in optimal time but need data structures as large as the text itself, which is too much for very repetitive data. The authors give the first optimal-time method that works in compressed space, using a symmetric compressed automaton called an SCDAWG. They also improve a weighted ancestor data structure so the distinct contexts can be listed with very small delays.
Catalog record
| CREATOR | Gonzalo Navarro and Francisco Olivares |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal-Time Contextual Pattern Matching in Compressed Space Thanks: Funded by Basal Funds FB0001 and AFB240001, and Fondecyt Grant 1260080, ANID, Chile. Affiliation: Centre for Biotechnology and Bioengineering, Chile Gonzalo Navarro and Francisco Olivares Abstract Contextual pattern matching is the task of, given a pattern P [ 1 , m ] P[1,m] , a context length λ \lambda , and a text T [ 1 , n ] T[1,n] , find all the o c c occ distinct contexts in which P P occurs in T T , the context being the λ \lambda symbols preceding and the λ \lambda symbols following the occurrence; a text position where each context occurs must be output. While the problem can be solved in optimal time O ( m + o c c ) O(m+occ) using O ( n ) O(n) -space precomputed data structures on T T , this type of search is particularly relevant on large repetitive text collections, where O ( n ) O(n) space can be prohibitive. We present the first optimal-time solution that runs in compressed space, namely that of a symmetric CDAWG (SCDAWG) of T T . Further, we show how the set of o c c occ solutions can be enumerated with O ( log log λ ) O(\log\log\lambda) delay after O ( m ) O(m) -time preprocessing of P P . To achieve this, we develop an improved linear-space distance-sensitive weighted ancestor data structure. 1 Introduction Given a text T[1,n] and a pattern P[1,m] , the classical Pattern Matching problem consists of finding all of the positions of T where P occurs. The Contextual Pattern Matching problem is a recently proposed variant [ 18 ] better suited for searching large collections of similar documents (e.g., genome collections, versioned documents, etc.). In such a case, if P occurs inside a piece of text that is repeated many times along the collection, it may be wasteful to list all those occurrences individually, as these are, for many purposes, essentially the same occurrence. Instead, the query provides also a context length \lambda and asks for one occurrence position of each distinct context around P : the context is formed by the \lambda characters preceding and the \lambda characters following the occurrence. This is formally stated as follows. Definition 1 ( [ 18 ] ) The Contextual Pattern Matching problem on a text T[1,n] is, given a pair (P[1,m],\lambda) , return a position in T for each of the occ distinct strings XPY occurring in T , for all X , Y such that |X|=|Y|=\lambda . To capture the occurrences near the extremes of T , assume T is preceded and followed by \lambda copies of the special symbol \$ , which cannot appear in P . In that paper [ 18 ] , it was shown that the problem can be solved in optimal time, O(m+occ) , by using O(n) -size data structures (essentially, suffix trees). This is not so satisfactory, however, because many repetitive collections are too large for O(n) space to be affordable. Instead, one desires some compressed indexing solution, which provides search functionality within space bounded by some measure of compressibility [ 19 , 16 ] . In the same paper (later corrected and improved [ 17 ] ) they provide one such compressed indexing solution: Letting r be the number of runs in the Burrows-Wheeler Transform of T , and \overline{r} the sum of the values of r for T and its reverse, the problem can be solved in time O(m+occ\log n) with an index of size O(\overline{r}\log\frac{n}{\overline{r}}) . Later, Abedin et al. [ 1 ] obtained O(m+occ\log\lambda\log\frac{n}{r}) time and O(r\log\frac{n}{r}) space. A natural question is whether one can obtain optimal time, O(m+occ) , within space proportional to some measure of repetitiveness (like r and \overline{r} , in the current solutions). In this paper we present the first index of this kind, whose space is related to measure e , which is the size of the CDAWG of T [ 6 ] . The CDAWG is a directed acyclic graph obtained by merging identical subtrees of the suffix tree: since the suffix tree of repetitive text collections tends to have many identical subtrees, e is a meaningful measure of repetitiveness. We actually build on a Symmetric CDAWG (SCDAWG) [ 11 ] , which includes the \overline{e} edges of T and of its reverse (the nodes are the same for both). Although it always holds \overline{e}\geq r , \overline{e} is incomparable with r\log\frac{n}{r} . Concretely, our index uses space O(\overline{e}) and performs Contextual Pattern Matching in optimal time, O(m+occ) . We then turn our attention to the enumeration problem: since the number of occurrences can be huge, we wish to provide an enumerator. This is a data structure that, after some (ideally small) preprocessing time, can deliver any new occurrence within a bounded delay . For example, it is easy to support enumeration for Pattern Matching, using a suffix tree with threaded leaves, with O(m) preprocessing and O(1) delay, but this is not so easy for Contextual Pattern Matching, even with O(n) space. Our optimal-time O(m+occ) algorithm naturally yields an enumerator with O(\lambda) delay, but we can do better: We give the first enumerator for Contextual Pattern Matching that, using O(\overline{e}) space, provides O(m) preprocessing time and O(\log\log\lambda) delay. To obtain this delay, we develop an improved linear-space distance-sensitive data structure for weighted ancestor queries [ 7 , 12 ] , which is of independent interest. Its time is loglogarithmic on the difference of weights between the query and answer nodes. We build our solution on top of previous work [ 12 ] , which incurs an O(\log^{*}n) extra penalty factor in order to achieve linear space. Using new techniques from the realm of compact data structures, we reduce this extra factor to constant. 2 Preliminaries By [i,j] we denote \{i,i+1,\dots,j\} , if i\leq j , and [i,j]=\emptyset , otherwise. By [n] we refer to [1,n] . T[1,n] denotes a length- n string over an alphabet \Sigma=\{1,\dots,\sigma\} . By |T| we refer to the length of T . T[i] denotes the i -th symbol of T , and T[i,j]=T[i]\cdots T[j] if [i,j]\neq\emptyset , otherwise ( j<i ) T[i,j]=\epsilon , which is the only string satisfying |\epsilon|=0 . T[1,i] is the prefix of T ending at position i and T[j,n] is the suffix of T starting at position j . The reverse of T is denoted by T^{\text{rev}}=T[n]\cdots T[1] . We assume T ends with a special symbol \$ only occurring at T[n] and that is smaller than any other symbol c\in\Sigma . Given T\in\Sigma^{*} and a,b\in\Sigma , we say that T[i,j] is a right-maximal substring of T if T[i,j]a and T[i,j]b are both substrings of T . Similarly, given c,d\in\Sigma , we say T[i,j] is a left-maximal substring of T if cT[i,j] and dT[i,j] are both substrings of T . We say that T[i,j] is maximal if it is right-maximal and left-maximal. 2.1 Suffix trees The suffix tree [ 21 , 14 , 20 ] of a string T over alphabet \Sigma , \textrm{STree}(T)=(V^{T}_{\textrm{\tiny STree}},E^{T}_{\textrm{\tiny STree}}) is a tree representing the