问题标签 [aho-corasick]

我得到了一个已经填充的Trie T 和一组字符串 S。我要计算 in 的所有元素出现的S总和T。我对如何去做这件事有点困惑。

一个示例 trie 是由 构建的aa，ab并且bbb应该返回9for S={"b","bb","bb","bbb"}，这在查看 trie 时似乎很明显（b出现 4 次、bb两次和bbb一次，所以4+2*2+1 = 9），但我不太确定如何在 a规模更大。非常感谢我必须经历的程序的任何帮助。

想象有一个很大的字符串 S 数组。从该数组中，我只需要获取那些包含特定子字符串的字符串。例如，如果我的数组是 String s [] = {"hello world", "back to hell", "say hello world"}; 并且我的关键字是“hello”，那么它应该返回我的第一个和最后一个元素。我尝试使用 KMP 和 Boyer-Moor 算法检查数组中的每个字符串是否包含子字符串，但这需要太多时间。然后我了解了 Aho-Corasick 算法。我仍在查找它，但似乎它需要一组子字符串和一个大字符串来匹配，而我想要的恰恰相反。因此，我一直在寻找有关如何为我的目的修改 Aho-Corasick 算法的建议，或其他实现这些目的的方法。将不胜感激任何建议。

我想在 Java 中实现基于字典的字符串匹配方法，这应该是高效的。进一步解释实施应基于模糊匹配分数。我已经尝试了几种实现，例如 Aho coresick，但没有得到想要的结果。任何建议都会非常有帮助。

我有一个 Word 文档的文本和一个字符串数组。目标是查找文档文本中这些字符串的所有匹配项。我尝试在 Aho-Corasick 算法的 C# 实现中使用 Aho-Corasick 字符串匹配，但默认实现不适合我。文本的典型部分看起来像

“<strong>启动”是指贷款人以附件 A 的形式向银行发出的书面通知。

“<strong>启动通知”是指贷款人以附件 A 和启动的形式向银行发出的书面通知。

“<strong>工作日”是指银行开放进行一般业务和激活通知的每一天（周六和周日除外）。

关键字的数组看起来像

Aho-Corasick 算法的默认实现返回以下出现次数

激活 - 4

激活通知 - 2

对于“激活说明”，这是正确的结果。但是对于“激活”，正确的计数也应该是 2，因为我不需要考虑相邻关键字“激活通知”中的出现次数。

这种情况有合适的算法吗？

我们的 ruby​​ on rails 应用程序使用 aho corasick gem 来查找任何给定的文本是否包含任何预先列出的坏词（这些是在加载应用程序时从静态配置中挑选出来的）。

但是，使用它会产生一些误报。例如，如果我在配置中的坏词是“abc”，那么包含“habcd”的文本也会被标记，这不是本意。

因此，我尝试将配置词从“abc”更改为“abc”（在单词前后添加空格）。但是，这有另一个缺点，即“abc is xyz”之类的文本将不会被标记，因为它应该是。所以，我还必须在我的配置中添加另外 2 个单词 - “abc”和“abc”，同样我需要在我的配置中添加“-abc”、“abc-”、“:abc”等，使配置相当大，因为除了 abc 之外还有很多这样的词。

因此，我在想是否可以在我的配置中输入某种正则表达式，例如 [",-" "]abc[",-" "] 以便涵盖上述所有情况并且不会出现误报被发现。

我们使用 gem 'aho_corasick', '0.1.0' ， ruby​​ - 1.9.3 和 rails - 3.2.8

任何帮助是极大的赞赏。提前致谢！！:)

我需要扩展 Aho-Corasick 算法以匹配部分字典条目。为此，我在 JS 中修改了一个实现并进行了一些测试，但它还不能很好地工作

这是我的代码：

当我在字典中输入这个条目时：

布朗尼 t 测试关键字 1 你好停止

结果是：

所以很好，但如果我输入这个：

布朗尼测试测试关键字1你好停止

结果是：

当我输入这个时：

布朗尼 tt 测试关键字 1 你好停止

结果是空的...

有人可以帮我找到我的错误吗？

谢谢！

我有一个元组列表，大约有 100k 个条目。每个元组由一个 id 和一个字符串组成，我的目标是列出元组的 id，其字符串包含给定子字符串列表中的子字符串。我目前的解决方案是通过集合理解，ids 可以重复。

有没有一种算法可以更快地做到这一点？我对精确的子字符串匹配感兴趣，也可能对近似匹配感兴趣。我在这里追求的主要是一种算法，它比理解提供速度优势。

我正在尝试解决hackerrank中的一个问题，讨论中的其他人说他们使用AC算法解决了这个问题。我的实现构建 trie 和确定后缀的速度相对较快，但字符串的实际匹配需要很长时间。有什么我想念的吗？插入/搜索的二等分有助于加快速度，但我不确定还有什么需要改进的（可能是不知道我不知道的情况。）我认为这可能与我的方式有关创建了特里，但我不确定。这是我的实现：

还有一个我用来测试的简单输入文件（这个不需要很长时间，需要很长时间的文件就像 2MB：

以及一些分析输出。匹配功能需要很长时间