kart

Kart (key alteration radix tree) is an associative array data structure based on Patricia / critbit / radix trees. The main advantage of a kart is to expand the applicability of Patricia trees to more kinds of key sets. Karts retain the ordering, running time, and storage space characteristics of Patricia trees.

Structure

The structure of a kart is the same as that of a Patricia tree. To store a character string key in a tree, the key must be represented as a bit string. Each character's numeric value is considered to be a sequence of bits, with more significant bits occurring earlier in the sequence than less significant bits. So the key “Mario” is represented as “01001101 01100001 01110010 01101001 01101111”, assuming the ASCII character set. (Spaces inserted for readability.) This is not just a matter of low-level storage; the individual bits are significant to the algorithm. A Patricia tree containing the keys “Green Shell” “Mario”, “Mushroom”, and “Rainbow Road” would look like this:

An internal node specifies the index of the first bit at which the keys in the left subtree differ from the keys in the right subtree. In this example, all the keys have the first 3 bits the same. The bit at index 3 is where the differences start; “Rainbow Road” has a 1, so it belongs in the right subtree of the root node, while all other keys have a 0, so they belong in the left subtree. Within the left subtree, the next difference among the remaining keys is at bit 4: “Green Shell” has a 0, so it goes on the left; the others have a 1, so they go on the right. The last two keys differ at bit 11. “Mario” has a 0, so it goes on the left; “Mushroom” has a 1, so it goes on the right.

To search for the key “Mario”, we start at the root node, and inspect the bit specified in the node. Bit 3 in “Mario” is 0, so we recurse on the left subtree. The node at the top of this subtree specifies bit index 4, so we inspect bit 4 of “Mario”; it's 1, so we go to the right subtree. This brings us to a node that specifies bit 11, which is 0 in “Mario”, so we go left. Now we arrive at a leaf, which means this is the only remaining node where “Mario” might be in the tree. A full key comparison with this node's key shows that the search key is in the tree.

An unsuccessful search ends either at a leaf with a mismatched key comparison, or at an internal node that has an index that exceeds the range of bits in the search key.

As a storage space optimization, we can replace all but one leaf with an upward link to an internal node, and store the leaf's key in the internal node. This way, there is only one kind of node, and only half as many nodes. Leaf links are detected when the pointed-to node's bit index is less than or equal to the pointing node's index; normally, when following links down the tree, indexes get larger.

Key alteration

The limitation here is that two keys cannot both be stored in the tree if one is a prefix of the other. At the index where two keys differ, the tree can only hold keys that have a 0 or 1 at the index, not any which end at the index. This could be fixed by allowing internal tree nodes to have three children, but that incurs a storage space penalty for all internal nodes. We could also use a terminiation character to mark the end of all keys, but then that character could not be used within a key. So instead, we can apply a transformation to all keys. The transformed version of the key is not stored anywhere in memory; individual bits are calculated on the fly. The transformation works by inserting a 1 bit before each byte of the original key, and appending a 0 bit after the last byte. The transformed version of the key is used to search for a key and to decide where in the tree to store a key. This way, the point at which “Mario” and “Mario Circuit” differ is represented by a bit where “Mario” has 0 and “Mario Circuit” has 1:

The translated bit at position pos in a key k of length klen can be calculated as:

unsigned int bit(size_t pos, unsigned char const* k, size_t klen) {
  if (pos/(CHAR_BIT+1)>=klen) return 0;
  if (pos%(CHAR_BIT+1)==0) return 1;
  return (((unsigned int)k[pos/(CHAR_BIT+1)])>>(CHAR_BIT-pos%(CHAR_BIT+1)))&(unsigned int)1;
}

Since the structure of the tree and the individual nodes is the same as in a normal Patricia tree, there is no penalty in storage space. The bit() function runs in constant time, so there is also no penalty in runtime complexity. For a tree of N nodes with a maximum key length of k (N=O(2k)), worst-case tree traversal is O(N) (the tree may be very unbalanced), but also O(k), since each step of the traversal examines one new bit from the search key. The final full key comparison is also O(k). (Analyses of other structures often ignore the cost of key operations: hash table lookups are often described as being O(1) in the best case, but this really means O(k).) The only penalty of karts, as compared to Patricia trees, is in maximum key length—a key whose length is the maximum size_t value, or close to it, can no longer be used, since each key is inflated by (assuming 8-bit bytes) 12.5% in translated form, and the translated length would not be representable in size_t. In practice, keys of this length are extremely unlikely.

Other key types

Only two basic operations are needed on a data type to use it as a key. Each value of the type must have a single, unique corresponding bit string representation; one operation fetches the Nth bit of the bit string for a given key value. The other finds the first bit where two keys differ, or indicates that the keys are equal. No key's bit string representation may be a prefix of another key's bit string. This can be ensured by making the bit strings be of the same length for all key values, or have inserted flag bits at each point where the bit string might end to indicate whether it does end there. To support the widest set of fast operations, the lexicographic order of the bit strings would match the natural order of the key values. But if entries will always be looked up using complete, exact keys, and iteration through entries need not be in any particular order, then the lexicographical order of the bit strings is not important.

Higher-dimensional compound values can also be used as keys. The method given above of inserting flag bits indicating the presence of another array element produces a unique bit string for a given list of element values, even if the bit strings for different elements are of different lengths, and even if the elements themselves are compound types. The bit() function will be more complicated with such complex keys. The function calculating the Nth bit of the outermost array must first figure out which of its elements to dispatch to, which requires knowing the length of each element's bit string (a new required operation). Deciding which element to dispatch to could then be done using a secondary Patricia tree, keyed with the cumulative lengths of the bit strings of the array elements. So we lose the simple O(k) tree traversal time, but the cost of a full key comparison rises even more, so karts remain attractive compared to other ordered trees that use multiple full key comparisons per traversal.

This is enough if the structure of all keys in a given tree will be the same, even if the keys are of different sizes. But if two keys may have different structures - being of different types themselves, or being compound types holding elements of different types in the same position - then the bit string for each element must first include a few bits to indicate which type of data is in this slot, followed by the bits encoding the data itself. Likewise for unions.

Bit strings for deep compound structures will grow even longer than for plain strings, with inflation due to inserted marker bits at each level. So the limit for key lengths at the innermost levels of these structures will drop further, or else will lead to using larger integer types as bit addresses.

Floating-point keys

Other transformations are possible for other kinds of keys. (Normalized) floating-point numbers can be represented like so:

• Negative infinity: all 0 bits.
• Positive infinity: all 1 bits.
• Finite negative numbers: 0, 1, the inverted bits of the exponent, and the inverted bits of the significand.
• Finite positive numbers: 1, 0, the bits of the exponent, and the bits of the significand.
• Zero: 1 followed by all 0 bits.

This encoding makes the lexicographic ordering of the bit strings match the numeric order. NaNs could be represented in a variety of ways, depending on where in the lexicographic order we want them to fall. A one-dimensional array of floating-point numbers could be handled similarly to strings above.

Bignum keys

Bignums, like text strings, can be of arbitrary length. But unlike text strings, they are “right-justified” instead of “left-justified”. That is, for text strings, their most significant bits are of equal rank for comparison purposes, and they could be padded with zeros at the least significant end. For bignums, their least significant bits are of equal rank, and they could be padded with zeros at the most significant end. This makes bignums hard to handle - if we designate the bit index where two bignums differ as an offset from the most significant bit between the two of them, then that index will have to be recalculated if we ever include another key that has more significant bits than either of the first two.

To avoid this problem, we could use bit indexes that indicate backward offsets from the least significant end of the bignums' bit strings. This means indexes would decrease as we progress down the tree. In the key transformation, all bit strings would be padded with infinitely many zeros at the most significant end. Since the key “0x” is considered identical to the key “x”, we wouldn't need to insert marker bits to indicate where the key actually ends. However, creating a tree containing bignum keys mixed with other key types, or compound keys with bignum elements, is not handled by this bit string transformation.

Alternatively, we could use bit offsets from the most significant end, where all bit strings are padded out to a length equal to the maximum value of the type used to hold bit indexes. The padded bit strings are then all of the same length, so they can be considered “left-justified” as well as “right-justified”. This way, bit indexes increase as usual as we progress down the tree. But the bit string for a single bignum key occupies the entire space of bit indexes, so we still can't include bignums as elements of compound keys. We can, however, mix bignums with other key types by adding a type code at the beginning of the bit string, and padding bignums out a little less to make room.