问题标签 [aho-corasick]

我正在尝试创建一个脚本，该脚本将允许用户输入许多正则表达式，这些正则表达式将通过输入文件并检索匹配项。我目前正在使用 ahocorasick，但是当我尝试输入正则表达式模式时遇到问题。

我在第二个 raw_input (colour_regex) 中输入了一个正则表达式，但在下面收到此错误：

任何对正确方向的帮助/指导都会很棒。

谢谢

我想在大量文档中搜索字符串。我有一个预定义的可用字符串列表，我想在每个文档中找到它们。每个文档的开头都包含一个标题，后跟文本，标题中是我想在标题下方的文本中搜索的附加字符串。

在文档的每次迭代中，是否可以在创建由主列表创建的初始树后添加标题字符串？或者修改原始数据结构以包含新字符串？

如果这不切实际，是否有更合适的替代搜索方法？

构建树时，如何处理关键字列表中的重复项？您是否应该在构建树之前确保列表没有重复项？

此代码适用于我从此处引用的 Aho-Corasick 算法

我理解这段代码直到 push_links 方法的 if 块，但我没有得到相同方法的 else 部分的用途或要求。更具体地说，第一种方法用于构建 trie。剩下的工作是通过第二种方法完成的，即将节点链接到它们最长的正确后缀，这些后缀也是某种模式的前缀。这是由 If 块执行的，那么 else 部分需要什么。

请帮助我。

假设我们有一个关键字字典

假设我们有第二个关键字词典（与第一个不同）

我想从输入文本中的两个字典中查找序列中无序关键字对的所有可能匹配项（即，仅由空格分隔）。例如，将以下内容视为输入文本

Aho-Corasick 算法是一种传统的解决方案，它通过构造一个类似 trie 的自动机并逐个字符地扫描文本，从而有效地从输入文本中的单个关键字词典中找到所有匹配项。

对于多个字典的情况，是否有一种有效的方法来扩展 Aho-Corasick ？

TL，博士

NSData请参阅（此处为 Swift）的此成员函数：

我想用Set（或其他集合）替换第一个参数NSData并返回第一个匹配项。一个数据模式可以是另一个数据模式的子集，因此返回最长的匹配。有任何想法吗？

我听说这种方法在其实现中使用了类似 Boyer–Moore 的方法。所以我的扩展可能会使用像 Aho-Corasick 这样的东西。

太长...

我想阅读电子邮件文件。

我打算一次读取一行文件，所以我需要一个换行检测算法。标准是 CRLF，但我应该扫描 just-CR、just-LF 和（用于完成）LFCR。请注意，我正在阅读二进制文件，其中二进制到文本是在稍后阶段完成的，所以所有这些NSString和NSRegularExpression东西都对我没有帮助。

我打算编写一个自定义例程，然后我意识到我可以概括它。我做了一个解析树节点类，一个线生成器的骨架类，和一堆测试。我已经拖延了代码的实质：输入字节扫描、创建解析树和遍历解析树。再次环顾四周，我仍然在拖延，因为这似乎是我们的程序员祖先必须解决的问题类型，并且已经有了代码。

这一次，我发现了字符串匹配算法，所以希望我更近一步（除了将它们翻译成 Swift）。

或者也许我应该放弃概括并rangeOfData: options: range:在每个循环中调用两次，一次用于 CR，一次用于 LF，然后协调它们。不过，这效率低下。或者保留自定义列表的想法；为每个模式制作一个带有分支的树，统一前缀与具有多个节点的分支重叠。（如果向后搜索，请创建面向后缀的分支！）这里的多次遍历会更加低效。

请注意，它NSData具有将其数据作为一系列块进行遍历的功能。我打算使用那个函数，但我必须小心，一个模式可能会被分成两个（或更多！）块。

如果是这样，有人可以解释后缀树中后缀链接的目的以进行精确的字符串匹配吗？

我有一个数百万名人的名字列表（来自 Wikidata），我需要创建一个系统来有效地找到在相当短的文本中提到的所有人：它可以只是一个词（例如“爱因斯坦”）到几页文本（例如维基百科页面）。

我需要系统对拼写错误（例如 Mikael Jackson 而不是 Michael Jackson）和短格式（例如 M. Jackson）具有相当的容忍度。如果有歧义，它应该返回所有可能的人（例如，“George Bush”应该返回父亲和儿子，可能还有其他同音词）。

这个相关问题有一些有趣的答案，包括使用Aho-Corasick 算法。有许多语言的库，包括Python。但是，它似乎不支持模糊搜索（即容忍拼写错误）。

我想我可以扩展词汇表以包含每个名字的所有可能拼写，但这会使词汇表太大，所以我宁愿尽可能避免这种情况（此外，我可能希望将此解决方案扩展到更多人一点）。

我快速浏览了一下Lucene /ElasticSearch，但它似乎不支持这个用例（除非我错过了它）。

有任何想法吗？

我想知道如何在线性时间内计算大海捞针中每根针的出现次数。我以为我会使用 Aho-Corasick 算法，但我不希望时间复杂度取决于针的出现次数。

我有一个 Aho Corasick trie，我通过它来解析一段文本。现在这个 trie 作为我的烧瓶应用程序的一部分存在。它部署在 Heroku 上，目前我天真地存储了自动机的腌制形式，在需要时将其取消腌制并使用它。有什么更好的方法可以有效地为这样的网络应用程序存储 Aho Corasick 自动机？