Source-linked AI summary
Tunnelling with a reference
Travis Gagie
TL;DR
For a highly repetitive text much longer than a non-repetitive reference, the paper adapts Baier’s tunnelling to use that reference. It describes auxiliary structures for accelerating r-index pattern matching when a long pattern substring matches one long reference substring, under a stated reference and tunnel-length condition.
Problem
The paper addresses how to speed up r-index pattern matching for a highly repetitive text T using a much shorter reference R.
Source: §2 · p. 2Method
Results
The method can speed up pattern matching when a long substring of the pattern matches a single long substring of the reference.
Source: §3 · p. 4Takeaways & Limitations
The paper’s approach uses reference-based auxiliary structures alongside an r-index for the longer repetitive text.
Source: §2 · pp. 2–3The stated setting assumes a non-repetitive reference and a tunnel length ℓ with log_σ n ≪ ℓ ≪ n.
Source: §2 · p. 3
Abstract
from arXiv · showhide
We show how to modify Baier's tunnelling for the case in which we have a non-repetitive and relatively short reference for a highly repetitive and much longer text. Given a pattern that mostly matches only one substring of the reference, we can use fairly small auxiliary data structures to speed up backward searching with an r-index for the whole text.
1 Introduction
The paper combines Lemma 1 with a modified version of Baier’s tunnelling, using a reference to speed up indexing highly repetitive texts. Lemma 1 uses a uniquely occurring pattern suffix to recover the longest suffix occurring in the text, its position, and its suffix-array rank.
1 Introduction
- The introduction frames switching between text order and BWT order as a way to gain an advantage, while noting that the cited r-index extensions do not make sense for non-repetitive texts.The cited examples include tag arrays [3] and suffixient sets [5].Source: §1 · p. 1
- Given a pattern with a suffix occurring only once in T, Lemma 1 finds its longest suffix occurring in T, that suffix’s position, and its suffix’s lexicographic rank.The lemma stores T in O(n log σ) bits.Source: §1 · p. 1
- Lemma 1’s procedure backward-searches until the BWT interval is a singleton, then uses SA and ISA queries and right-to-left comparisons to locate the longest matching suffix.The supplied proof passage describes the search and comparisons but does not provide complete bounds for every step.Source: §1 · p. 2
- The paper combines Lemma 1 with Baier’s tunnelling, modified to use a reference and allow substrings to leave tunnels midway, for indexing highly repetitive texts.The authors distinguish this from Ayad et al.’s use of a more sophisticated version of Lemma 1 in the U-index.Source: §1 · p. 2
2 Data structures
The data structures use a short reference R to organize intervals in the BWT of the longer repetitive text T. Their design assumes a non-repetitive reference and a tunnel length ℓ between log_σ n and n.
2 Data structures
- The construction starts by packing the reference R and targets auxiliary structures closer in size to n than to the repetitive text length N.The setting has σ ≤ n ≪ N.Source: §2 · p. 2
- For each reference character, the construction defines a BWT interval whose suffixes share a length-ℓ prefix with the reference and have a uniquely longest common prefix with that reference suffix; these intervals are disjoint and may be empty.The intervals are called tunnel entrances.Source: §2 · p. 2
- Two sparse N-bit vectors mark tunnel-entrance starts and ends, supporting containment checks in O(log log N) time; storing each entrance’s reference position j avoids SA queries.These vectors take O(n log N) bits.Source: §2 · p. 2
- For a non-repetitive reference, the authors expect 1 − p_ℓ to be close to 1 when log_σ n ≪ ℓ ≪ n, and use such an ℓ.This is stated as an expectation about the reference, not a guarantee for every reference.Source: §2 · pp. 2–3
- Tunnel exits store BWT interval endpoints for characters ℓ positions left of marked characters in tunnel entrances; each exit is a subinterval of an earlier entrance and avoids ISA queries.Storing all exits takes O(n log N) bits; the auxiliary structures accompany an r-index using O(r log N) bits.Source: §2 · p. 3
3 Pattern matching
The method uses reference matches to accelerate backward search with an r-index for a much longer repetitive text. Its stated speedup applies when a long pattern substring matches a single long reference substring.
3 Pattern matching
- When a pattern-suffix interval lies inside a tunnel entrance, the search compares the reference and uses rank queries to continue through tunnel exits, falling back to r-index backward steps at a mismatch.The interval checks and reference comparisons are interleaved with backward search.Source: §3 · p. 3
- The theorem assumes σ ≤ n ≪ N and log_σ n ≪ ℓ ≪ n, and stores the r-index for T in O(r log N) bits.Here R has length n and T has length N.Source: §3 · p. 3
- The auxiliary structures speed pattern matching when a long pattern substring matches a single long substring of the reference.The stated auxiliary-space bound depends on p_ℓ, which the passage says is usually close to 0.Source: §3 · pp. 3–4
- The query condition identifies the longest and shortest pattern suffixes occurring exactly once in R as P[m−smax+1..m] and P[m−smin+1..m].Source: §3 · p. 4
- A more careful variant can accelerate search even when the processed pattern suffix has no reference match, provided a sufficiently long prefix of that suffix has a single reference match.The authors defer this technique's details to the full version.Source: §3 · p. 4