Unveiling the Trie: A Masterstroke for Efficient String Searches

Welcome back, fellow developers! In our last rendezvous, we deciphered the intricacies of recursion, peeking into the call stack and heap dynamics. Today, we embark on a journey to unravel the mysteries of the Trie data structure, a silent hero in the realm of efficient string searches. So buckle up your code belts and let's dive in! Here's a link to the original post.

The ABCs of Trie: What is it?

Imagine a dictionary, organized not alphabetically, but in a way that groups words by common prefixes. That's essentially what a Trie (pronounced "try") is—a tree-like data structure where each node represents a single character. It's a linguistic maze where the journey from the root to a leaf node spells out a complete word.

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 Awesomeness

Ever wondered how autocomplete in search bars works seamlessly? Trie is the wizard behind the curtain, swiftly predicting your next word with unparalleled speed.

2. Spell Checking Sorcery

Trie is your vigilant guardian against 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!