Skip to main content
 首页 » 编程设计

python3 (nltk/numpy/等) : ISO efficient way to compute find pairs of similar strings

2025年01月19日8exmyth

我有一个包含 N 个字符串的列表。我的任务是找到所有足够相似的字符串对。也就是说,我需要 (i) 一个相似性度量,它会产生一个预定义范围内的数字(比如在 0 和 1 之间)来衡量两个字符串的相似程度,以及 (ii) 一种通过 O(N^2) 的方法快速配对以找到高于某种阈值的那些(如果度量为更相似的字符串提供更大的数字,则说 >= 0.9)。对于大的 N,我现在正在做的事情非常慢(正如人们所预料的那样):

import difflib 
 
num_strings = len(my_strings) 
for i in range(num_strings): 
    s_i = my_strings[i] 
 
    for j in range(i+1,num_strings): 
        s_j = my_strings[j] 
        sim = difflib.SequenceMatcher(a=s_i, b=s_j).ratio() 
        if sim >= thresh: 
            print("%s\t%s\t%f" % (s_i,s_j,sim)) 

问题:

  1. 矢量化这个双循环以加速它的好方法是什么 也许使用 NLTK、numpy 或任何其他库?
  2. 您会推荐一个比 difflib 的比率更好的指标吗(同样来自 NLTK、numpy 等)?

谢谢

请您参考如下方法:

如果您想要最佳解决方案,则必须为 O(n^2),如果您想要最佳解决方案的近似值,则可以选择一个阈值并删除具有公平相似率的对。 我建议您使用其他指标,因为您使用 difflib 的比率增加了复杂性(这取决于字符串的长度)。这些比率可以是熵或曼哈顿/欧几里得距离。