2

要求

  1. 目前我们有一个包含上万个关键词或句子的列表（数量为N）
  2. 输入一个长字符串，长度为L

问题：检查字符串是否包含给定列表中的关键字或句子

该问题可以描述为wikipedia上的单词过滤器，但我在该页面上没有找到任何算法。解决此问题的最简单方法是迭代所有关键字或句子，并且每次检查长文本是否包含此类子字符串。由于我们有多个关键字，同时考虑到长文本，性能很差。它使用 O(NL) 时间

似乎更好的解决方案应该在 O(L) 中完成。有人可以对此提出一些建议吗？

4

1 回答 1

4

有几种方法可以解决这个问题，时间复杂度为 O(M + L)，其中 L 是字符串的长度，M 是所有模式的组合长度：

  1. Aho–Corasick 字符串匹配算法。
  2. 使用Ukkonen 算法为字符串构造一个后缀树，然后找到每个模式与该后缀树的匹配项。
  3. 为一组模式构造一个通用的后缀树，然后找到输入字符串和这个后缀树之间的匹配。
  4. 为字符串构造一个Suffix 数组，并使用它来搜索每个模式。这种方法的时间复杂度为 O(M + L + N log L)，其中 N 是模式的数量。
  5. Commentz-Walter 算法。

您可以在这本书中找到所有这些算法（除了 Commentz-Walter 算法）的详细信息：Dan Gusfield 的字符串、树和序列算法。

如果您可以明确地从输入字符串中提取单独的单词/句子，则可以使用几种不同（更简单）的方法。

  1. 准备一个大小足够大的布隆过滤器，以保证 N 个模式的误报概率低。添加到布隆过滤器位，由关键字/句子的哈希函数确定。然后扫描字符串，提取连续的单词/句子，并检查这些单词/句子是否可以在布隆过滤器中找到。仅当 Bloom 过滤器中存在单词/句子时，才在模式列表中搜索它。该算法具有预期的时间复杂度 O(M + L) 并且是节省空间的。
  2. 将所有模式插入哈希集中。然后扫描字符串，提取连续的单词/句子，并检查它们是否在哈希集中。这具有相同的预期时间复杂度 O(M + L)，比布隆过滤器方法更简单，但不节省空间。
  3. 将所有模式插入基数树（trie）。然后用它从字符串中搜索单词/句子。这与广义后缀树方法没有太大区别，但更简单，性能更好。它具有最坏情况下的时间复杂度 O(M + L)，可能比 Bloom 过滤器或哈希集方法要慢一些，并且在必要时可以非常节省空间。
于 2012-11-22T16:37:51.027 回答