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

我们拥有一个包含字符串的长列表（约18k条目）。目标是找到所有类似的字符串并按最大相似性对它们进行分组。（“a”是用绳子名单）用于字符串重复搜索的Python代码优化

我已经写了下面的代码：

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”的长度而非常非常慢。所以我想问问有没有办法优化这个代码？有任何想法吗？

来源

2012-03-23 annndrey

您应该做的第一件事是描述这里的实际瓶颈。我的猜测是'SequenceMatcher.ratio（）'相当昂贵，所以你可以尝试使用'quick_ratio（）'或甚至'real_quick_ratio（）'来代替。 – 2012-03-23 17:47:48

另外，你有什么理由在这里使用'SequenceMatcher'？也许你可以提供你自己的差异度量，这个度量可以针对你的问题进行优化，而不是诉诸像'quick_ratio'这样看起来很差的函数。这将有助于理解问题的背景：每个字符串有多长，为什么它们很重要，如果它们相似，以何种方式定义相似性等等。 – 2012-03-23 18:03:08

请注意，'quick_ratio'比'比率... ... anagrams的比率尤其成问题。以“contains”和“sanction”为例：'quick_ratio'为'1.0'，但'ratio'为'0.375'。但它确实给出了一个上限，所以你可以同时使用它们 - 使用'quick_ratio'来快速消除明显不同的字符串，然后在剩下的部分使用更昂贵的比率。显然你会想要描述这个，最糟糕的情况是它可能会变慢。 – cha0site 2012-03-23 18:04:24

几个小的优化的：

你可以开始搜索前从列表中删除重复项（例如a = list（set（a）））。目前，如果a包含字符串“hello”的18k副本，它将调用diff 18k * 18k次。
Curently你会比较字符串我数与字符串号j，并且还串号j与串号我。我认为这些结果会返回相同的结果，因此您只能计算其中的一个，并且可能会快两倍。

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

以下是这将是相关的不同的情况可能的方法的几个例子：

假设字符串是非常不同的长度。如果字符串的长度在2的因子范围内，diff只会返回> 0.5。在这种情况下，您可以按照O（nlogn）时间长度对输入字符串进行排序，然后只比较具有相似长度的字符串。
假设字符串是单词的序列，并且预期会非常不同或非常相似。您可以为单词构造倒排索引，然后仅与包含相同不常用单词的字符串进行比较。
假设您期望字符串属于少数组。您可以尝试运行K-means算法将它们分组为簇。这需要K * n * I，其中I是您选择使用的K-means算法的迭代次数。

如果n增长得非常大（几百万），那么这些将不合适，您可能需要使用更多近似技术。用于群集网页的一个示例称为MinHash

来源

2012-03-23 20:03:12

当需要遍历许多项目，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)

根据您的约束，（因为排列是多余的计算和空间明智的），你可以替换的组合排列，但那么你的访问方法将需要进行调整（因为AB将只在上市[b]但不是b [a]）。

在我使用quick_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)

来源

2012-03-23 18:21:38 hexparrot

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

回答

相关问题