Text Indexing and Pattern Matching with Ephemeral Edits

Solon P. Pissis · 2025

Read Text Indexing and Pattern Matching with Ephemeral Edits by Solon P. Pissis (2025) 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-2508-05124.txt.

Introduction

Solon Pissis wrote this 2025 paper on searching text that is being tested with edits which are then undone. An edit stream is called ephemeral when each change is paired with its reverse, restoring the original string. Such streams arise when software tests what if edits on live data.

Pissis builds a data structure over a fixed text that answers pattern searches under these fleeting edits. The edits can insert, delete, or swap a short piece of the text. Setup takes time in line with the text length. A query pattern is prepared quickly, in near linear time and its own length in space. The result speeds a task that naive rescans handle poorly.

Catalog record

CREATORSolon P. Pissis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05124

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Text Indexing and Pattern Matching with Ephemeral Edits Solon P. Pissis Abstract A sequence e 0 , e 1 , … e_{0},e_{1},\ldots of edit operations in a string T T is called ephemeral if operation e i e_{i} constructing string T i T^{i} , for all i = 2 ​ k i=2k with k ∈ ℕ k\in\mathbb{N} , is reverted by operation e i + 1 e_{i+1} that reconstructs T T . Such a sequence arises when processing a stream of independent edits or testing hypothetical edits. We introduce text indexing with ephemeral substring edits , a new version of text indexing. Our goal is to design a data structure over a given text that supports subsequent pattern matching queries with ephemeral substring insertions, deletions, or substitutions in the text; we require insertions and substitutions to be of constant length. In particular, we preprocess a text T = T [ 0 . . n ) T=T[0\mathinner{.\,.}n) over an integer alphabet Σ = [ 0 , σ ) \Sigma=[0,\sigma) with σ = n 𝒪 ⁡ ( 1 ) \sigma=n^{\mathcal{O}(1)} in 𝒪 ⁡ ( n ) \mathcal{O}(n) time. Then, we can preprocess any arbitrary pattern P = P [ 0 . . m ) P=P[0\mathinner{.\,.}m) given online in 𝒪 ⁡ ( m ​ log ⁡ log ​ m ) \mathcal{O}(m\log\log m) time and 𝒪 ⁡ ( m ) \mathcal{O}(m) space and allow any ephemeral sequence of edit operations in T T . Before reverting the i i th operation, we report all Occ occurrences of P P in T i T^{i} in 𝒪 ⁡ ( log ⁡ log ⁡ n + Occ ) \mathcal{O}(\log\log n+\textsf{Occ}) time. We also introduce pattern matching with ephemeral edits , a new version of pattern matching. Here, the goal is to design a data structure over two given strings that supports pattern matching with ephemeral edits in one of the two strings. In particular, we preprocess two strings T T and P P , each of length at most n n , over an integer alphabet Σ = [ 0 , σ ) \Sigma=[0,\sigma) with σ = n 𝒪 ⁡ ( 1 ) \sigma=n^{\mathcal{O}(1)} in 𝒪 ⁡ ( n ) \mathcal{O}(n) time. Then, we allow any ephemeral sequence of edit operations in T T . Before reverting the i i th operation, we report all Occ occurrences of P P in T i T^{i} in the optimal 𝒪 ⁡ ( Occ ) \mathcal{O}(\textsf{Occ}) time. Along our way to this result, we also give an optimal solution for pattern matching with ephemeral block deletions . The utility of these results is underscored by the following key aspects: • Our algorithms are founded on a model highly motivated by real-world applications; e.g., in pangenomics, one often wants to process local variants originating from different individuals . • As anticipated, our algorithms outperform their fully dynamic counterparts [Gawrychowski et al., SODA 2018; Amir et al., ACM Trans. Algorithms 2007] within this model. • In stark contrast to their fully dynamic counterparts, our algorithms are simple to implement, leveraging only textbook algorithms or data structures with mature implementations. 1 Introduction Pattern matching and text indexing are the two flagship problems of combinatorial pattern matching. In pattern matching , we are given a pattern P=P[0\mathinner{.\,.}m) of length m and a text T=T[0\mathinner{.\,.}n) of length n , and we are asked to find all occurrences of P in T . This can be solved in \mathcal{O}(n) time by the classical Knuth-Morris-Pratt algorithm [ KJP77 ] . In text indexing , we are asked to preprocess a text T of length n into a data structure that supports subsequent pattern matching queries: given a pattern P , we report (or count) all occurrences of P in T . Reporting all Occ occurrences of P in T can be done in the optimal \mathcal{O}(m+\textsf{Occ}) time using suffix trees, which can be constructed in \mathcal{O}(n) time [ FFM00 ] . A central question of theoretical and practical interest is: What happens when text T is subjected to edit operations? Motivation. In a typical setting, one already has at hand a long reference string as the text T (e.g., a reference genome, a baseline legal document or a configuration file), which will remain mostly static, except for a few local edits. These local edits are often independent (e.g., genomic variants coming from individuals or client-specific variations); or hypothetical (e.g., they are not intended to be permanent, but rather are applied temporarily to test a specific scenario in a scientific simulation or to analyze the impact of a potential alteration). More concretely, this setting is highly relevant in computational pangenomics [ Con18 , TM20 , MWHBS24 ] , where T models an existing reference sequence, and the sequence of independent edit operations represents a collection of short local variants originating from different individuals . 1 1 1 The Variant Call Format ( https://en.wikipedia.org/wiki/Variant_Call_Format ) stores this type of data. In fact, many international consortia (e.g., https://alpaca-itn.eu/ and https://www.pangenome.eu/ ) deal with such data. The fact that local variants originate from different individuals suggests that once a variant is processed, the corresponding edit should be reverted before processing the next one. Indeed, when querying a pattern against one individual’s genome (which is a variant of the reference), we do not want that variant to persist when moving on to query against another individual’s genome, which will have its own distinct short local variant from the reference. In response, we introduce new versions of text indexing and pattern matching with ephemeral edits. A sequence e_{0},e_{1},\ldots of edit operations in a string T is called ephemeral if operation e_{i} constructing string T^{i} , for all i=2k with k\in\mathbb{N} , is reverted by operation e_{i+1} that reconstructs T . Since for any odd i , T^{i}=T , when the context is clear, we may simply use T^{i} to refer to a case where i is even. Our Contributions. We introduce a new interesting version of text indexing that we call text indexing with ephemeral substring edits . The goal is to design a data structure over a given text that supports subsequent pattern matching queries with ephemeral substring insertions, deletions, or substitutions in the text; we require insertions and substitutions to be short (of constant length), but deletions can be arbitrarily long. First, we preprocess a text T of length n . Then, we are asked to preprocess any arbitrary pattern P of length m given online, and subsequently allow any ephemeral sequence of edit operations on T . Before reverting the i th operation, we must report all occurrences of P in T^{i} . We show that after an \mathcal{O}(n) -time preprocessing of T , we can preprocess any arbitrary pattern P of length m in \mathcal{O}(m\log\log m) time and \mathcal{O}(m) space to then support pattern matching queries after any edit in \mathcal{O}(\log\log n+\textsf{Occ}) worst-case time. Note that P is not static; we can preprocess any subsequent pattern in \mathcal{O}(m\log\log m) time and \mathcal{O}(m) space (i.e., independently of n ). Further note that our query time is essentially independent of m . More formally, we show the following result. Theorem 1 . Given a text T of length n over an

Read the complete text