阅读中文版本

Trie Autocomplete CLI

A Node CLI that builds a trie from a word list and prints autocomplete suggestions for a prefix, sorted by frequency.

node --version

node trie.mjs words.txt hel

node --test trie.test.mjs

Prints words from the word list that start with the given prefix, sorted by frequency (occurrence count in the list).

What it does

Builds a trie from a word list, where each node is a map from character to child node and terminal nodes store a frequency and the full word. For a prefix query, it navigates to the prefix node, walks the subtree to collect all completions, and sorts by frequency.

import { readFileSync } from 'node:fs';
const root = {};
for (const w of readFileSync(process.argv[2], 'utf8').split('\n')) {
  let node = root;
  for (const ch of w) node = node[ch] ??= {};
  (node.$ ??= [0, w])[0]++;
}
const prefix = process.argv[3];
let node = root;
for (const ch of prefix) { node = node[ch]; if (!node) { console.log('no matches'); process.exit(0); } }
const results = [];
const walk = (n) => { if (n.$) results.push(n.$); for (const k in n) if (k !== '$') walk(n[k]); };
walk(node);
results.sort((a, b) => b[0] - a[0]).forEach(([f, w]) => console.log(w + ' (' + f + ')'));

Run and verify

node trie.mjs words.txt hel

Run the test command to check the implementation: node --test trie.test.mjs.

Expected Output

For a word list containing hello, help, helmet with frequencies, the prefix hel prints:

hello (3)
help (2)
helmet (1)

Limitations

The trie is rebuilt from the word list on every run. The subtree walk is O(alphabet size * depth), which is fine for small completions but could be optimized with a per-node top-k cache.