传递相似词的Levenshtein距离

Question

代码的目的是:两个单词是朋友，如果它们的Levenshtein距离为1。也就是说，您可以添加、删除或替换单词X中的一个字母来创建单词Y。一个单词的社交网络由它的所有朋友、他们所有的朋友以及他们所有的朋友的朋友等等组成。数一下社交网络中某个单词的朋友。

我的代码是使用Steve编写的Trie实现的。他的代码在这里：http://stevehanov.ca/blog/index.php?id=114。

我所做的是：

social_links = set_up_dictionary_from_text('dictionary.txt')
tree = Trie()
for i in social_links:
    tree.insert(i)
def find(keyword):
    neighbors = [keyword]
    already_in_set = set()
    while len(neighbors) > 0:
        if neighbors[-1] not in already_in_set:
            temp = neighbors[-1]
            already_in_set.add(neighbors.pop())
            current_neighbors = search(tree, temp)
            neighbors.extend(current_neighbors)
        else:
            already_in_set.add(neighbors.pop())
    return(len(already_in_set))

此代码可以工作，但对于超过10万字的文件，运行时间超过8分钟。我做错什么了吗？或者我不应该用Python来完成这个任务？

Answer 1

首先，这不是Python问题。相反，这是一个实现本身的问题。

我同意“Gareth Rees”您应该始终提供代码的最低工作示例。对于StackOverflow，尤其是对于CodeReview，这是正确的。在这方面，我们能看到的只是你提供的小片段，假设你没有提供的函数做某些事情。

首先可以切割的是else:块。它进入当且仅当neighbors的最后一个元素在already_in_set中，它所做的就是将neighbors的最后一个元素添加到already_in_set中；换句话说: nothing。作为一个副作用，您确实弹出了最后一个元素，因为在这两种情况下都是这样做的，所以最好将其分配到if之上。

看起来，search(tree, temp)将返回一个可迭代的东西，其中包含temp的所有1级邻居。如果您不进行任何缓存，search是非常慢的！松散地说，这是用于简单实现的O(len(dictionary.txt) * max([len(word) for word in dictionary.txt])^2)，对于您提到的博客文章中给出的实现是O(max([len(word) for word in dictionary.txt]) * depth(tree))。

更糟糕的是，你只为一个单词中的每一个朋友做这件事(因为你修剪过一次)。因此，您运行的是O(len(dictionary.txt)*max([friends(word) for word in dictionary.txt])*O(search))，在最糟糕的情况下，它可以是O(len(dictionary.txt)^4) (!)；尽管这种情况只与理论上的考虑有关。

下面是你可以做的事情清单：

• 缓存两个单词的Levenshtein距离；也不需要实际值，而是表达式distance <= 1的结果，因此有更多优化的空间。这也是对称的：distance(a,b) = distance(b,a)，因此您可以为每次计算缓存两个值。
• 缓存search(tree, temp)的结果。同样，这是对称的：if b in search(tree,a) then a in search(tree,b)，因此您可以为search(tree,a)的每个元素缓存这个结果，而无需计算它们( 请注意，这也是反射性的：a in search(tree,a) )。
• 缓存find(keyword)的结果。find在dictionary.txt上定义了一个组关系；因此，如果b in find(a)和c in find(a)也是：a in find(b)、a in find(c)、c in find(b)、b in find(c)。对象的网络中的每个元素都可以缓存这个数字。

所有这些都会降低O(O(find)+O(search)+O(distance)) = O(len(dictionary.txt)^2)最坏的性能，并且会大大加快速度。您可以想出减少search和distance所需的计算数量的方法，这可能会降低总体复杂性，但我没有进一步考虑这一点。