使用python搜索兩個字符串中的相似單詞（具有指定長度）的有效方法

我的輸入是兩個長度相同的字符串和一個數字，它表示我需要在兩個字符串中找到的常用單詞的長度。我寫了一個非常簡單的代碼來做到這一點，它可以工作，但它超級超級慢，考慮到每個字符串都是〜200K字母的事實。使用python搜索兩個字符串中的相似單詞（具有指定長度）的有效方法

這是我的代碼：

for i in range(len(X)): 
    for j in range(len(Y)): 
     if(X[i] == Y[j]): 
      for k in range (kmer):     
       if (X[i+k] == Y[j+k]): 
        count +=1 
       else: 
        count=0 
       if(count == int(kmer)): 
        loc=(i,j) 
        pos.append(loc) 
        count=0  

     if(Xcmp[i] == Y[j]): 
      for k in range (kmer):     
       if (Xcmp[i+k] == Y[j+k]): 
        count +=1 
       else: 
        count=0 
       if(count == int(kmer)): 
        loc=(i,j) 
        pos.append(loc) 
        count=0 

return pos

當第一序列是X，第二個是Y和k聚體是的常用詞的長度。（當我說的話，我只是意味着字符..）

我能夠創建一個由kmer矩陣X（而不是Y的巨大X），但這仍然是非常緩慢。

我也想過使用一個trie，但認爲它可能需要太長時間來填充它？

最後我只需要那些常見子序列的位置。

關於如何改進我的算法的任何想法？謝謝！ :)

來源

2014-01-16 FairyDuster

特里結構聽起來是個好主意。如果我理解正確，可以限制「kmer」的深度。 –

謝謝！有關如何開始實施trie的任何提示？特別是在有限的深度？ – FairyDuster

只需插入'X [0：kmer]'，'X [1：kmer + 1]'，...深度永遠不會超過'kmer' –

創建一組單詞這樣

words = {X[i:i+kmer] for i in range(len(X)-kmer+1)} 
for i in range(len(Y)-kmer+1): 
    if Y[i:i+kmer] in words: 
     print Y[i:i+kmer]

這是相當有效的，只要kmer不是那麼大，你會耗盡內存的設置。我認爲這不是因爲你已經創建了一個尺寸的矩陣。

對於位置，創建一個字典，而不是一組蒂姆表明

from collections import defaultdict 
wordmap = defaultdict(list) 
for i in range(len(X)-kmer+1): 
    wordmap[X[i:i+kmer]].append(i) 

for i in range(len(Y)-kmer+1): 
    word = Y[i:i+kmer] 
    if word in wordmap: 
     print word, wordmap[word], i

來源

2014-01-16 03:11:39

由於OP需要匹配的*位置*，所以'words'可能需要是一個將字符串映射到字符串開頭的索引列表的字典。 –

你真了不起！非常感謝你！ :)）） – FairyDuster

一個三重嵌套for循環給你一個n^3的運行時間，因爲你是從字面上檢查每個條目。考慮使用Rolling Hash。它具有線性平均運行時間和最差情況n^2。最好是找到子串，或多或少地找出你正在做的事情。在這種情況下，你可能更接近n^2，但在n^3時仍然很好。

來源

2014-01-16 03:00:07 ZekeDroid

使用python搜索兩個字符串中的相似單詞（具有指定長度）的有效方法

回答

相關問題