python - 用于字符串重复搜索的python代码的优化

Question

我们有一个长长的字符串列表(大约 18k 个条目)。目标是找到所有相似的字符串并按最大相似性对它们进行分组。 (“a”是带有字符串的列表)

我写了下面的代码:

def diff(a, b):
    return difflib.SequenceMatcher(None, a, b).ratio()

dupl = {}

while len(a) > 0:
    k = a.pop()
    if k not in dupl.keys():
        dupl[k] = []
    for i,j in enumerate(a):
            dif = diff(k, j)
            if dif > 0.5:
                dupl[k].append("{0}: {1}".format(dif, j))

此代码从列表中取出一个元素并在列表的其余部分中搜索重复项。如果相似度大于 0.5，则将相似的字符串添加到字典中。

一切正常，但由于列表“a”的长度，速度非常非常慢。所以我想问一下有没有办法以某种方式优化这段代码？有什么想法吗？

Answer 1

一些小的优化:

1. 您可以在开始搜索之前从列表中删除重复项(例如 a=list(set(a)))。目前，如果 a 包含字符串 'hello' 的 18k 个副本，它将调用 diff 18k*18k 次。

2. 目前，您将比较字符串编号 i 和字符串编号 j，以及字符串编号 j 和字符串编号 i。我认为这些将返回相同的结果，因此您可以只计算其中一个，而且速度可能会提高一倍。

当然，基本问题是对于长度为 n 的列表 diff 被调用 n*n 次，理想的解决方案是减少 diff 被调用的次数。使用的方法将取决于字符串的内容。

以下是与不同情况相关的可能方法的一些示例:

1. 假设字符串的长度非常不同。如果字符串的长度在 2 的因数以内，diff 将仅返回 >0.5。在这种情况下，您可以在 O(nlogn) 时间内按长度对输入字符串进行排序，然后只比较具有相似长度的字符串。

2. 假设字符串是由单词序列组成的，并且预计它们要么非常不同，要么非常相似。您可以为单词构建倒排索引，然后只与包含相同不寻常单词的字符串进行比较

3. 假设您希望字符串分为少数几个组。您可以尝试运行 K-means 算法将它们分组到集群中。这需要 K*n*I，其中 I 是您选择使用的 K-means 算法的迭代次数。

如果 n 变得非常大(数百万)，那么这些将不合适，您可能需要使用更多近似技术。用于聚类网页的一个示例称为 MinHash