Skip to main content
 首页 » 编程设计

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

2025年01月19日22luoye11

我有两个非常长的 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。

请您参考如下方法:

我可以建议另一种解决方案,但我不确定您是否想要我建议的完全相同的东西。 首先,有两个列表,如果我们将列表中的一个元素与其自身进行匹配,则相似度为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)。我希望这可能有所帮助。