Trie Autocomplete Visualizer

Most lookups ask a yes or no question: is this exact thing stored? Autocomplete asks something looser. Given the few letters typed so far, which stored words could the person mean? That question has a shape of its own, and one old data structure fits it exactly.

Spelling your way to the answer

The structure is the trie. The NIST Dictionary of Algorithms and Data Structures defines it as a tree for storing strings in which there is one node for every common prefix. The root stands for the empty prefix. Each edge carries one character, so the path from the root to any node spells out a prefix, and two words that begin with the same three letters share the same first three steps. Looking a word up is not a search in the usual sense. It is a walk: take the edge for the first letter, then the edge for the second, and so on. The walk takes one step per character, however many other words share the tree.

That is why “what starts with this?” comes so naturally. Once the walk reaches the node for the typed prefix, every word that begins with it lies below that node and nowhere else. Nothing has to be filtered out of a larger pile. Everything outside that branch is simply never visited.

A hash table cannot do that. The authors of the adaptive radix tree put the contrast plainly: hash tables are fast but support only point queries, while their radix tree keeps its keys in sorted order and so allows range scans and prefix lookups. The Wikipedia article on tries adds that a trie needs no hash function and has no collisions between keys.

The order is free as well. If each node lists its children by edge label, a preorder walk of the tree visits the words in lexicographic order. The tree is a sort that has already been done.

The mark that makes a word

Now the subtle part. Store “card”, and the path c, a, r exists, because “card” needs it. Is “car” in the tree? The path alone cannot say. So each node carries one more bit of information: an end-of-word mark, set only where a stored word finishes. Without it, every prefix of every word would count as a word. Storing “careful” would quietly add “c”, “ca”, “car” and every other start of it to the dictionary. In the tool, a marked node is a square with a smaller square inside, and a node that is only a prefix is a plain circle. Shape, not colour, carries the difference.

Deleting shows the mark at work. Removing “carton” from a list that also holds “cart” clears the mark on the last node and then prunes the two nodes for “o” and “n”, since no other word passes through them. Removing “car” clears the mark and prunes nothing, because “card” still needs every step of that path.

The empty string is the edge case. Storing it would mark the root itself, so every prefix query would return it. The tool refuses it.

What counts as a character

Letters are not as simple as they look on screen. The MDN reference for string normalisation gives the classic case: an n with a tilde can be written as the single code point U+00F1, or as a plain n followed by the combining tilde U+0303. They look identical but compare unequal. A trie keyed on raw code points would build two separate paths for one word. Normalisation Form C, which MDN describes as canonical decomposition followed by canonical composition, brings both spellings to one form first. The example list in the tool types “cafe” with an acute accent both ways, with weights 22 and 5. Under NFC they become one word with weight 27.

There is a second trap underneath. JavaScript strings are sequences of 16-bit code units. Unicode code points run from 0 to 0x10FFFF, so anything above 65535 is stored as a surrogate pair, two units standing for one code point. Key a trie on code units and half an emoji ends up alone at a node, which is no character at all. In the example, the word “cat” followed by a cat emoji produces two such half nodes when read as units. Iterating a string yields whole code points and keeps every pair intact. It does not keep grapheme clusters together, though, so an emoji assembled from several code points still takes several steps down the tree.

Case is a choice rather than a fact. The Unicode case folding file maps characters so that differences of case disappear, and its full folding lets “FUSS” match the German spelling with a sharp s. The same file warns that folding does not preserve normalisation, so a careful pipeline normalises again afterwards. Fold when “Car” and “car” should be one suggestion. Keep case when they are different things, as product codes often are. In the example, folding merges “Car” into “car” and its weight becomes 43.

Squeezing the chains

A plain trie spends a node on every single letter, including letters where nothing ever branches. In “careful”, the nodes for “f” and “u” each have one child and no mark. They exist only to hold one letter on the way somewhere else. In 1968 Donald Morrison published PATRICIA, an algorithm whose abstract stresses that it is economical of index space. The NIST entry for the Patricia tree, also known as the radix tree, describes the idea compactly: a node that is an only child is merged with its parent. Do that along every chain of unmarked single-child nodes and the chain becomes one edge with a longer label, “ful” in place of three separate steps.

Here is the worked example, which the tool loads on first visit. Seventeen lines go in. NFC merges the two spellings of the accented word, so 16 words remain. The plain list holds 67 code points. The trie needs 31 nodes, counting the root, joined by 30 edges, and so it stores 30 of 67 code points, one per edge, because shared starts are stored once. Compression takes it from 31 to 19 nodes. The radix tree’s labels still add up to 30 code points: compression moves letters onto fewer, longer edges rather than deleting any. What it saves is nodes, and with them the pointers between nodes.

The compressed form can also be grown directly. Add “carefree” to the radix tree and the walk reaches the node for “care”, whose edge toward the leaf reads “ful”. The new word agrees with that label for one letter and then leaves it, so the edge splits after “f”: a new node for “f” now has two children, “ul” and “ree”. Built this way, the radix tree comes out identical to one compressed from the full trie after the insertion.

How much memory any of this takes depends on how a node keeps its children, and the honest way to discuss that is arithmetic, not a benchmark. An array as wide as the alphabet gives every node a slot for every possible next letter. The example uses 17 distinct code points, so 31 nodes need 527 slots, of which 30 are ever filled. A map needs one entry per child, 30 in all. A first-child and next-sibling list needs two pointers per node, 62.

The adaptive radix tree paper notes that excessive worst-case space plagues most radix trees, and its answer is to pick a compact node structure to suit each node. These are counts of slots, not bytes; the language, the allocator and the spare room inside a map all change the real figure.

Ranking what comes back

A list of completions needs an order, and alphabetical order is rarely what a person wants. Hsu and Ottaviano state the basic problem of query auto-completion in their 2013 paper: retrieve from a string set a small number of completions, the strings beginning with a given prefix, that score highest under some static ranking. In the tool, the score is a weight the visitor supplies next to each word.

The method is short. Visit every word below the prefix and keep the best k so far in a min-heap of size k, a priority queue whose top is the weakest word still kept. A new candidate replaces that top only when it ranks higher. With m words below the prefix this costs about m log k steps, so asking for five suggestions out of a thousand candidates stays cheap. Ties need a rule, or the same list can come back in different orders on different days. Here equal weights fall back to code point order of the word.

With the prefix “car” and k set to 5, the example ranks car 40, care 31, card 25, cart 18 and careful 12, and carton, at 6, misses the cut. The trie visits 4 nodes on the way down, root included, and 9 below. The radix tree visits 3 and 6.

Plain code point order is a different walk. It can stop as soon as k words are found, and here it visits 7 nodes below the prefix. Remember that it is not a dictionary’s order: a capital Z, U+005A, sorts before a lowercase a, U+0061.

What a prefix tree will not do

It matches exact prefixes only. A typo in the first letter sends the walk down the wrong branch, and nothing in the structure notices; tolerant matching is a separate algorithm. The weights are static, so the ranking knows nothing about who is typing or what they asked a minute ago. Very large sets need compressed representations, which is the subject of the 2013 completion paper. And the Wikipedia article notes that a trie can lose to a hash table when the data is read straight from storage with slow random access, such as a hard disk.

Last, the name. Rene de la Briandais described the structure for a computer in 1959. Edward Fredkin described it independently in his 1960 paper “Trie memory” and coined the word from the middle of “retrieval”. NIST quotes a note Fredkin wrote in 2008: he meant it to be said “tree”, combining the structure and its purpose. Many people say “try” anyway, so that a trie and a tree can be told apart out loud.