Autocomplete Demystified: A Common Use-Case of Trie

Imagine this: You're typing a friendly message in a WhatsApp group directed to one of your peers, and your fingers, seemingly possessed by a digital imp, instead of typing 'far too nice', types 'fart oo nice'. Now everyone thinks you're a creep. Frustrating, right? Fear not! Trie is the unseen sidekick behind your keyboard here to maintain your public image.

How 'Trie' Solves the Typo Trouble

Think of Trie as your personal autocorrect wizard. When you type a word, Trie steps in to predict what you're trying to say. It's like having a smart assistant that finishes your sentences, but for typing!

Imagine you're typing "eleph." Trie jumps in and goes, "Ah, you must mean 'elephant'!" It's like magic—no more wrestling with the keyboard to spell out every word perfectly.

So, How Does It Work?

I'll do something different here. Instead of starting off with a written explanation, I'll do a visual walkthrough on how the Trie works (yes, I also happen to be an artist). If the visual explanation doesn't work for you, feel free to read on!

trie diagram

Picture Trie as a giant family tree of words. Each letter in a word is like a family member. The journey from the root ( the grandparent) to the leaves (the kids) spells out a complete word.

Let's say you've typed "eleph." Trie checks its family tree and quickly realizes that "eleph" fits perfectly into the " elephant" branch. Voila! It suggests the complete word without missing a beat.

A Friendly Go-Away Message

This silent sidekick is also evident in other aspects of your life other than Autocorrect. An example most of us might relate to: Browser History. So for those clandestine folks who toggle 'Incognito Mode' at those wee hours to remove traces of their online presence, think of the 'Trie' and it's selfless contributions next time you do this.

Feel free to share your feedback especially if something wasn't clearly explained!

If you are intrigued by the inner workings of Trie, and ready for a deep dive into the digital ocean (don't sue me, digitalocean), keep reading. The next section is where we unveil the code sorcery behind Trie for our tech-savvy friends. Also, if you have already read the previous blog titled: 'Unveiling the Trie: A Masterstroke for Efficient String Searches', you can stop here (but you don't have to :-)).

Gentlemen, and women, and everyone else, shall we?

A brief introduction to Trie: it's a data structure (similar to an array, a list, a tuple etc.) that stores data as a tree where the branch of the tree traces out the path to where the data is, i.e. the leaf nodes/child nodes.

Here's the link to the GitHub repository with the full implementation.

Now, let's get hands-on with some JavaScript code!

Here's our Trie implementation:

// Trie Node
function TrieEntry(word) {
  this.word = word;
  const words = [];
  for (let i = 0; i < 26; i++) {
    words.push(null);
  }
  this.words = words;
}

// Main Trie Dictionary
function TrieDictionary() {
  const letterToIndexMapping = {
    "a": 1,
    "b": 2,
    "c": 3,
    "d": 4,
    "e": 5,
    "f": 6,
    "g": 7,
    "h": 8,
    "i": 9,
    "j": 10,
    "k": 11,
    "l": 12,
    "m": 13,
    "n": 14,
    "o": 15,
    "p": 16,
    "q": 17,
    "r": 18,
    "s": 19,
    "t": 20,
    "u": 21,
    "v": 22,
    "w": 23,
    "x": 24,
    "y": 25,
    "z": 26,
  }

  this.root = new TrieEntry();

  this.insertWord = (word) => {
    const wordChars = word.toLowerCase().split("");
    let currWord = "";

    let currSlot = this.root;
    for (const char of wordChars) {
      currWord += char;
      // traverse our root adding each char.
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (arraySlotForChar) {
        currSlot = arraySlotForChar;
      } else {
        currSlot.words[idx] = new TrieEntry(currWord);
        currSlot = currSlot.words[idx];
      }
    }
  }

  this.searchWord = (word) => {
    const wordChars = word.toLowerCase().split("");

    let currSlot = this.root;
    for (const char of wordChars) {
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (!arraySlotForChar) {
        break;
      }
      currSlot = arraySlotForChar;
    }
    return currSlot.word === word;
  }

  this.printDictionary = () => {
    const printRecursively = (entry) => {
      if (!entry) return "";

      for (const en of entry.words) {
        if (en) {
          console.log("en: ", en);
          console.log("--------------------");
        }
        printRecursively(en);
      }
    }

    printRecursively(this.root);
  }
}

Why Trie? A Performance Benchmark Comparison Between Trie and Linear Search

Feel free to run the code directly on your machine if you'd prefer a more hands-on approach.

1. Dictionary Population (1049938 words)

Adding words to our Trie is a breeze. Here's the javascript code sample:

const trieDict = new TrieDictionary();
const wordsDictionary = ["apple", "banana", "orange", /* ...a million more words */];

const start = new Date();
for (const word of wordsDictionary) {
  trieDict.insertWord(word);
}
const end = new Date();

const elapsedTime = (end - start) / 1000;
console.log(`Trie Population Time: ${elapsedTime} seconds`);

Dictionary population (1049938 words) timestamp start:  1699963909921
Timestamp after population:  1699963911482
Trie Population Time:  1.561
------------------------------------------------------------

In a mere 1.561 seconds, our Trie is ready to rock and roll with over a million words. Impressive, isn't it?

2. The Great Search Showdown

Now, let's pit Trie against the traditional linear search in a battle for supremacy. Our contenders: Trie vs. Linear Search!

const wordsToSearch = ["apple", "programming", "debugging", /* ...4,829 more words */];

// Linear Search
const linearSearchStart = new Date();
for (const word of wordsToSearch) {
  // ... linear search logic
}
const linearSearchEnd = new Date();

// Trie Search
const trieSearchStart = new Date();
for (const word of wordsToSearch) {
  trieDict.searchWord(word);
}
const trieSearchEnd = new Date();

// Calculating and Displaying Results
const linearSearchTime = (linearSearchEnd - linearSearchStart) / 1000;
const trieSearchTime = (trieSearchEnd - trieSearchStart) / 1000;

console.log(`Linear Search Time: ${linearSearchTime} seconds`);
console.log(`Trie Search Time: ${trieSearchTime} seconds`);

Drumroll, please! The results are staggering:

Linear Search Time: 8.839 seconds
Trie Search Time: 0.004 seconds

Yes, you read it right! Trie search takes a mere fraction of a second, showcasing a jaw-dropping 2200X performance boost!

Use-Cases: 'Trie's' Playgrounds

1. Autocomplete During Search

Ever wondered how autocomplete in search bars works seamlessly? Trie is the wizard behind the curtain, swiftly predicting your next word as best as it can.

2. Spell Checking

Tries are responsible for checking typos and spelling mishaps. It detects errors with the swiftness of a well-optimized algorithm, making corrections before you finish typing "debug."

Wrapping it Up: Trie and the Future of Performance

In the blink of an eye, Trie has transformed the landscape of our search experiences. With its unparalleled speed in word insertion and instant searches, this data structure emerges as a strategic asset for software optimization.

As you navigate through the complexities of code, consider the Trie as a reliable companion, streamlining your path through the intricate web of linguistic data.

Before we part ways, contemplate this: How might integrating Trie elevate the efficiency of your software projects? Share your insights in the comments below! Stay tuned for our upcoming tech discussions, where we'll unravel more coding intricacies.

Wishing you seamless coding journeys!