Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Double-array tries: static incident-code transitions with BASE and CHECK

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A double-array trie stores each transition at BASE[parent] plus the label number. CHECK at the resulting slot records the parent that owns it. A lookup must compare CHECK, because an occupied numerical slot can belong to an unrelated prefix. Terminal flags answer exact membership; reaching a prefix node alone does not prove that the prefix is a stored code. The builder first groups lowercase alphanumeric codes into a temporary trie, then searches for a free offset for each node's outgoing labels. It rejects an empty code and characters outside its declared alphabet. The temporary trie is only a build aid: queries use the three arrays. The output length counts allocated slots, including holes, rather than only live nodes. This is a frozen dictionary, so adding a new code requires rebuilding the arrays.

Operational case

The dictionary stores dock47, dock83, door29, and hub61. An exact query for dock47 succeeds, while dock is only a reachable prefix. A query for dome fails even though its first two letters share a path with stored codes. The sample array allocates 38 positions but owns only 17 nodes, including the root; that difference illustrates why a two-array representation is not automatically compact in a high-level runtime. If a label calculation lands on a slot whose CHECK names another parent, traversal stops immediately. The chosen offset is an implementation detail and must not be used as a stable code identifier.

Working Python program

python
class IncidentCodeIndex:
    def __init__(self, codes):
        root = {}
        terminals = set()
        for code in codes:
            if not code or any(character not in "abcdefghijklmnopqrstuvwxyz0123456789" for character in code):
                raise ValueError("codes must use lowercase letters or digits")
            node = root
            for character in code:
                node = node.setdefault(character, {})
            terminals.add(code)
        self.base = [0, 0]
        self.check = [-1, -1]
        self.terminal = [False, False]
        pending = [(1, root, "")]
        while pending:
            parent, children, prefix = pending.pop(0)
            self.terminal[parent] = prefix in terminals
            if not children:
                continue
            labels = [(self._label(character), character) for character in children]
            offset = 1
            while any(offset + label < len(self.check) and self.check[offset + label] != -1
                      for label, _ in labels):
                offset += 1
            self.base[parent] = offset
            for label, character in labels:
                slot = offset + label
                while len(self.check) <= slot:
                    self.base.append(0)
                    self.check.append(-1)
                    self.terminal.append(False)
                self.check[slot] = parent
                pending.append((slot, children[character], prefix + character))

    @staticmethod
    def _label(character):
        alphabet = "abcdefghijklmnopqrstuvwxyz0123456789"
        return alphabet.index(character) + 1

    def _walk(self, text):
        node = 1
        for character in text:
            if character not in "abcdefghijklmnopqrstuvwxyz0123456789":
                return None
            child = self.base[node] + self._label(character)
            if child >= len(self.check) or self.check[child] != node:
                return None
            node = child
        return node

    def contains(self, code):
        node = self._walk(code)
        return node is not None and self.terminal[node]

    def has_prefix(self, prefix):
        return self._walk(prefix) is not None


if __name__ == "__main__":
    index = IncidentCodeIndex(["dock47", "dock83", "door29", "hub61"])
    print(index.contains("dock47"), index.contains("dock"))
    print(index.has_prefix("dock"), index.has_prefix("dome"))
    print(len(index.base), sum(parent != -1 for parent in index.check))

Output

Output
True False
True False
38 17

Time, space, and tradeoff

A lookup or prefix test visits O(L) transitions for a length-L code and uses O(1) auxiliary query space. Building first takes O(S) nodes for S total input characters before prefix sharing; the naive first-fit offset search can scan many occupied slots per node, so it has no claimed linear construction bound. Array length depends on placement and alphabet gaps, and Python integer lists add object overhead. The temporary trie and queued prefixes also consume build memory proportional to the input, with repeated prefix strings adding copying cost. A pointer trie handles online insertion more naturally; this layout suits a static dictionary where fast indexed traversal is worth a separate build.

Common Mistakes

  • Do not accept a transition without checking its recorded parent.
  • Do not treat a reachable prefix as a terminal code.
  • Do not assume two arrays imply packed memory when placement leaves holes.
  • Do not edit the source code set without rebuilding the frozen index.

Connected lessons

Compare the operation boundary with Hopscotch hashing: keep each shipment near its home bucket, Invertible Bloom tables: peel differences between replica ID sets, De Bruijn graphs: compact non-branching k-mer routes into unitigs, then complete the audit project and decision quiz.

Adaptive radix trees: grow byte-edge nodes as incident codes branch examines a related structure with a different operation boundary.

Minimal acyclic dictionaries: merge equivalent word suffix states examines a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details