python - 尽可能快的类字典匹配

Question

我将不得不在 Python 中执行类似拼写检查的操作，如下所示:

我有一个巨大的单词列表(我们称之为词典)。现在我得到了一些文本(我们称之为示例)。我必须在词典中搜索每个样本词。如果我找不到它，则该示例词是错误的。

简而言之 - 一个强力拼写检查器。然而，线性搜索词典中的每个样本词肯定会很慢。执行此操作的更好方法是什么？

复杂的因素是样本和词典都不是英文的。它是一种语言，而不是 26 个字符，可以有 300 多个 - 存储在 Unicode 中。

任何算法/数据结构/并行化方法的建议都会有所帮助。以低于 100% 的准确度为代价的高速算法将是完美的，因为我不需要 100% 的准确度。我知道 Norvig 的算法，但它似乎是特定于英语的。

Answer 1

您可以使用一组 Unicode 字符串:

s = set(u"rabbit", u"lamb", u"calf")

并使用 in 操作符来检查一个单词是否出现:

>>> u"rabbit" in s
True
>>> u"wolf" in s
False

这个查找本质上是 O(1)，所以字典的大小无关紧要。

编辑:这是(区分大小写的)拼写检查器(2.6 或更高版本)的完整代码:

from io import open
import re
with open("dictionary", encoding="utf-8") as f:
    words = set(line.strip() for line in f)
with open("document", encoding="utf-8") as f:
    for w in re.findall(r"\w+", f.read()):
        if w not in words:
            print "Misspelled:", w.encode("utf-8")

(print 假定您的终端使用 UTF-8。)