用於字符串重複搜索的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代碼優化

回答

相關問題