python - 特里？在python中匹配带有尾随字符的单词

Question

这与 stackoverflow 上的大多数 trie 问题有点不同(是的，我花时间搜索和阅读)，所以请耐心等待。

我有 FILE A，其中包含以下词:allow*、apolog* 等。总共有数万个这样的条目。我有包含文本正文的 FILE B，最多有数千个单词。我希望能够将文件 B 中的文本中的单词与文件 A 中的单词进行匹配。

例子:

文件 B 的“道歉”将匹配文件 A 的“道歉*”

文件 B 的“a”既不匹配“allow*”也不匹配“apolog*”

文件 B 的“apologizetomenoworelseiwillkillyou”也会匹配文件 A 的“apolog*”

谁能建议一个算法/数据结构(最好在 python 中可行)来帮助我实现这个目标？我研究过的尝试似乎更多的是将前缀与整个单词匹配，但在这里，我将整个单词与前缀匹配。词干算法是不可能的，因为它们有固定的规则，而在这种情况下，我的后缀可以是任何东西。我不想遍历文件 A 中的整个列表，因为那样会花费太多时间。

如果这令人困惑，我很乐意澄清。谢谢。

Answer 1

将所有前缀放入哈希表中。然后取出 B 中的每个单词并在哈希表中查找它的所有前缀。您得到的任何命中都表示匹配。

因此哈希表将包含“allow”和“apolog”。对于“apologize”，您会先查找“a”，然后查找“ap”，依此类推，直到您查找“apolog”并找到匹配项。