python - 两个单词向量之间的字符串相似度

Question

我有两个非常长的 O(100k) 单词列表，我需要找到所有相似的词对。我的解决方案的时间复杂度为 O(n*m)。这是优化该算法的一种方法 - 降低其复杂性吗？

def are_similar(first, second):
    threshold = 0.88
    return difflib.SequenceMatcher(a=first.lower(), b=second.lower()).ratio() > threshold


list_1 = ["123456","23456",  ...] # len(list_1) ~ 100k
list_2 =["123123","asda2131", ...] # len(list_2)~ 500k

similar = []
for element_list1 in list_1:
    for element_list2 in list_2:
        if are_similar(element_list1,element_list2 ):
            similar.append((element_list1,element_list2 ))

print (similar)

并行化上述代码的最佳方式是什么？我当前的实现(不包括在内)在第一个循环中使用 multiprocessing.Pool。

Answer 1

我可以建议另一种解决方案，但我不确定您是否想要我建议的完全相同的东西。首先，有两个列表，如果我们将列表中的一个元素与其自身进行匹配，则相似度为1，即完全匹配。所以，我们可以从下一个词开始比较。现在，让我们通过获取列表集来获取单个列表中的所有单词。

list_1 = ["123456","23456",  ...] # len(list_1) ~ 100k
list_2 =["123123","asda2131", ...] # len(list_2)~ 500k


list_3 = list_1 + list_2
list_3 = list(set(list_3)) # this will merge all same words to a list of unique words.
similar = []
for i in range(0, len(list_3)):
    if are_similar(list_3[i], list_3[i+1]):
        similar.append((list_3[i],list_3[i+1]))

print (similar)

我将这里的 list of words 集合列表进行比较，因为如果我们可以一次又一次地比较完全相同的单词，那么我们会显着减少重复单词的比较次数。此方法的复杂度为 O(n)。我希望这可能有所帮助。