提高字符串前缀匹配性能

Question

我正在寻找一种方法来加快我天真的字符串匹配过程：

// 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% 保证匹配存在。我只需要知道输入是否绝对不包含任何前缀或可能包含。

我还看到一篇关于 Burst Tries 算法的文章，据我所知，它也有类似的用途。坦率地说，尽管我对算法的了解还不够深入，无法掌握完整的实现细节并确保这就是我要找的东西。

旁注：我假设此函数将获得的 99.95% 的输入不会匹配任何前缀。因此，我希望这是一个优化步骤，只处理可能具有我正在寻找的前缀的字符串。

非常感谢任何帮助或建议:3

Answer 1

如果预先知道前缀并且可以对其进行预处理，您可以试试 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"));

Answer 2

要在字符串中搜索很多可能的子串，可以使用Rabin-Karp算法的思路。

在我的程序中Banmoron I used this algorithm for select malicious requests by search substring. See sources on github.

Answer 3

编辑：startsWith 比 indexOf 快是有道理的，我很难找到比较两者的基准，我找到的基准取决于浏览器速度，chrome 运行 indexOf 比 startsWith 快，我很乐意了解更多信息。以下为原答案：

我最近对 .indexOf 进行了很多处理，以应对其中的大多数情况。根据我的阅读，性能优于大多数循环情况并且易于使用，这是两个函数的示例：

findOne：Returns 找到的第一个条目（打破可以提高性能的循环）。
findAll：遍历所有前缀和returns一个数组找到前缀

如果你是专门找前缀的（因此索引值等于0，只需要改变函数来表示它

input.indexOf(prefixes[i]) === 0

而不是

input.indexOf(prefixes[i]) >= 0

这是代码片段：

const exampleString = "Hello, I am Michael, bey";
const examplePrefixes = ["Hello", "Holla", "bey"];

function findOne(input, prefixes) {
  // Loop through prefixes to test if is in the string
  for (let i = 0; i < prefixes.length; i++) {
    // If the prefix does not exist in the string it returns a value of -1
    if (input.indexOf(prefixes[i]) >= 0) {
      // Retrun the prefix value if it is found
      return prefixes[i];
    }
  }
  // Return null if nothing is found
  return null
}

function findAll(input, prefixes) {
  // Initialize return array
  let retArr = [];
  // Loop through prefixes to test if is in the string
  for (let i = 0; i < prefixes.length; i++) {
    // If the prefix does not exist in the string it returns a value of -1
    if (input.indexOf(prefixes[i]) >= 0) {
      // If the prefix exists, push it onto the return array
      retArr.push(prefixes[i]);
    }
  }
  // return the array after looping through each prefix
  return retArr.length !==0 ?  retArr :  null
}

let value1 = findOne(exampleString, examplePrefixes);
let value2 = findAll(exampleString, examplePrefixes);

console.log(value1); // Hello
console.log(value2); // [ 'Hello', 'bey' ]

Answer 4

这与 גלעד ברקן 的在逻辑上没有区别，但它显示了以完全不同的代码风格使用 trie。（它还使用 $ 而不是 leaf 作为终止符；Symbol 将是一个很好的选择。）

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 接受一个前缀列表和 returns 一个函数，该函数将报告字符串是否以这些前缀之一开头。它通过创建一个 trie 并将其部分应用于 hasPrefix 来实现。在内部，trie 是通过在初始空对象上折叠 insertWord 构建的。

当然，这只有在您的用例具有可重复用于多个调用的前缀时才有意义。如果不是，我觉得比 const testPrefixes = (prefixes) => (word) => prefixes .some ((pfx) => word .startsWith (pfx))

好不了多少

提高字符串前缀匹配性能

Improve string - prefix matching performance

javascript

string

algorithm

string-comparison