Estoy buscando una manera de acelerar mi ingenuo proceso de coincidencia de cadenas:
// Treat this as pseudo code function find(input: string, prefixes: string[]) { for (let i = 0; i < prefixes.length; i++) { const prefix = prefixes[i]; if (input.startsWith(prefix)) { return prefix; } } return null; } const prefixes = [ "Hey", "Hi", "Hola", ... ]; const prefix = find("Hey, I'm Michael", prefixes);Investigué algunas estructuras de datos probabilísticos como el filtro de floración, pero no pude encontrar uno que se ajustara a mis necesidades. Dicho esto, en realidad no me importa obtener el prefijo que habría coincidido ni necesito una garantía del 100% de que existe una coincidencia. Solo necesito saber si la entrada definitivamente NO contiene ningún prefijo o si podría contenerlo.
También encontré un artículo sobre un algoritmo Burst Tries que, por lo que pude entender, tendrá un propósito similar. Francamente, aunque no soy lo suficientemente profundo en los algoritmos para comprender los detalles completos de implementación y asegurarme de que esto es lo que estoy buscando.
Nota al margen: supongo que el 99,95% de la entrada que obtendrá esta función no coincidirá con ningún prefijo. Por lo tanto, me gustaría que este sea un paso de optimización para procesar solo cadenas que probablemente tengan un prefijo que estoy buscando.
Cualquier ayuda o sugerencia sería muy apreciada :3
Si los prefijos se conocen de antemano y se pueden preprocesar, puede intentarlo. Especialmente si van a ser tan cortos como 10 caracteres. Eso significaría que cada verificación es del orden de 10 comparaciones. No estoy seguro de cuánto mejor se podría hacer.
function buildTrie(trie, words){ for (let word of words){ let _trie = trie; for (let i=0; i<word.length; i++){ const letter = word[i]; _trie[letter] = _trie[letter] || {}; if (i == word.length - 1) _trie[letter]['leaf'] = true; _trie = _trie[letter]; } } return trie; } function find(trie, str, i=0){ const letter = str[i]; if (!trie[letter]) return false; if (trie[letter]['leaf']) return true; return find(trie[letter], str, i + 1); } const prefixes = [ "Hey", "Heya", "Hi", "Hola"]; const trie = buildTrie({}, prefixes) console.log(trie) console.log(find(trie, "Hey, I'm Michael")); console.log(find(trie, "Heuy, I'm Michael"));Esto no tiene una diferencia lógica con la respuesta de גלעד ברקן, pero muestra trabajar con un trie en un estilo de código bastante diferente. (También usa $ en lugar de leaf como terminador; un símbolo sería una buena alternativa).
const trie = (words) => words .reduce (insertWord, {}) const insertWord = (trie, [c, ...cs]) => c ? {...trie, [c]: insertWord (trie [c] || {}, cs)} : {...trie, $: 1} const hasPrefix = (trie) => ([c, ...cs]) => '$' in trie ? true : c ? c in trie && hasPrefix (trie [c]) (cs) : true const testPrefixes = (prefixes) => hasPrefix (trie (prefixes)) const hasGreeting = testPrefixes (["Hey", "Hi", "Hola", "Howdy"]) console .log (hasGreeting ("Hey, I'm Michael")) console .log (hasGreeting ("Hello, Michael. I'm Michelle")) console .log (trie ((["Hey", "Hi", "Hola", "Howdy"]))) .as-console-wrapper {max-height: 100% !important; top: 0} testPrefixes acepta una lista de prefijos y devuelve una función que informará si una cadena comienza con uno de esos prefijos. Lo hace creando un trie y aplicándolo parcialmente a hasPrefix . Internamente, el trie se construye plegando insertWord sobre un objeto vacío inicial.
Por supuesto, esto solo tiene sentido si su caso de uso tiene prefijos que se reutilizan para varias llamadas. Si no, veo poco mejor que const testPrefixes = (prefixes) => (word) => prefixes .some ((pfx) => word .startsWith (pfx))
Para buscar muchas subcadenas posibles en la cadena, puede usar la idea del algoritmo Rabin-Karp .
En mi programa Banmoron utilicé este algoritmo para seleccionar solicitudes maliciosas por subcadena de búsqueda. Ver fuentes en github .