我们有一个很长的字符串列表(约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”的长度非常非常慢.因此,我想问一下是否有一种方法可以优化此代码？有任何想法吗？

解决方法:

几个小的优化：

>您可以在开始搜索之前从列表中删除重复项(例如a = list(set(a))).目前,如果a包含字符串’hello’的18k副本,它将调用diff 18k * 18k次.
>现在,您将比较字符串编号i与字符串编号j,以及字符串编号j与字符串编号i.我认为这些将返回相同的结果,因此您只能计算其中之一,而且运行速度可能快一倍.

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

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

>假设字符串的长度完全不同.如果字符串的长度在2的因数之内,diff将仅返回> 0.5.在这种情况下,您可以按O(nlogn)时间的长度对输入字符串进行排序,然后仅比较相似长度的字符串.
>假设字符串是单词的序列,并且期望是非常不同或非常相似的.您可以为单词构造一个倒排索引,然后仅与包含相同异常单词的字符串进行比较
>假设您希望将字符串分成少数几个组.您可以尝试运行K-means算法将其分组.这将花费K * n * I,其中I是您选择使用的K-means算法的迭代次数.

如果n变得非常大(数百万),则这些将不合适,您可能需要使用更多近似技术.用于群集网页的一个示例称为MinHash