搜索文本中模式的长列表的最快方法
搜索文本中模式的长列表的最快方法
提问于 2021-12-08 04:51:28
给定一个“大”模式列表和一个“简短”文本，在文本中搜索/标记这些模式的最佳/最快方法是什么?在文本中，我们试图将模式作为文本的子字符串查找？如果一个文本中有多个模式匹配，我们希望理想地找到所有匹配的模式。
具体来说，文本实际上是流查询，要查找的模式是命名实体。我们需要一个完整的模式来完全匹配。培训NER模型以标记实体不是一种选择。所谓“大”列表，我指的是几十万个要查找的实体。所谓“短文”，我指的是平均10个字。
例如：
文本:在复仇者联盟中扮演黑寡妇的演员。
我在考虑尝试和FSTs。试图了解两者在这个特殊情况下的利弊。如有任何指示，将不胜感激。
回答 1
Stack Overflow用户
发布于 2021-12-08 05:32:05
你可以看看Aho-Corasick算法。该算法从所有的搜索模式中构造一个有限状态机，基本上是一个trie，但有一些额外的边。然后使用这个trie同时搜索所有搜索模式的输入字符串。时间复杂度为O(n +m+ z)；n=输入文本的长度，m=所有搜索模式中的总字符，z是输入文本中搜索模式出现的次数。
然而，这一次的复杂性假设您为每个搜索构建trie，所以如果您预先构建trie (考虑到您的搜索模式似乎没有改变)，并将其保存到内存中，我认为您可以根据O(n)中的预先计算的trie (有限状态机)搜索字符串。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70270111
复制相关文章
相似问题
腾讯云开发者
