文字列重複検索のためのPythonコードの最適化

Question

長いリストには文字列（約18kのエントリ）があります。目標は、すべての類似した文字列を検索し、それらを最大の類似性でグループ化することです。

（「」文字列を含むリストである）私は、次のコードを書いている：

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と比較します。私はこれらが同じ結果を返すと思いますので、あなたはこれらのうちの1つだけを計算し、恐らく2倍速く行くことができます。もちろん

、基本的な問題は、diffが長さのリストについてのn * n回呼び出されていることであるnと、理想的な解決策は、時間差分の数が呼び出されている減らすことであろう。使用方法は、文字列の内容によって異なります。ここで

は異なるケースに関連するだろう可能なアプローチのいくつかの例です：

1. は、文字列が非常に異なる長さであると仮定します。 diffは、文字列の長さが2の係数内にある場合にのみ0.5を返します。この場合、入力文字列をO（nlogn）時間で長さでソートし、同様の長さの文字列を比較することができます。

2. 文字列が一連の単語であり、非常に異なるか非常に似ていると予想されるとします。単語の逆索引を作成し、同じ珍しい単語を含む文字列と比較することができます

3. 文字列が少数のグループに入ると想定します。それらをクラスタにグループ化するためにK平均アルゴリズムを実行しようとすることができます。これはK * n * Iをとります。ここでは、私が使用するK平均アルゴリズムの反復回数です。 nは（何百万）が非常に大きくなるように成長した場合

、これらは適切ではないであろうと、あなたはおそらくよりおおよその技術を使用する必要があります。 Webページのクラスタリングに使用される1つの例は、MinHash

Answer 2

多くのアイテム、itertoolsを繰り返し処理する必要がある場合、レスキュー！

このスニペットは、文字列（置換）のすべての可能性を並べ替えて元のコードのやり方で返します。私はnot inがpythonicとしてではなく、チェックするために不必要に高価な方法だと感じています。 Permutationsは、2つの指定された文字列の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（）を使用していますが、十分な精度があるかどうかの判断に応じて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)