最快速的字典匹配

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.)