提高字符串前缀匹配性能
我正在寻找一种方法来加快我天真的字符串匹配过程：
// 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);我研究了一些概率数据结构，比如布卢姆过滤器，但我找不到适合我需要的结构。尽管如此，我并不想得到匹配的前缀，我也不需要100%的保证匹配。我只需要知道输入是否肯定不包含任何前缀，或者它是否包含前缀。
我还遇到了一篇关于突发尝试算法的文章，据我所知，该算法将起到类似的作用。坦率地说，尽管我对算法的研究还不够深入，无法掌握完整的实现细节并确保这正是我所要寻找的。
附带注意:我假设这个函数得到的99.95%的输入将与任何前缀不匹配。因此，我希望这是一个优化步骤，只处理可能有前缀的字符串。
如有任何帮助或建议，我们将不胜感激：
回答 4
Stack Overflow用户
发布于 2021-08-23 23:59:21
如果预先知道前缀并可以进行预处理，则可以尝试trie。特别是如果他们要短到10个字符。这意味着每一次检查都要进行10次比较。不知道一个人能做什么更好。
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"));
Stack Overflow用户
发布于 2021-08-24 15:50:49
这与答案的גלעדברקן没有逻辑上的区别，但它显示的是以完全不同的代码样式使用trie。(它还使用$而不是leaf作为终止符；符号是一个很好的选择。)
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接受前缀列表，并返回一个函数，该函数将报告字符串是否以其中一个前缀开头。它通过创建一个trie并将其部分应用于hasPrefix来做到这一点。在内部，trie是通过在初始空对象上折叠insertWord构建的。
当然，只有当您的用例有用于多个调用的前缀时，这才有意义。如果不是，我看不出比const testPrefixes = (prefixes) => (word) => prefixes .some ((pfx) => word .startsWith (pfx))更好
https://stackoverflow.com/questions/68896660
复制相似问题
腾讯云开发者
