Data structures for annotations in large-scale text editor

Question

I need to create a specialized text editor capable of handling text up to billions of characters long, with no line breaks.

I've read of multiple data structures to manage the text itself, including ropes, zippers, piece tables, gap buffers, and more.

However, I also need to support annotations on the text. Like comments in MS Word, each annotation lies over a range of positions. (Unlike MS Word comments, each annotation may lie over multiple non-intersecting ranges.)

Annotations can cover a single character or the whole text. Annotations may be created before, in between, or after text edits.

There can be tens to hundreds of thousands of annotations. Reacting to each edit by adjusting the coordinates of every single feature would incur a large, linear cost.

What are data structures that would support the following, even as coordinates change due to text editing, whose complexity does not include the number of annotations as a factor?

1. Finding the coordinates of features discovered by text search, in the current coordinate system resulting from text edits made after the annotations.
2. Finding annotations that intersect a range presented to the user, in the current coordinate system resulting from text edits made after the annotations.

For 1, one idea I've had is to store a history of coordinate-system changes, and apply all of those made after the feature's creation. However, the cost of this grows linearly with the number of edits.

For 2, one idea I've had is to create a custom R-tree of annotations which reacts to text edits by modifying its own coordinate system but not its clustering. But not sure how to handle new features, which don't necessarily lie anywhere in the original coordinate system. And again, the cost of this could grow linearly with the number of edits.

Answer 1

There are many possible data structures you could use. I will list one.

Augmented balanced binary tree

Stores the string in a balanced binary tree. Each leaf of the tree holds one character of the document, and you store them in a balanced binary tree data structure: e.g., a red-black tree or AVL tree. In other words, you think of the tree as representing a map $i \mapsto S[i]$ that maps from an index $i$ to the $i$th character in the document.

This data structure will avoid the need to update the coordinate system by the simple expedient of not using any coordinate system at all. No indices or offsets are used explicitly. Instead, everything is represented implicitly in the shape of the tree.

Note that each internal node of the tree implicitly corresponds to a substring of the tree: namely, it is the substring obtained by concatenating all leaves that are descendants of that node. Equivalently, it corresponds to an interval of indices: namely, the interval $[\ell,r]$ where $\ell$ is the index of the leftmost leaf under that internal node and $r$ is the index of the rightmost leaf under that node.

Also any substring of the document can be expressed into a disjoint union of $\le \lg n$ substrings obtained in this way. Thus, if $T$ is a substring of the document, it can be viewed as corresponding to a set of $\le \lg n$ internal nodes of the tree (so that concatenating all of the leaves under those nodes yields exactly $T$).

Now you have a list of annotation objects, one per annotation. The annotation object stores the set of internal nodes that correspond to the substring it is attached to. Also, each internal node in the tree has a list of backpointers to annotation objects that it is associated with.

Now to attach an annotation to some substring $T$, you simply find the corresponding set of internal nodes, create an annotation object, and add backpointers to that object from each of those internal nodes. This can be done in $O(\lg n)$ time.

Similarly, to delete or insert into the document, you insert or delete into the balanced binary tree data structure. You can quickly identify which annotations this affects, by looking at the range of leaves affected, finding a list of $\le lg n$ internal nodes whose disjoint union is exactly that range, and following the backpointers in those nodes and all of their descendants. Then you can update those annotation objects if needed. Insertion and deletion doesn't disturb any of the annotations on the rest of the document, so there is no need to update any coordinate system.

What if you want to do random-access into the middle of document, i.e., given an index $i$, you want to quickly find the $i$th character in the document? You can augment the data structure to make this efficient, by storing in each node the number of leaves it has under it. If you insert or delete something somewhere in the document, then you update one or more leaves and all of the nodes on the path from those leaves to the root.

In this way, all operations can be performed in basically $O(\log n)$ time.