What is the point of the “check” array in a triple-array trie?

Question

I am currently reading the definition of a triple-array trie as described here.

More precisely, I am trying to understand the nature of the three arrays:

• base. Each element in base corresponds to a node of the trie. For a trie node s, base[s] is the starting index within the next and check pool (to be explained later) for the row of the node s in the transition table.
• next. This array, in coordination with check, provides a pool for the allocation of the sparse vectors for the rows in the trie transition table. The vector data, that is, the vector of transitions from every node, would be stored in this array.
• check. This array works in parallel to next. It marks the owner of every cell in next. This allows the cells next to one another to be allocated to different trie nodes. That means the sparse vectors of transitions from more than one node are allowed to be overlapped.

I understand how those three arrays are linked together, but I fail to see the point of the "check" array. It seems to me like you could walk the trie without using the "check" array at all.

What am I missing?

Answer 1

It is a bit confusing. Suppose the alphabet has size $\Sigma$.

Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next[] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid transitions from each state, check[] lets us "overlap" these blocks of $\Sigma$ elements, and thereby save space, provided there are no "collisions" -- that is, elements in next[] that correspond to valid transitions from more than one state.

A crucial piece of information that seems to be missing from the article (I only read down to the beginning of the next section, "Double-array Tree") is that initially all check[] values must have some special "no current owner" sentinel value (which in practice would be something like -1).

Think of each element in next[] as a resource slot, which can be either unallocated (as it is initially), or allocated to exactly one source state: check[i] tells you which source state the i-th element is allocated to (or if it is unallocated). The rule is: If a source state s does not own the slot in next[] that corresponds to the transition on some character c, then there is no valid transition from state s on character c. Specifically, check[base[s] + c] != s, which literally means "State s does not own slot base[s] + c in next[]", also implies "State s has no transition on character c".

In this way, all the elements of next[] that would have been set to a "this transition is invalid" sentinel value in the original every-state-gets-its-own-block-of-$\Sigma$-elements-in-next[]-to-itself scheme become available to be used by some other source state. If some such element, say at position i, is later needed by some other state s, then check[i] will be set to s at that time.

Example

First let's initialise the triple-array trie data structure.

Suppose the alphabet is the digits 0-9, the states range from 0-49, and we have the following transitions for state 17, to which we allocate the block of 10 elements starting at position 20 in next[]:

Transitions from state 17
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     3     |     40     |      23     |
|     5     |      6     |      25     |
|     8     |     13     |      28     |

After adding this information to the triple-array trie, base[17] = 20, next[23] = 40, next[25] = 6 and next[28] = 13, and check[23], check[25] and check[28] are all set to 17, with every other element in check[] remaining at its initial value of -1.

Now suppose we that we have the following transitions for state 35, to which we try to allocate the overlapping block of 10 elements starting at position 22 in next[]:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      24     |
|     3     |     33     |      25     | <-- COLLISION

There is a problem, since next[25] is needed by both source states. We detect this by noticing that check[25] != -1. In this case, either state 17's or state 35's range of slots in next[] has to be reallocated somehow. Let's reallocate state 35's range. First, undo the allocation already done (set check[24] back to -1; it is not necessary or helpful to change next[24] to anything, since there is no meaning attached to the value of next[i] when check[i] == -1). Now we will try to reallocate state 25's slot range to start at position 24 in next[]. (Why 24? It's just a value that I know will work. In practice, you would probably need to just keep trying different starting points until one worked, and there is no guarantee that any will work.) Now it looks like this:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      26     |
|     3     |     33     |      27     |

And there will be no collisions. So after adding the information for states 17 and 25 to the data structure, we will have base[17] = 20, base[35] = 24, and next[] and check[] look like this:

|  i  | next[i] | check[i] |
|-----+---------+----------|
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
| 20  |don'tcare|    -1    |
| 21  |don'tcare|    -1    |
| 22  |don'tcare|    -1    |
| 23  |   40    |    17    |
| 24  |don'tcare|    -1    |
| 25  |    6    |    17    |
| 26  |   10    |    25    |
| 27  |   33    |    25    |
| 28  |   13    |    17    |
| 29  |don'tcare|    -1    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |

Now let's try some queries.

1. Is there a transition from state 17 on character 5? First see if state 17 owns the relevant entry in next[]: check[base[17] + 5] = check[25] = 17, so it does (and the destination state is then given by next[25] = 6).
2. Is there a transition from state 35 on character 1? check[base[35] + 1] = check[25] = 17 != 35, so state 35 does not own this entry in next[] => there is no transition from state 35 on character 1.