寻找类似的单词

Question

我正在尝试编写一个拼写检查模块.

它加载一个文本,从16 mb文件创建一个字典,然后检查遇到的单词是否与字典中的单词相似(类似=最多两个字符),如果是,则将其从字典更改为表单.

现在我正在使用Levenshtein距离算法,处理50个字的设置需要3分钟......

我很确定必须有更快的解决方案.Profiler告诉我,我的应用程序花费了超过80%的时间在Levenshtein Distance功能.

有没有更好的解决方案/算法？

这是我使用的算法版本的实现:

def levenshteinDistance(s1, s2):
    l_s1 = len(s1)
    l_s2 = len(s2)
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)]
    for i in xrange(1, l_s1 + 1):
        for j in xrange(1, l_s2 + 1):
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1]))
    return d[l_s1][l_s2]

Answer 1

我已经使用了 Norvig 的拼写纠正器，在评论中提到过，它非常棒。

然而，对于您的问题，您已经编写了动态规划编辑距离算法。您的算法有资格成为数据并行算法。在共享内存上，即在单台机器上，如果您有多核，则可以利用它们。你知道map-reduce吗？现在请不要考虑分布式，只考虑一台四核机器和共享内存。作为步骤 1，您可以对字典进行分区，并将一部分分配给每个线程，该线程将在字典的一部分上运行编辑距离（类似于映射步骤）。稍后，您的所有线程将以编辑距离 2 返回所有单词（类似于减少步骤）。这样您的程序将受益于多核架构。

我能想到的另一件事是在你的Python代码中用C编写CPU密集型编辑距离算法，即通过编写Python扩展。