5

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

它加载文本，从 16 mb 文件创建字典，然后检查遇到的单词是否与字典中的单词相似（相似 = 最多变化两个字符），如果是，则将其更改为字典中的形式。

现在我正在使用 Levenshtein 距离算法，处理 50 个单词集需要 3 分钟......

我很确定必须有一个更快的解决方案。Profiler 告诉我，我的应用程序在 Levenshtein Distance 函数中花费了超过 80% 的时间。

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

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

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]
4

2 回答 2

2

我使用了评论中提到的 Norvig 的拼写校正器，非常棒。

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

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

于 2012-04-08T20:15:40.963 回答
0

也许问题在更高的层次上。当分析器告诉您在一个函数中花费了很多时间时，可能是您调用它的频率太高了。您是否可能将文本中的每个单词与字典中的每个单词进行比较？换一种方式试试：对于文本中的单词，直接生成距离 <= 2 的单词并检查它们是否在字典中。

于 2012-04-08T21:06:40.953 回答