我有一本字典，它将单词映射到 id，例如:
at: 0
hello: 1
school: 2
fortune:3
high:4
we: 5
eat: 6
....
high_school: 17
fortune_cookie: 18
....
然后，我有一个文档。将文档内容传输到 id 的最快、最有效的方法是什么？ 例如:
"At high school, we eat fortune cookie."
=> "0 17, 5 6 18"
希望看到您的建议。 感谢阅读。
最佳答案
这实际上取决于您的文档有多大，您的关键字列表是否是静态的，以及您是否需要查找多词短语。最简单的方法是在字典中查找文档中的每个单词。因为字典查找的时间复杂度为 O(1)，查找每个单词将花费 O(n) 时间，其中 n 是文档中的单词数。如果您需要查找多词短语，您可以对输出进行后处理以找到它们。
这不是最有效的做事方式，但它确实很容易实现，速度相当快，而且如果您的文档很大，它也能很好地工作。
如果您有非常大的文档，那么您可能需要像 Aho-Corasick string matching algorithm 这样的东西.该算法分两个阶段进行。首先，它根据字典中的单词构建一个 trie，然后单次遍历文档并输出所有匹配项。它比朴素的方法更复杂，但一旦构建了 trie，它就可以很好地工作。而且，说实话，实现起来并不难。链接自维基百科文章的原始论文很好地解释了该算法，并且不难将其伪代码转换为工作程序。
但是请注意，您可能会得到一些意想不到的结果。例如，如果您的字典包含单词“high”和“school”以及两个单词的短语“high school”，Aho-Corasick 会在看到短语“high school”时为您提供这三个单词的匹配项。
关于algorithm - 高效查字典的方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27688502/