问题标签 [aho-corasick]

我对 Aho-Corasick 算法的输出函数的实现有疑问。一般来说，我不太了解输出功能是如何工作的。根据这篇论文，在 goto 函数中，我将适当的模式索引放在输出中，就像output[currentState] = patternIndex; 在失败函数中一样，我将状态 S 的现有输出与失败状态 S 的输出合并，就像output[s] += output[fail[s]];在搜索函数中我使用这样的条件：if (output[state]) != 0) then we find our pattern. 但是这种方法不起作用并且我有胡说八道的结果。也许，输出函数的伪代码在那篇论文中还有其他含义，我不知道。

我在这里得到的具有按位映射的输出函数在大多数情况下也不能正常工作。错误的模式与此条件匹配if ((output[currentState] & (1 << j)) != 0) 此外，我不太明白为什么按位运算用于输出计算。

对于澄清输出功能的实现，我将不胜感激。

EDIT1：看来，这个问题是在移位操作后溢出： 到目前为止，尝试使用 BigInteger，但似乎它会导致性能问题output[currentState] |= (1 << i);。out[currentState] & (1 << j)

EDIT2：尝试了 BitSet，但性能仍然很差。也许，算法的实现有问题，我不知道。

现在我知道以前有关于这个算法的问题，但是老实说我还没有遇到过简单的 java 实现。许多人在他们的 GitHub 个人资料中复制并粘贴了相同的代码，这让我很恼火。

因此，出于面试练习的目的，我计划使用不同的方法来设置和实施算法。

该算法往往非常非常具有挑战性。老实说，我不知道该怎么做。只是逻辑没有意义。我几乎花了 4 天的时间直接绘制该方法，但无济于事。

因此，请用您的智慧启发我们。

我主要是根据这些信息做算法Intuition behind the Aho-Corasick string matching algorithm

如果可以在这里实现自己的解决方案，那将是一个很大的好处。

但这是我真正陷入困境的以下不完整且不起作用的解决方案：

如果您对代码感到不知所措，那么主要问题在于 Aho-Corasick 的主要算法。我们已经很好地创建了字典树。

但问题是，既然我们有了 trie 结构，我们如何真正开始实施。

这些资源都没有帮助。

我已经设置了一个工作正常的 trie 数据结构。所以这里没问题

特里.java

节点也是一样的。

节点.java

我正在编写一个程序，它读取文本文件目录并找到重叠的字符串的特定组合（即在所有文件之间共享）。我目前的方法是从这个目录中获取一个文件，解析它，构建每个字符串组合的列表，然后在其他文件中搜索这个字符串组合。例如，如果我有十个文件，我会读取一个文件，解析它，存储我需要的关键字，然后在其他九个文件中搜索这个组合。我会为每个文件重复此操作（确保单个文件不会自行搜索）。为此，我正在尝试使用 python 的acora模块。

我到目前为止的代码是：

正如您可能知道的那样，我使用match_lines了 acora 网页“常见问题解答和食谱”#3 中的功能。我还在模式下使用它来解析文件（使用ac.filefind()），也位于网页中。

该代码似乎有效，但它只为我提供了具有匹配字符串组合的文件名。我想要的输出是从包含我匹配的字符串组合（元组）的其他文件中写出整行。

我正在尝试解决 HackerRank 上的问题；“确定 DNA 健康状况。” 在查看了一些讨论后，我决定 Aho-Corasick 算法将是最佳选择。该问题涉及在字符串中搜索具有关联值的各种序列。任务是从给定列表中获取这些序列值对的一个子部分，并找到与输入字符串关联的值。这意味着使用 100000 个序列值对的列表完成 44850 次。我已经实现了这个算法，虽然它比我的第一次尝试快了很多，但它仍然不够快，无法通过这个测试用例。这是我的实现：

构建特里：

通过特里搜索：

Trie 节点类：

我知道对于失败案例可以在这里进行更多的边缘构建，但是讨论中的几个人说它会更慢，因为需要为每个查询重建 trie。对于这样的问题，我应该使用一些更有效的集合吗？如何在保持纯粹功能风格的同时加快速度？

我有一个 C++ 库来运行字符串匹配（PFAC 库）PFAC-lib。如何从 WinForm C# 运行这个库？

我还使用managedCuda从我的 C# 运行 cuda 代码。任何想法？

我已经看到了类似问题的答案： https ://stackoverflow.com/a/44311921/5881884

ahocorasick 算法用于显示列表中的每个单词是否存在于字符串中，时间为 O(n)。但我想获取字符串列表中每个单词的频率。

例如，如果

我想要结果：

我在文档中没有找到一个确切的例子，知道如何做到这一点吗？

除了使用 ahocorasick 之外的其他 O(n) 解决方案也将不胜感激。

我有一个大文本（5MB-500MB）文件和一组几千个模式。对于每个模式，我想获取文件中模式的出现次数。该文本不包含空格，是一个基本的长字母数字字符串。

为此，我尝试使用 Aho-Corasick 算法，特别是 Robert-Bor 的 Java 实现，它确实运行得足够快，但是有一个问题：使用模式计算发射的结果，因为它们的字符串不相等使用notepad++等文本编辑器打开文本文件并计算模式的结果。对我来说重要的是，计数的出现次数将恰好是在文件中找到的模式的次数。因此，我需要找到解决这个问题的方法。

为了实现我的目标，我可以在算法的实现中做出改变吗？也许某种 EmitHandler 可以解决我的问题？我也愿意接受其他建议，例如替换算法/解决方案方法。但是，如果可能的话，我想继续使用 java，并尽可能快地获得结果（例如，发出索引对我来说并不重要）。

编辑：例如，即使是安装文件的以下小文本： File Link和模式：

5b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff

根据发出计数在文件中出现 150 次，但根据 Notepad++/Ctrl-f 在浏览器中的计数功能仅出现 10 次。

以及同一文本的另一个示例：

f34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0

根据发射计数出现 99 次，但根据文本编辑器的计数仅出现 10 次。

链接到算法的实现，在这里。我目前基于实现运行的内容：

谢谢！

我还尝试了实现中可用的非重叠选项，但它不符合要求，而且对于我的使用来说也太慢了。

All the literature and implementations I've found of Aho-Corasick are about building the entire trie beforehand from a set of phrases. However, I'm interested in ways to work with it as a mutable data structure, where it can handle occasional adds and removes without needing to rebuild the whole trie (imagine there are 1 million entries in it). It's OK if the worst case is awful, as long as the average case is close to logarithmic.

From how I figure it, the fail state for each node is another node that uses the same symbol. So if we have a hash multimap from each symbol to the list of nodes which use that symbol, we have our candidates whose fail states need updating.

Remove is straightforward. You find all other nodes which use the deleted node as a fail state and recompute their fail state. Go from the end of the string backwards, and the tree should still be in good shape.

Add is a bit trickier. Any node that failed to that symbol could have the new node as a better candidate. However, again it seems to be enough to traverse every other node with that symbol and fully recompute its fail state.

In other words, if we're adding or removing a node with symbol "A", we need to visit every other "A" node anywhere in the trie, and recompute the fail state (look for its closest ancestor with "A" as a child, or the root). This would require visiting every node for symbol "A", but in my case, that would be several orders of magnitude less than visiting every node in the trie.

Would that algorithm work, or am I missing something obvious?

I'm just copying the example from this github project page without any change and it's giving me a compile error

To reproduce, add this dependency to your pom

Then try to run this:

The compile error is

Please let me know if you need anything to clarify. You should be able to reproduce this with what I have provided here though.

Also, it's been suggested this may be a duplicate question when I posted this previously, but I do not think that's the case as that question is not related to lambda functions. If I'm wrong, please help me understand how that question's answer can resolve what I'm experiencing

首先，我是使用二进制文件的新手，希望这不是一个愚蠢的问题。

我已经从二进制文件的 .text 部分生成了带有指令序列的表。具有 2 个指令序列的表如下所示：

使用 IDAPython 提取序列，生成的文本文件如下所示：

更新

现在，我使用 Aho-Corasick 算法将这些序列匹配到我从中提取它们的同一个二进制文件中。我只是将表中的所有序列添加到 Aho 自动机：

然后我得到以下输出：

我的问题是 Aho-Corasick 返回 0x38b7 并且我在 Ubuntu 中使用 ghex 再次查看二进制文件，并在预期的偏移量处找到了两条指令：

这意味着我应该在 0x1c54 - 0x1c5c 的范围内找到它们，这是原始偏移量 (0x9c54 - 0x8000)

我还没有真正理解如何获得相同的偏移量，但我想使用 Aho-Corasick 获得原始偏移量。我知道 Aho-Corasick 返回关键字结尾的偏移量。