Autocompleting words

Autocomplete is everywhere, IDE suggestions, search engines, you name it. It’s basically expected at this point!

Let’s try our hand at making a simple version of this from the basics. We’ll make a CLI autocomplete tool using a trie data structure.

Approach #

Trie data structure for prefix matching #

A trie (prefix tree) is perfect for autocomplete because it naturally organizes words by their prefixes. Each node represents a character, and paths from root to leaf spell out complete words.

This gives us some major advantages: prefix searches become path traversals, memory usage is shared across words with common prefixes, and completion generation is just collecting all paths from a prefix node.

Rather than scanning through word lists linearly, the trie lets us jump directly to the relevant prefix and enumerate completions from there. Each node knows whether it represents the end of a valid word and holds references to its character children.

Interactive terminal interface #

The interesting challenge is building a responsive terminal experience. Users expect TAB completion to work instantly, with completions updating as they type and clean visual feedback.

The interaction system handles several key behaviors:

• Real-time updates: Completions refresh as the user types each character
• TAB cycling: Multiple TAB presses cycle through available options
• Clean display: Completions appear below the current line without disrupting input
• Keyboard shortcuts: Enter to accept, Ctrl+C to exit, backspace updates dynamically

The result feels natural—like modern shell completion but optimized for word suggestions rather than file paths.

File scanning and dictionary building #

The tool needs to build comprehensive dictionaries from existing text files. It recursively processes directories looking for .txt and .md files, extracting meaningful words while filtering out noise.

The scanning system handles word extraction intelligently by splitting on whitespace, filtering short or purely numeric terms, and deduplicating entries. All extracted words get inserted into the trie for instant availability in interactive mode.

Building the trie system #

Core trie implementation #

The trie structure uses a simple but powerful design—each node contains a map of character children and a flag indicating word boundaries:

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class TrieAutocomplete {
  private root: TrieNode = new TrieNode();

  insert(word: string): void {
    let current = this.root;
    for (const char of word.toLowerCase()) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char)!;
    }
    current.isEndOfWord = true;
  }

  autocomplete(prefix: string, limit: number = 10): string[] {
    const results: string[] = [];
    const prefixNode = this.findPrefixNode(prefix.toLowerCase());

    if (prefixNode) {
      this.collectWords(prefixNode, prefix.toLowerCase(), results, limit);
    }

    return results;
  }
}

The trie insertion creates nodes as needed while traversing character by character. Autocomplete finds the prefix node and then recursively collects all valid word endings from that point.

Efficient completion collection #

The completion system uses depth-first traversal to gather words, but with smart optimizations to avoid scanning the entire subtree:

private collectWords(
  node: TrieNode,
  currentWord: string,
  results: string[],
  limit: number
): void {
  if (results.length >= limit) return;

  if (node.isEndOfWord) {
    results.push(currentWord);
  }

  for (const [char, childNode] of node.children) {
    this.collectWords(childNode, currentWord + char, results, limit);
  }
}

private findPrefixNode(prefix: string): TrieNode | null {
  let current = this.root;
  for (const char of prefix) {
    if (!current.children.has(char)) {
      return null;
    }
    current = current.children.get(char)!;
  }
  return current;
}

This approach stops collecting once the limit is reached and handles non-existent prefixes gracefully. The prefix traversal is fast because it follows a single path to the relevant subtree.

Interactive terminal handling #

Readline integration #

The interactive mode uses Node’s readline module with custom keypress handling to create a smooth completion experience:

class InteractiveMode {
  private trie: TrieAutocomplete;
  private rl: readline.Interface;
  private currentInput: string = '';

  start(): void {
    this.rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
      prompt: '> '
    });

    process.stdin.on('keypress', (str, key) => {
      if (key.name === 'tab') {
        this.handleTabCompletion();
      } else if (key.name === 'return') {
        this.handleEnter();
      }
    });

    this.rl.prompt();
  }

  private handleTabCompletion(): void {
    const completions = this.trie.autocomplete(this.currentInput, 10);
    if (completions.length > 0) {
      console.log('\n' + completions.join('  '));
      this.rl.prompt();
    }
  }
}

The keypress detection intercepts TAB before readline processes it, allowing us to show completions without interfering with the input buffer. The completion display appears below the current line and then re-prompts for continued typing.

Real-time completion updates #

As users type, the system continuously updates available completions without waiting for explicit TAB presses. This creates a responsive feel where the completion set narrows with each character:

private updateCompletions(): void {
  const completions = this.trie.autocomplete(this.currentInput);

  if (completions.length === 0) {
    this.showMessage('No completions found');
  } else if (this.currentInput.length === 0) {
    // Show random sample for empty input
    const randomSample = this.getRandomWords(5);
    console.log('Sample words: ' + randomSample.join('  '));
  }
}

private handleInput(input: string): void {
  this.currentInput = input;
  this.updateCompletions();
}

This keeps the interface feeling alive and responsive, with immediate feedback as the user’s input changes the available completion space.

File processing system #

Smart word extraction #

The file scanner processes text files intelligently, extracting meaningful words while filtering out noise like short strings, numbers, and punctuation:

class FileScanner {
  scanPath(path: string): string[] {
    const words = new Set<string>();

    if (fs.statSync(path).isDirectory()) {
      this.scanDirectory(path, words);
    } else if (this.isValidFile(path)) {
      this.scanFile(path, words);
    }

    return Array.from(words);
  }

  private extractWords(content: string): string[] {
    return content
      .split(/\s+/)
      .map(word => word.replace(/[^\w]/g, ''))
      .filter(word => word.length >= 3 && !/^\d+$/.test(word))
      .map(word => word.toLowerCase());
  }

  private isValidFile(filePath: string): boolean {
    return filePath.endsWith('.txt') || filePath.endsWith('.md');
  }
}

This processing pipeline removes punctuation, filters short and numeric terms, and normalizes to lowercase for consistent matching. The deduplication through Set ensures the trie doesn’t waste memory on duplicate entries.

Demo #

So the part we’re all curious about – let’s see it in action!

Wrapping up #

We kept this focused on core autocomplete functionality, but it’s straightforward to extend. The trie foundation supports more advanced features like fuzzy matching, word frequency ranking, or even collaborative dictionary sharing.

The full code for this can be found here: https://github.com/pdulapalli/basic-text-autocomplete