给定一个“大”模式列表和一个“短”文本，在文本中搜索/标记这些模式的最佳/最快方法是什么，我们试图在其中找到模式作为文本的子字符串？如果文本中有多个模式匹配，我们希望理想地找到所有匹配。
更具体地说，文本实际上是流式查询，要查找的模式是命名实体。我们需要一个完整的模式来完全匹配。训练 NER 模型来标记实体不是一种选择。“大”列表是指要查找的几十万个实体。“短”文本是指平均 10 个单词。
例如：
文字：复仇者联盟中饰演黑寡妇的演员。
我正在考虑尝试和 FST。试图了解在这种特定情况下两者的优缺点。任何指针将不胜感激。
你可以看看 Aho-Corasick 算法。该算法从所有搜索模式构造一个有限状态机，基本上是一个 trie，但有一些额外的边缘。然后它使用这个 trie 同时搜索所有搜索模式的输入字符串。时间复杂度为 O(n + m + z)；n = 输入文本的长度，m = 所有搜索模式中的总字符，z 是输入文本中搜索模式的出现次数。
但是，这种时间复杂度假设您为每个搜索构建了 trie，因此，如果您预先构建 trie（假设您的搜索模式似乎没有改变），并将其保存到内存中，我认为您可以根据 pre 搜索字符串在 O(n) 中计算 trie（有限状态机）。