wire / wire-format / trie

Trie (prefix tree)

A trie (prefix tree) stores strings by their prefixes. Each node represents a prefix; edges are labeled with characters. Root = empty string. A path from root to node spells the key. Used for autocomplete, spell checking, IP routing (longest prefix match), and dictionary storage. Variants: radix tree (compressed trie, merges single-child chains), Patricia trie (binary radix tree), suffix tree (all suffixes of a string).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Trie (prefix tree)

wire format

spec: Trie (prefix tree)

A trie (prefix tree) stores strings by their prefixes. Each node represents a prefix; edges are labeled with characters. Root = empty string. A path from root to node spells the key. Used for autocomplete, spell checking, IP routing (longest prefix match), and dictionary storage. Variants: radix tree (compressed trie, merges single-child chains), Patricia trie (binary radix tree), suffix tree (all suffixes of a string).

fieldsizemeaning
NodevariableArray of child pointers (one per alphabet symbol) + terminal flag (is this a complete word?).
Edge1 characterEach edge is labeled with a character.
PathvariablePath from root to node spells the key.
Terminal flag1 bitMarks the end of a complete word.
Radix treevariantCompressed trie: merges chains of single-child nodes into a single edge with a string label.
Patricia trievariantBinary radix tree: each node has 2 children (0/1). Used for IP routing (longest prefix match).
Suffix treevariantTrie of all suffixes of a string. O(n) construction (Ukkonen's algorithm). Used for string matching.
Ternary search treevariantEach node has 3 children: less, equal, greater. More space-efficient than standard trie.

example:

00 00 00 00

Trie (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/trie or /wire-format/trie.json