wire / wire-format / trie
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).
aka: Trie (prefix tree)
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).
| field | size | meaning |
|---|---|---|
| Node | variable | Array of child pointers (one per alphabet symbol) + terminal flag (is this a complete word?). |
| Edge | 1 character | Each edge is labeled with a character. |
| Path | variable | Path from root to node spells the key. |
| Terminal flag | 1 bit | Marks the end of a complete word. |
| Radix tree | variant | Compressed trie: merges chains of single-child nodes into a single edge with a string label. |
| Patricia trie | variant | Binary radix tree: each node has 2 children (0/1). Used for IP routing (longest prefix match). |
| Suffix tree | variant | Trie of all suffixes of a string. O(n) construction (Ukkonen's algorithm). Used for string matching. |
| Ternary search tree | variant | Each node has 3 children: less, equal, greater. More space-efficient than standard trie. |
example:
00 00 00 00
Trie (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/trie
or /wire-format/trie.json