1 Introduction↩︎

Dynamic strings support insertion, deletion, substitution, splitting, and concatenation. A fundamental query on such strings is the longest common extension (LCE) query: given two positions, possibly in two different strings, return the length of the longest common prefix of the two corresponding suffixes. Dynamic LCE and dynamic string equality are basic primitives in dynamic text processing, versioned documents, genome editing, and dynamic indexing.

The dynamic string problem has a long history, from practical rope data structures [1] to the optimal structure of Gawrychowski, Karczmarz, Kociumaka, Łącki, and Sankowski [2], which achieves logarithmic updates and constant-time equality and LCE queries w.h.p. using locally consistent parsing [3]. In contrast, Lipták, Masillo, and Navarro proposed \(\mathsf{FeST}\) (a forest of enhanced splay trees) as a simple textbook solution [4]. \(\mathsf{FeST}\) supports splits, concatenations, equality, and LCE queries with logarithmic or nearly logarithmic amortized bounds.

This paper focuses on making this simple paradigm fully persistent. A fully persistent data structure allows updates on any version, producing a new branch of the version history. Throughout this paper, \(n\) denotes the total length of the string(s) involved in the operation under consideration. For a sequence of \(U\) updates, we write \(n_{\max}=\max_{0 \leq i \leq U} n_u\), where \(n_u\) is the corresponding value of \(n\) for the \(u\)-th update.

Amortized structures like splay trees [5] lose efficiency in full persistence because poorly balanced versions can be repeatedly queried. Therefore, we propose \(\mathsf{FeAVL}\) (a forest of enhanced AVL trees), replacing self-adjusting trees with worst-case balanced implicit-key trees such as AVL trees [6] augmented with sizes and fingerprints. Path copying gives full persistence because rank searches, splits, concatenations, and rebalancing affect only \(\mathcal{O}(\log n)\) nodes

The choice of AVL trees also has a compressed counterpart: AVL grammars, introduced by Rytter for grammar-based compression [7]. In the resulting fully persistent data structure, called the \(\mathsf{FeAVL}\) grammar, an LZ77 factorization of size \(z_0\) for an initial string of length \(n_0\) can be transformed into an AVL grammar of size \(\mathcal{O}(z_0\log n_0)\). By choosing the smaller of this grammar and the uncompressed AVL tree, we may assume an initial size of \(g_0=\mathcal{O}(\min\{n_0,z_0\log n_0\})\). For subsequent updates, we only rely on the fact that split and concatenation operations function correctly for arbitrary AVL grammars. Table 1 summarizes the two layers of the result, and our contributions are summarized as follows:

1. We give an AVL-tree version of \(\mathsf{FeST}\), called \(\mathsf{FeAVL}\), with worst-case rather than amortized tree bounds: equality in \(\mathcal{O}(\log n)\) time w.h.p. and LCE in \(\mathcal{O}(\log n+\log^2 \ell)\) time w.h.p., where \(\ell\) is the answer.

2. We make the structure fully persistent by path copying. Every update can be issued from any previous version and creates only \(\mathcal{O}(\log n)\) new permanent nodes.

3. We isolate the obstruction to a straightforward fully persistent splay-based \(\mathsf{FeST}\): path copying may copy a linear-height access path, and full persistence allows the same bad old version to be reused repeatedly.

4. We give a grammar-compressed instantiation using AVL grammars. Starting from an initial grammar of size \(g_0\), after \(U\) updates, the structure occupies \(\mathcal{O}(g_0+I+U\log n_{\max})\) permanent grammar nodes.

2 Preliminaries↩︎

2.1 Strings and Dynamic LCE↩︎

Let \(\Sigma\) be an alphabet. An element of \(\Sigma^*\) is a string. The length of a string \(s\) is denoted by \(|s|\). For \(1\le i\le j\le |s|\), \(s[i..j]\) denotes the substring \(s[i]\cdots s[j]\) that starts at position \(i\) and ends at position \(j\) in \(s\). Let \(s[i..] = s[i..|s|]\) and \(s[..j] = s[1..j]\). For strings \(s\) and \(t\), \(st\) denotes their concatenation, of length \(|s|+|t|\). Given a position \(i\) in a string \(s\) and a position \(j\) in a string \(t\), the longest common extension (LCE) query is to answer \[\mathsf{lce}(s,i,t,j)=\max\{\ell\ge 0 : s[i..i+\ell-1]=t[j..j+\ell-1]\},\] which is the longest common prefix (LCP) length of \(s[i..]\) and \(t[j..]\).

We maintain a collection of string objects. The following operations are used throughout the paper.

• \(\mathsf{make\_string}(w)\): create a new string object storing the static string \(w\).

• \(\mathsf{split}(s,i)\): split string \(s\) into \(s[1..i]\) and \(s[i+1..]\).

• \(\mathsf{concat}(s,t)\): concatenate two strings \(s\) and \(t\), producing \(st\).

• \(\mathsf{access}(s,i)\): return character \(s[i]\).

• \(\mathsf{equal}(s,i,t,j,\ell)\): test whether \(s[i..i+\ell-1]=t[j..j+\ell-1]\).

• \(\mathsf{lce}(s,i,t,j)\): return the LCE length of strings \(s[i..]\) and \(t[j..]\).

Single-character insertion, deletion, substitution, extraction, and introduction of substrings are obtained from these primitives in the standard way.

Unless stated otherwise, for an operation on one or two strings we write \(n\) for the total length of the string or strings involved in that operation. Thus, for \(\mathsf{lce}(s,i,t,j)\), we use \(n=|s|+|t|\) if \(s\) and \(t\) are distinct string objects, and \(n=|s|\) if the two positions belong to the same string. For space bounds over a sequence of updates, \(n_u\) denotes the corresponding value of \(n\) for the \(u\)-th update, and \(n_{\max}\) denotes the maximum string length involved over the whole history. Throughout the paper, logarithmic terms in asymptotic bounds are understood to be at least one; equivalently, \(\log x\) means \(\max\{1,\log_2 x\}\) inside \(\mathcal{O}(\cdot)\)-bounds.

2.2 Karp–Rabin Fingerprints↩︎

We use Karp–Rabin fingerprints [8]. Let \(p\) be a prime and let \(b\in\{1,\ldots,p-1\}\) be chosen uniformly at random. For a string \(x=x[1]\cdots x[m]\), define \[\kappa(x)=\sum_{r=0}^{m-1} x[m-r] b^r \bmod p .\] For two strings \(x\) and \(y\), let \(\kappa(xy)=(\kappa(x)b^{|y|}+\kappa(y))\bmod p\). We store with each represented substring both its fingerprint and the value \(b^{|x|}\bmod p\). As usual, by choosing \(p\) sufficiently large, all equality answers are correct w.h.p. over any polynomial-length sequence of operations. The data structure itself is deterministic except for this fingerprinting choice.

2.3 AVL Trees as Implicit-Key Sequence Trees↩︎

An AVL tree [6] is a binary tree in which, for every internal node, the heights of the two children differ by at most one (see [6], [9]). We use AVL trees as implicit-key sequence trees: the in-order traversal spells the represented string, and ranks are in-order positions computed from subtree sizes [9]. The standard rank search, split, concatenate, and rebalancing operations visit and modify only \(\mathcal{O}(\log n)\) nodes in the worst case.

We shall use the following property of AVL trees.

AVL trees satisfy Definition 1. The same uncompressed construction extends to other joinable balanced trees satisfying the logarithmic update-path property.

2.4 AVL Grammars↩︎

A straight-line program, or grammar, is a directed acyclic graph of rules in which each rule is either a terminal rule \(X\to a\) or a binary rule \(X\to YZ\). Each symbol \(X\) derives a unique string, denoted \(\mathsf{val}(X)\). The size of the grammar is the number of symbols. For a terminal rule we set \(h(X)=0\), and for a binary rule \(X\to YZ\) we set \(h(X)=1+\max\{h(Y),h(Z)\}\).

An AVL grammar is therefore a DAG representation of a string whose unfolded derivation tree is an AVL tree. The graph itself need not be a tree because the same symbol may be shared by many parents. Rytter introduced AVL grammars for grammar-based compression and proved the following result.

In this paper, Theorem 1 is used only to obtain a small initial representation. All subsequent dynamic and persistent operations require only that the current representation is an AVL grammar.

2.5 Persistence↩︎

A partially persistent structure allows queries on old versions, but updates only on the newest version. A fully persistent structure allows both queries and updates on any old version. The version graph is therefore a tree; each update derives from a single existing version. We use the standard path-copying method [10]: when an update changes a node, a fresh copy of that node is created, and the change is propagated through copied ancestors up to the root. Old nodes are never overwritten.

3 An AVL-Tree Data Structure for Dynamic LCE↩︎

In this section, we propose our fully persistent data structure, called \(\mathsf{FeAVL}\) (a forest of enhanced AVL trees). In our structure, each string is stored in one AVL tree. The in-order traversal of the tree spells the string. For a node \(v\), let \(L(v)\) and \(R(v)\) be its left and right children. The node \(v\) stores five values \(v.\mathsf{char}\), \(v.\mathsf{size}\), \(v.\mathsf{height}\), \(v.\mathsf{fp}\), and \(v.\mathsf{pow}\), where \(v.\mathsf{size}\) is the number of nodes in the subtree rooted at \(v\), \(v.\mathsf{height}\) is the AVL height, \(v.\mathsf{fp}\) is the fingerprint of the substring represented by the subtree rooted at \(v\), and \(v.\mathsf{pow}=b^{v.\mathsf{size}}\bmod p\), where \(b\) is the Karp–Rabin base fixed in Sec. 2. Null children have size 0, fingerprint 0, and power 1. Each time \(v\) obtains a new child, its fields are updated in constant time: \[\begin{align} v.\mathsf{size}&= \mathsf{size}(L(v)) + \mathsf{size}(R(v)) + 1,\\ v.\mathsf{fp}&= ((\mathsf{fp}(L(v))\cdot b + v.\mathsf{char})\cdot \mathsf{pow}(R(v)) + \mathsf{fp}(R(v))) \bmod p,\\ v.\mathsf{pow}&= \mathsf{pow}(L(v))\cdot b\cdot \mathsf{pow}(R(v)) \bmod p. \end{align}\] The height field is updated in the standard AVL way. All rotations and joins call this constant-time update routine on the nodes whose children changed.

3.1 Basic Operations↩︎

3.1.0.1 Construction.

\(\mathsf{make\_string}(w)\) builds a balanced tree whose in-order labels are the characters of \(w\). A perfectly balanced tree can be constructed in \(\mathcal{O}(|w|)\) time, and all auxiliary fields are computed by a post-order traversal.

3.1.0.2 Access.

\(\mathsf{access}(s,i)\) follows the usual rank search using subtree sizes. Because the tree has logarithmic height, the time is \(\mathcal{O}(\log |s|)\).

3.1.0.3 Split and concatenate.

\(\mathsf{split}(s,i)\) applies rank-based split to the tree representing \(s\) and returns two roots. \(\mathsf{concat}(s,t)\) applies AVL concatenation to the two roots. Both operations preserve all auxiliary fields by recomputing them on the modified nodes. By Definition 1, each operation takes \(\mathcal{O}(\log |st|)\) worst-case time.

3.2 Substring Fingerprints and Equality↩︎

To compute the fingerprint of substring \(s[i..j]\), we temporarily split the tree into three parts \(s[..i-1]\), \(s[i..j]\), and \(s[j+1..]\). The middle root stores the fingerprint of \(s[i..j]\). In the non-persistent structure the three parts can be concatenated back.

3.3 LCE Queries↩︎

The LCE query follows the LCP algorithm of Lipták et al. [4]. Their algorithm uses substring equality tests together with temporary extraction and reinsertion of windows. It first obtains a crude upper bound on the answer by testing candidate lengths that grow by repeated squaring, and then finishes the search inside localized windows. To avoid an extra factor depending on the global length when the answer is small, it applies this localization idea twice, the “hitting twice” strategy of \(\mathsf{\mathsf{FeST}}\).

The same algorithm applies to our enhanced AVL trees. Indeed, the primitives used in the \(\mathsf{\mathsf{FeST}}\) LCP algorithm—substring equality, split, concatenate, extract, and introduce—are supported by Lemmas 1 and 2 in worst-case logarithmic time. Thus the amortized analysis of Lipták et al.becomes a worst-case analysis in our setting.

4 Full Persistence by Path Copying↩︎

We now make the structure fully persistent in the sense of Sec. 2.5. A version is a set of root pointers, one per string object; an operation acts on strings of a given version and returns a new version, modifying no node reachable from an old version.

4.1 Path-Copied AVL Trees↩︎

We path-copy every primitive: a node whose child pointer or auxiliary field would change is copied, and untouched subtrees are shared with the old version.

4.2 Persistent Updates and Queries↩︎

Updates such as insertion, deletion, substitution, split, concatenate, extract, and introduce are implemented as in the non-persistent structure with path-copied primitives, so each creates a new version while preserving the input.

Equality and LCE queries are non-destructive: a read-only fingerprint traversal adds no permanent nodes, and any temporary path-copied splits used instead are discarded after the query.

4.2.0.1 Space accounting.

Let \(U\) be the number of updates, let \(n_0\) be the total length of initially created strings, and let \(I\) be the total number of explicitly inserted fresh characters over all versions. Let \(n_u\) be the total length of the strings involved in update \(u\). The total number of permanent nodes is \(\mathcal{O}(n_0+I+U \log n_{\max})\). This form is preferable to a bound stated only in terms of the current total length, because fully persistent structures retain nodes belonging to old branches.

4.3 Why Splay-Based \(\mathsf{FeST}\) Is Problematic↩︎

\(\mathsf{FeST}\) uses splay trees [11], which give amortized logarithmic bounds in the ephemeral setting. This amortization is not robust under a straightforward path-copying implementation.

The proposition rules out only the straightforward path-copied \(\mathsf{FeST}\): for partial persistence, where updates follow a single evolving tree, the standard amortized analysis still applies. Under full persistence, a worst-case balanced tree is the natural replacement.

5 AVL-Grammar-Compressed Version↩︎

We present a compressed version of a fully persistent data structure, the \(\mathsf{FeAVL}\) grammar, based on grammar-based compression [7]. It replaces the AVL tree of Sec. 3 by an AVL grammar DAG. Each nonterminal \(X\) stores the fields \(|\mathsf{val}(X)|\), \(h(X)\), \(\mathsf{fp}(X)\), and \(\mathsf{pow}(X)\), which are initialized directly for a terminal rule \(X\to a\), and updated from the two children in \(O(1)\) time for a binary rule \(X\to YZ\). \[\begin{align} |\mathsf{val}(X)| &= |\mathsf{val}(Y)|+|\mathsf{val}(Z)|,\\ h(X) &= 1+\max\{h(Y),h(Z)\},\\ \mathsf{fp}(X) &= (\mathsf{fp}(Y)\cdot \mathsf{pow}(Z)+\mathsf{fp}(Z)) \bmod p,\\ \mathsf{pow}(X) &= \mathsf{pow}(Y)\cdot \mathsf{pow}(Z) \bmod p. \end{align}\] The rule is valid only when \(|h(Y)-h(Z)|\le 1\). Symbols are immutable, and a version stores root symbols for the strings in that version.

5.1 Closure under Split and Concatenation↩︎

The basic operation is Rytter’s AVL-grammar concatenation. Given two AVL grammars rooted at \(X\) and \(Y\), it creates an AVL grammar for \(\mathsf{val}(X)\mathsf{val}(Y)\). If the two heights differ by at most one, it creates the single rule \(Z\to XY\). If one side is much taller, the algorithm descends along the appropriate spine of the taller derivation tree, inserts the shorter grammar at the first height-compatible position, and then rebuilds and rebalances on the way back.

We next use the interval-decomposition operation that already appears in Rytter’s construction. When processing a new LZ factor, Rytter locates its previous occurrence in the already constructed prefix grammar and decomposes the corresponding interval into nonterminals \(S_1, S_2,\ldots,S_t\) whose derived strings concatenate to the factor. Because the grammar is AVL-balanced, this decomposition has \(t=\mathcal{O}(\log n)\) fragments; moreover, the fragment heights have the right-sided/left-sided, equivalently bitonic, structure used in Rytter’s analysis. Joining this sequence telescopes: a concatenation of two grammars adds symbols proportional to their height difference, and along a bitonic sequence these differences sum to \(\mathcal{O}(\log n)\). Thus the fragments can be concatenated into one AVL grammar by adding only \(\mathcal{O}(\log n)\) new symbols, not \(\mathcal{O}(\log^2 n)\). This argument is independent of the LZ origin of the interval: once an AVL grammar is given, the same top-down decomposition applies to any substring interval.

Lemmas 5 and 6 hold for arbitrary AVL grammars; Rytter’s construction is needed only for the initial size bound (Theorem 1).

5.2 Persistent AVL Grammars↩︎

We implement all grammar operations functionally, with every symbol immutable. Split, concatenation, insertion, deletion, and substitution create new symbols and reuse all unaffected old symbols. Therefore, every old version remains valid automatically, and any old root can be used as the input to a new update.

Substring equality and LCE follow Secs. 3 and 4, substituting grammar roots for tree roots. Temporary grammar splits yield range fingerprints, and the LCE algorithm in Sec. 3.3 uses the same strategy by Lipták et al.

We remark that this bound does not guarantee a size bounded by the LZ77 size \(z_t\) of later versions. Without rebuilding or dynamic parsing, the space depends solely on the initial grammar and the number of updates.

6 Experiments↩︎

We empirically evaluate \(\mathsf{FeAVL}\), the AVL-tree structure of Secs. 3 and 4, measuring running time and peak memory against the string length \(n\) and corroborating Theorems 2 and 3 and Proposition [prop:splaybad]. All plots vary one parameter on log–log axes, so the slope separates \(\mathcal{O}(\log n)\) from \(\mathcal{O}(n)\). Each data point is the total wall-clock time of a fixed number \(Q\) of queries, averaged over five runs on a single fixed-seed input. Operands are uniform random, except for equality and the worst case, which use constructed inputs.

The experiments were run on Ubuntu 22.04.5 LTS (64-bit) with \(64.0\) GiB of memory and an AMD Ryzen Threadripper 3990X, compiled with g++ 12.3.0. We implement three approaches in C++ and compare them: the naive array, where \(\mathsf{access}\) costs \(\mathcal{O}(1)\) and the other operations \(\mathcal{O}(n)\) (with \(\mathsf{equal}\) in \(\mathcal{O}(\ell)\)); the splay-based FeST of [4] and its path-copied persistent version; and our \(\mathsf{FeAVL}\).

6.1 Dynamic Operations↩︎

With \(Q = 10^4\) queries, extraction and introduction, a composition of split and concatenate, scale logarithmically for both trees and linearly for the naive array; the trees are faster beyond \(n \sim 10^5\) (Figure 1 (a)), consistent with Theorem 2. For equality we fix \(n = 2\times10^6\) and vary the match length \(\ell\) over a fully matching range. \(\mathsf{FeAVL}\) and FeST stay nearly constant in \(\ell\) (about \(0.25\) s and \(12\) ms, respectively; \(\mathcal{O}(\log n)\) by fingerprints), while the naive array grows linearly to about \(2.4\) s at \(\ell = 10^6\) (\(\mathcal{O}(\ell)\)), consistent with Corollary 1 (Figure 1 (b)); persistent equality behaves identically.

6.2 Persistent Operations↩︎

With \(Q = 10^4\) queries, persistent introduction scales logarithmically for both trees and linearly for the naive per-version copy; the crossover is near \(n \sim 2\times10^4\) (Figure 2 (a)), consistent with Theorem 3. For space we issue \(Q = K = 10^5\) introductions, retain every resulting version, and vary \(n\): per version the trees use \(\mathcal{O}(\log n)\) and the naive array \(\mathcal{O}(n)\), so the totals are \(\mathcal{O}(n_0 + I + U\log n_{\max})\) and \(\mathcal{O}(K n)\), respectively (Sec. 4). At \(n = 10^5\) the naive array reaches about \(20\) GB while the trees use about \(0.5\) GB (Figure 2 (b)); the per-node overhead makes the trees heavier only up to \(n \sim 10^3\).

6.3 Worst Case of Splay-Based FeST under Persistence↩︎

To confirm that our \(\mathsf{FeAVL}\) avoids the persistent worst-case degradation of the splay-based \(\mathsf{FeST}\), we repeatedly apply the access pattern that triggers it. We first force the tree into a path by accessing positions in ascending order, and then issue \(Q = 10^3\) accesses to the deepest position \(0\) while varying the size \(n\) (Figure 3). This reflects Proposition [prop:splaybad]: discarding the splayed result leaves the base version as a path. Consequently, the execution time of \(\mathsf{FeST}\) scales linearly (\(\sim 42\) s at \(n = 10^5\)) generating \(\Theta(n)\) new nodes, whereas \(\mathsf{FeAVL}\) takes near-constant time (\(0.2\) ms) and the naive array takes \(\mathcal{O}(1)\).

7 Conclusions↩︎

We presented \(\mathsf{FeAVL}\) and its grammar-compressed variant to make the FeST paradigm [4] fully persistent by replacing splay trees with worst-case balanced structures. This achieves worst-case (near-)logarithmic time for dynamic operations and LCE queries, with the compressed version yielding a total size of \(\mathcal{O}(g_0+I+U \log n_{\max})\), with initial size \(g_0=\mathcal{O}(\min\{n_0,z_0\log n_0\})\).

Future work includes applying our data structure to large-scale real-world versioned documents like software repositories and genome databases [13]. A particularly interesting application in bioinformatics is simulating pangenomic evolution and phylogenetic trees, which models mutations and sequence recombinations (via split and concatenate) while maintaining full historical states [14].

References↩︎