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

我们有一个带字符串的长列表（大约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，则将相似字符串添加到dict.

一切都很好，但由于列表"a"的长度，速度非常非常慢。所以我想问一下，有没有一种方法可以以某种方式优化这些代码？有什么想法吗？

几个小的优化：

您可以在开始搜索之前从列表中删除重复项（例如a=list（set（a）））。目前，如果a包含18k个字符串"hello"的副本，它将调用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

当需要迭代多个项目时，itertools会提供帮助！

这个片段将排列字符串的所有可能性（排列），并以原始代码的方式返回它们。我觉得not in是一种不必要的昂贵检查方式，而不是蟒蛇。之所以选择置换，是因为它可以让您最多地检查两个给定字符串的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_rio（），这取决于您是否有足够的精度。

在这种情况下，一个简单的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)

相关内容

最新更新

热门标签：