针对字符串重复搜索，优化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"的长度非常长，所以速度非常慢。因此我想问是否有方法来优化此代码？有什么想法吗？

- annndrey

---

你需要做的第一件事情是确定实际的瓶颈在哪里。我猜测 SequenceMatcher.ratio() 的计算成本相当高，因此你可以尝试使用 quick_ratio() 或者甚至是 real_quick_ratio() 来代替。 - Niklas B.

此外，你在这里使用SequenceMatcher有什么原因吗？也许你可以提供自己的差异度量标准，这将针对你的问题进行优化，而不是诉诸于一个似乎文档不太好的函数quick_ratio。了解你的问题的背景会有所帮助：每个字符串有多长，如果它们相似很重要，你想如何定义相似性等等。 - machine yearning

请注意，quick_ratio 比 ratio 差得多... 乱序词比率尤其令人困扰。以 "contains" 和 "sanction" 为例：quick_ratio 是 1.0，但是 ratio 只有 0.375。但它确实提供了一个上限，所以你可以两者都使用——使用 quick_ratio 快速排除明显不同的字符串，然后在剩下的内容上使用更昂贵的 ratio。显然您需要对此进行分析，最坏情况下会更慢。 - cha0site

好的，我错过了quick_ratio和real_quick_ratio。首先使用它们是个好主意。我认为另一个问题是迭代18000个元素的列表。有更快的迭代方法吗？ - annndrey

Answer 1

当需要遍历许多项时，itertools应运而生!

以下代码段可以将您的字符串的所有可能排列（排列）进行排列，并以您原始代码的方式返回它们。 我认为使用 not in 的方式是一种不必要昂贵的检查方式，也不够pythonic。选择排列是因为它可以使您最方便地检查给定两个字符串 a->b 或 b->a 之间的关系。

import difflib
import itertools

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

def calculate_ratios(strings):
     dupl = dict()
     for s, t in itertools.permutations(strings, 2):
          try:
               dupl[s].append({t: diff(s,t)})
          except KeyError:
               dupl[s] = []
               dupl[s].append({t: diff(s,t)})
     return dupl

a = ['first string', 'second string', 'third string', 'fourth string']
print calculate_ratios(a)

根据您的限制（因为排列在计算和空间方面是冗余的），您可以用组合替换排列，但是访问方法需要进行调整（因为a-b只会在a[b]中列出，而不是b[a]）。

在代码中我使用了quick_ratio()，但是根据您是否需要足够的精度，它可以简单地更改为ratio()或real_quick_ratio()。

在这种情况下，一个简单的IF语句就可以解决这个问题：

import difflib
import itertools

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

def calculate_ratios(strings, threshold):
     dupl = dict()
     for s, t in itertools.permutations(strings, 2):
          if diff(s,t) > threshold: #arbitrary threshhold
               try:
                    dupl[s].append({t: diff2(s,t)})
               except KeyError:
                    dupl[s] = []
                    dupl[s].append({t: diff2(s,t)})
     return dupl

a = ['first string', 'second string', 'third string', 'fourth string']
print calculate_ratios(a, 0.5)

- hexparrot

---

非常好，我在我的算法中加入了quick_ratio和ratio，大大提高了性能。处理时间减少了近6倍。谢谢！ - David Vega

Answer 2

一些小优化：

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

2. 目前，您将比较字符串编号i和字符串编号j，以及字符串编号j和字符串编号i。我认为它们将返回相同的结果，因此您只能计算其中一个，并且可能会快两倍。

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

以下是几种可能适用于不同情况的方法示例：

1. 假设字符串长度差异很大。如果字符串的长度在2倍范围内，diff函数才会返回>0.5。在这种情况下，您可以按长度对输入字符串进行排序，时间复杂度为O(nlogn)，然后仅比较长度相似的字符串。

2. 假设字符串是单词序列，并且预计非常不同或非常相似。您可以为单词构建反向索引，然后仅与包含相同不寻常单词的字符串进行比较。

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

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

- Peter de Rivaz