Meta
Cheguei bem longe trabalhando com IA para me ajudar a construir um Trie para encontrar palavras que rimam. Basicamente, digamos que você tem 10 milhões de palavras em inglês escritas usando o sistema de pronúncia CMU , onde cada fonema é um nó no Trie ( ARPABETnesta imagem).
Aqui estão os principais recursos:
- Os nós Trie são símbolos ASCII 1+ . Como
Bpara o som "b" eCHpara o som "ch", etc. - Trie pode paginar e pular de uma página específica. Então, ele pega uma propriedade
limit, epage. - A paginação pode ser opcionalmente limitada a correspondências de um comprimento de sequência de fonemas em particular . Como fonemas de
g l a dseriam 4. - A entrada de pesquisa Trie (fornecida pelo usuário) é uma matriz de fonemas . Fonemas são as unidades de som em ASCII (como o
ARPABETacima). - A entrada para o trie é expandida para todas as rimas possíveis . Ela é expandida usando um mapa de fonema para array de fonemas (implementado apenas parcialmente na função abaixo, levará semanas para ajustar adequadamente os valores aqui, o que preciso de TODO em breve).
- Podemos chamar a entrada expandida de "
rhymingPhonemeArray" . - Cada sequência de fonemas no
rhymingPhonemeArrayé ponderada . Por "ponderada", esse peso é basicamente "quão próximo o fonema mapeado está do fonema original". Isso é para que possamos dizer "essa sequência de fonemas (com um peso cumulativo menor ) é uma rima melhor do que essa outra sequência de fonemas norhymingPhonemeArray".
Problemas
O(s) problema(s) que estou enfrentando agora (com a solução que encontramos, compartilhada abaixo em JavaScript), são:
- Percorrendo todo o trie para encontrar todas as correspondências possíveis , o que não é otimizado. Idealmente, ele só percorre o que precisa (a página / quantidade limite e deslocamento).
- O Trie classifica todo o conjunto de correspondências depois , em vez de fazer o que queremos, que é obter a quantidade de páginas/limites já classificada. Este é o problema principal, não tenho certeza se/como ele pode fazer isso de forma otimizada, ou se é mesmo possível.
- O
rhymingPhonemeArrayé iterado por 😔 , então se estivermos paginando e orhymingPhonemeArrayfor como[G-A-D (cum-weight: 10), G-L-A-D (cum-weight: 24 or whatever), G-R-A-D (cum-weight: 29), etc.], você vai encontrar tudo que rima comG-A-Dprimeiro, então depois disso é paginado por, paginar porG-L-A-D, etc.. Eu gostaria de evitar esse agrupamento . Em vez disso, o peso cumulativo precisa ser classificado e paginado por meio do "conjunto global" de todas as 10 milhões de palavras.
Portanto, para (3), ele deve encontrar ( algo como isto):
input: G-A-D
matches:
G-A-D
G-L-A-D
A-G-A-D
A-R-G-A-D
G-R-A-D
A-G-R-A-D
A-R-G-L-A-D
A-R-G-R-A-D
...
Por "algo assim", quero dizer, observe como NÃO é assim (onde primeiro, todas as G-A-Dcorrespondências são encontradas, depois todas G-L-A-Dsão encontradas etc.):
input: G-A-D
matches:
G-A-D
A-G-A-D
A-R-G-A-D
G-L-A-D
A-R-G-L-A-D
G-R-A-D
A-G-R-A-D
A-R-G-R-A-D
...
Em vez disso, no primeiro matches, ele é mais entrelaçado , o que deve ser baseado no peso cumulativo global de cada palavra.
Pergunta
Como você pode modificar a seguinte "Implementação Trie" para resolver os problemas de 1, 2 e 3 acima? Nota: não precisa ser 100% exato, apenas buscando o insight chave sobre como resolver esse problema de paginação corretamente (mesmo que apenas em um nível alto/pseudocódigo). Eles são todos aspectos do mesmo problema subjacente, que é o que eu já declarei, mas declararei novamente:
A implementação do Trie abaixo não pagina corretamente e de forma um tanto eficiente as palavras classificadas por peso cumulativo global , que são correspondências exatas para
rhymingPhonemeArray(que é gerado a partir daphonemesentrada).
É possível resolver esse problema sem ter que iterar sobre o Trie inteiro? Dado (lembre-se), a entrada é expandida para rhymingPhonemeArray(o que pode ser um monte de possibilidades, mas vamos praticamente limitar a entrada a provavelmente 3 sílabas, além do ponto). Se não for possível, você pode explicar por que não é possível?
Se possível, como você modificaria esta tela para suportar paginação e pular para uma página específica sem precisar percorrer tudo, enquanto ao mesmo tempo os resultados paginados são classificados globalmente pelo peso cumulativo de cada palavra?
Implementação Trie
O Trie em que pousamos era este:
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"]Atualizações
- Aqui está um resumo com mais expansões/tentativas do Trie para resolver esse problema fundamental.
