我有一个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("%st%st%f" % (s_i,s_j,sim))
问题：
- 矢量化这个双循环以加速它的好方法也许使用 NLTK、numpy 或任何其他库？
- 你会推荐一个比difflib的比率更好的指标吗(再次，来自NLTK，numpy等(？
谢谢
如果你想要最优解，你必须是O(n^2(，如果你想要最优解的近似值，你可以选择一个阈值并删除具有公平相似率的对。我建议您使用另一个指标，因为您正在增加 difflib 比率的复杂性(这取决于字符串的长度(。这些比率可能是熵或曼哈顿/欧几里得距离。