Esencialmente, tengo un Conjunto de palabras, alrededor de 250,000 de ellas y quiero poder devolver una lista de las que se encuentran en una cadena determinada.
p.ej. la cadena de entrada es 'APPLEASEDITION', quiero regresar
[APP,APPLE,PLEA, PLEAS,PLEASE,PLEASED,lEA,LEAS,LEASE,LEASED,EA,EAS,EASE,EASED,AS,SEDITION,EDITION,IT,TI,ON]Se me ocurrió este código, que funciona más rápido que el método mencionado anteriormente para cadenas de entrada más cortas (hasta 15 caracteres), pero duplica el tiempo de ejecución con cada letra agregada:
const findWords = (instring, solutions = null) => { if (!solutions) solutions = new Set(); if (!instring) { return new Set(); } if (words[instring]) { solutions.add(instring); } const suffix = instring.slice(1); const prefix = instring.slice(0, instring.length - 1); if (!solutions.has(prefix)) solutions = new Set([...solutions, ...findWords(prefix, solutions)]); if (!solutions.has(suffix)) solutions = new Set([...solutions, ...findWords(suffix, solutions)]); return solutions; };¿Me pregunto si alguien puede ayudarme a optimizar el código?
Editar:
Hice una solución diferente, funciona mucho mejor.
const getAllSubstrings = (str) => { let result = []; for (let i = 0; i < str.length; i++) { for (let j = i + 1; j < str.length + 1; j++) { result.push(str.slice(i, j)); } } return result; } const findWords = (instring) => { const solutions = [] let subs = getAllSubstrings(instring) for (let sub of subs) { if (words[sub]) solutions.push(sub) } return solutions }Todavía abierto a posibles mejoras, pero esto funciona lo suficientemente bien para mi caso de uso
Tal como está, su lógica asume que su entrada comienza o termina con la frase, pero no considera las palabras en el medio; deberá generar permutaciones
Convierta su diccionario en un hash donde las palabras son claves - O(n) => O(1) - puede comprobar si hay palabras posibles en el diccionario comprobando dictionary[possibleWord]
Puede convertir su matriz de palabras del diccionario en un árbol de búsqueda binaria o un trie: puede haber un beneficio de rendimiento al convertir su texto fuente en una colección de BST/Tries, donde cada uno representa una posible palabra/permutación, y luego comparar BST /Intenta en lugar de cadenas, pero no estoy seguro de cómo eso sería más rápido que la comparación de cadenas en este momento.
Puede limitar la longitud a la longitud máxima de una permutación determinada de las palabras de su diccionario. Terminará con muchas permutaciones, pero posiblemente menos de las que tiene actualmente.
Como indican los comentarios, es posible que desee hacer este lado del servidor para obtener más potencia/en un lenguaje más eficiente que JS, o usar WASM.
Algunas bibliotecas de JavaScript que tienen herramientas de árbol de búsqueda binario: