Como construir um trie para encontrar correspondências fonéticas exatas, classificadas globalmente por peso e paginadas? (Construindo a partir deste exemplo)

class TrieNode {
  constructor() {
    this.children = {}; // Store child nodes
    this.isWord = false; // Flag to check if node marks the end of a word
    this.word = null; // Store the word if this is an end node
    this.cumulativeWeight = 0; // Store the cumulative weight for sorting
    this.phonemeLength = 0; // Length of the phoneme sequence
  }
}

class PhoneticTrie {
  constructor() {
    this.root = new TrieNode(); // Root node of the trie
  }

  // Insert words and phoneme clusters into the Trie
  insert(word, phonemes, weight) {
    let node = this.root;
    for (let phoneme of phonemes) {
      if (!node.children[phoneme]) {
        node.children[phoneme] = new TrieNode();
      }
      node = node.children[phoneme];
    }
    node.isWord = true;
    node.word = word;
    node.cumulativeWeight = weight; // Store the cumulative weight at this node
    node.phonemeLength = phonemes.length; // Store the length of the phoneme sequence
  }

  // Global sorting of rhyming phoneme matches using a min-heap
  searchWithPagination({ phonemes, limit, page, length }) {
    const minHeap = new MinHeap(); // Min-Heap to store sorted results

    // Generate rhyming phoneme variations
    const rhymingPhonemesArray = expandToRhymingPhonemes(phonemes);

    // Search the Trie for all rhyming phoneme sequences and insert results into the global heap
    for (let rhyme of rhymingPhonemesArray) {
      this.searchAndInsertToHeap(rhyme.phonemes, this.root, rhyme.weight, minHeap, length);
    }

    // Paginate results directly from the globally sorted heap
    const paginatedResults = [];
    const startIndex = (page - 1) * limit;
    let index = 0;

    while (minHeap.size() > 0 && paginatedResults.length < limit) {
      const wordData = minHeap.extractMin();
      if (index >= startIndex) {
        paginatedResults.push(wordData.word);
      }
      index++;
    }

    return paginatedResults;
  }

  // Search a specific phoneme sequence in the Trie and insert matches into the heap
  searchAndInsertToHeap(phonemes, node, rhymeWeight, heap, targetLength, depth = 0, phonemeSeq = []) {
    if (depth === phonemes.length) {
      if (node.isWord && node.word) {
        // If length filtering is specified, ensure the word matches the phoneme length
        if (!targetLength || node.phonemeLength === targetLength) {
          heap.insert({
            word: node.word,
            cumulativeWeight: node.cumulativeWeight + rhymeWeight, // Add the rhyme weight here
            phonemeLength: node.phonemeLength, // Include phoneme length for sorting
          });
        }
      }
      return;
    }

    const phoneme = phonemes[depth];
    if (!node.children[phoneme]) return; // No match
    this.searchAndInsertToHeap(phonemes, node.children[phoneme], rhymeWeight, heap, targetLength, depth + 1, [...phonemeSeq, phoneme]);
  }
}


class MinHeap {
  constructor() {
    this.heap = []; // Store the heap elements
  }

  // Insert an item into the heap based on its weight and phoneme length
  insert({ word, cumulativeWeight, phonemeLength }) {
    this.heap.push({ word, cumulativeWeight, phonemeLength });
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    let currentIndex = index;
    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      // Sort primarily by cumulative weight, secondarily by phoneme length
      if (
        this.heap[currentIndex].cumulativeWeight > this.heap[parentIndex].cumulativeWeight ||
        (this.heap[currentIndex].cumulativeWeight === this.heap[parentIndex].cumulativeWeight &&
          this.heap[currentIndex].phonemeLength > this.heap[parentIndex].phonemeLength)
      ) {
        break;
      }
      [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
      currentIndex = parentIndex;
    }
  }

  // Extract the item with the lowest weight
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  bubbleDown(index) {
    const lastIndex = this.heap.length - 1;
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let smallestIdx = index;

      if (
        leftChildIdx <= lastIndex &&
        (this.heap[leftChildIdx].cumulativeWeight < this.heap[smallestIdx].cumulativeWeight ||
          (this.heap[leftChildIdx].cumulativeWeight === this.heap[smallestIdx].cumulativeWeight &&
            this.heap[leftChildIdx].phonemeLength < this.heap[smallestIdx].phonemeLength))
      ) {
        smallestIdx = leftChildIdx;
      }
      if (
        rightChildIdx <= lastIndex &&
        (this.heap[rightChildIdx].cumulativeWeight < this.heap[smallestIdx].cumulativeWeight ||
          (this.heap[rightChildIdx].cumulativeWeight === this.heap[smallestIdx].cumulativeWeight &&
            this.heap[rightChildIdx].phonemeLength < this.heap[smallestIdx].phonemeLength))
      ) {
        smallestIdx = rightChildIdx;
      }
      if (smallestIdx === index) break;

      [this.heap[index], this.heap[smallestIdx]] = [this.heap[smallestIdx], this.heap[index]];
      index = smallestIdx;
    }
  }

  size() {
    return this.heap.length;
  }
}

function expandToRhymingPhonemes(phonemes) {
  // todo: this function would have a huge map of phoneme substitutions...
  const phonemeSubstitutions = {
    "k": ["g", "p"], // Example of substitutions for the phoneme "k"
    "æ": ["a", "e"], // Example for "æ"
    "t": ["d", "s"], // Example for "t"
  };

  const rhymingPhonemesArray = [];

  function generateRhymes(sequence, depth = 0, currentWeight = 0) {
    if (depth === sequence.length) {
      rhymingPhonemesArray.push({ phonemes: sequence.slice(), weight: currentWeight });
      return;
    }

    const phoneme = sequence[depth];
    const substitutions = phonemeSubstitutions[phoneme] || [phoneme];

    for (const sub of substitutions) {
      generateRhymes(
        [...sequence.slice(0, depth), sub, ...sequence.slice(depth + 1)],
        depth + 1,
        currentWeight + (sub === phoneme ? 0 : 1)  // Substitution adds to weight
      );
    }
  }

  generateRhymes(phonemes);
  return rhymingPhonemesArray;
}

const trie = new PhoneticTrie();
trie.insert("glad", ["g", "l", "a", "d"], 3);
trie.insert("grad", ["g", "r", "a", "d"], 2);
trie.insert("blad", ["b", "l", "a", "d"], 4);
trie.insert("grin", ["g", "r", "i", "n"], 5);

// Search for similar words to "g-l-a-d" and paginate the results, with optional length filtering
const resultsPage1 = trie.searchWithPagination({
  phonemes: ["g", "l", "a", "d"],
  limit: 2,
  page: 1,
  length: 4, // Only consider words with exactly 4 phonemes
});

const resultsPage2 = trie.searchWithPagination({
  phonemes: ["g", "l", "a", "d"],
  limit: 2,
  page: 2,
  length: 4,
});

console.log(resultsPage1); // Output: ["grad", "glad"] (sorted by weight and length)
console.log(resultsPage2); // Output: ["blad", "grin"]