Can ropes (AVL trees) be interned?

Question

Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?

---

I recently implemented a rope data structure in Lua as an AVL tree.

However, I realized a since the ropes are not interned, they can't be used efficiently as keys in a dictionary. (Lua walks over all new strings made by concatenation or slicing in order to intern them, making these $\Theta(n)$ operations, but guarantees fast dictionary lookup by only comparing addresses)

Can AVL tree ropes (or another type of balanced tree) be interned in a similar fashion in better than $O(n)$ time? Can fast interning be proved impossible?

Below is what I have thought of so far. I haven't found any resources about interning non-string data structures.

• Hashing: You can efficiently determine the hash value of a concatenation or a slice with extra bookkeeping for some hash schemes (like Java's). However, you can't guarantee there are no collisions in these hashes (and actually their slicability/concateability can make them very easy to attack).

• Normalizing: There are many different shapes that AVL trees with identical contents can take on. I could try to pick one special form for each size and designate it as the "canonical" form. When new trees are made when concatenating or slicing, in addition to balancing the tree, we reshape it to its canonical form. Naively this should not be efficient, because the vast majority of forms for a given size are $O(n)$ edits away from any particular canonical form. However, maybe if all subtrees are given some particular form, canonicalizing can be made efficient.

  I tried the obvious perfectly-balanced tree as the canonical shape, but I couldn't make an efficient way to concatenate these. Another version I considered was "as left leaning as possible" but this had the same result.

Answer 1

I'll present two candidate solutions.

Solution #1: Associative hashing

Yes. You can associate a hash value with the contents of any binary tree data structure (including a rope). The basic idea is that you augment each node of the tree to store a hash value. The hash for a node is $H(h_1,\dots,h_k,x)$ where $h_1,\dots,h_k$ are the hashes on its $k$ children and where $x$ is the value stored in the node. In this way, any time you update a node, you can update its hash (and all of its ancestors' hashes) in $O(\log n)$ time. Since all operations take $O(\log n)$ time anyway, this doesn't increase the asymptotic time of the basic tree operations. Now the hash value at the root of the tree summarizes the contents of the entire tree, so can be used as the index into a hash table. Basically, you use that hash value instead of using the address of the object.

You don't need to worry about hash collisions. With a good hash function, hash collisions are sufficiently rare to not be worth worrying about. And if you're using a hashtable, you always have the possibility of hash collisions, so you need a good hash function in any case.

The big shortcoming of this approach is that it doesn't take care of normalization; the hash value reflects both the contents of the nodes as well as the structure of the tree, so if you have two trees with the same contents but with a different structure, they will end up with a different hash value. However, you can fix that up by a clever choice of the hash function. In particular, I suggest you use an associative hash function, which is a function $H$ and a binary operation $\cdot$ where $H(x) \cdot H(y) = H(x,y)$. Now you can use $h_1 \cdot H(x) \cdot h_2$ as the hash value for a node, where $h_1,h_2$ are the hashes of its two children and $x$ is the value stored in this node. In this way the hash value at the root will be equal to what you'd get if you concatenated all of the values at all of the nodes (in infix order), then hashed them. So now the hash value of the tree depends only on the contents of the tree, not on its structure.

Where do you find an associative hash function? They take some cleverness to construct, but one option is to let $H$ denote the $SL_2(\mathbb{F})$-based hash function in https://crypto.stackexchange.com/a/17936/351 and $\cdot$ represent matrix multiplication.

With this technique, my construction is now normalizing as well, and it should be efficient.

Solution #2: SeqHash

A possible alternative would be to use the SeqHash data structure from the following paper:

VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich. CCS 2014.

This data structure lets you store a sequence of characters in a deterministic tree-based data structure. In particular, it provides a hash of the data in the data structure that is normalizing (because the data structure is deterministic). It also provides $O((\log n)^2)$ time insertion, deletion, concatenation, and lookup into the data structure. It's not a rope, but it might be a possible alternative to a rope that meets your interning requirements.

Related: see also Canonical representation of finite maps on non-overlapping finite rational intervals.