尋找快速的方式來計算多對字符串的明智的距離

我有一個約100萬個獨特的16字符字符串（一個數組稱爲VEC）的列表，我想計算每個人的最小成對漢明距離Python（一個名爲RES的數組）。基本上，我一次只計算一行完整的成對距離矩陣，但僅將每行最小值存儲在RES中。尋找快速的方式來計算多對字符串的明智的距離

VEC= ['AAAAAAAAAAAAAAAA','AAAAAAAAAAAAAAAT','AAAAGAAAAAATAAAA'...]

使得DIST（VEC [1]，VEC [2]）= 1，DIST（VEC [1]，VEC [3]）= 2等...和RES [1] = 1。使用提示和技巧，通過這些頁面，我想出了：

#METHOD#1: 
import Levenshtein 
import numpy 
RES=99*numpy.ones(len(VEC)) 
i=0 
for a in VEC: 
    dist=numpy.array([Levenshtein.hamming(a,b) for b in VEC]) #array of distances 
    RES[i]=numpy.amin(dist[dist>0]) #pick min distance greater than zero 
    i+=1

的只有10000縮短VEC花了大約70秒，但如果我推斷出充分萬人將需要8天。我的做法似乎是浪費，因爲我重新計算距離矩陣的對稱部分，所以我嘗試，我跟着去計算矩陣的一半，而更新RES每一行：

#METHOD #2: 
import Levenshtein 
import numpy 
RES=99*numpy.ones(len(VEC)) 
for i in range(len(VEC)-1): 
    dist=[Levenshtein.hamming(VEC[i],VEC[j]) for j in range(i+1, len(VEC))] 
    RES[i]=min(numpy.amin(dist),RES[i]) 
    #update RES as you go along: 
    k=0 
    for j in range(i+1,len(VEC)): 
     if dist[k]<RES[j]: 
      RES[j]=dist[k] 
     k+=1

也許並不奇怪，這第二方法需要幾乎兩倍的時間（117秒），所以它不是很好。無論如何，任何人都可以推薦改進/更改以使其更快嗎？

來源

2013-01-21 jfb

這可能需要很長時間。您可以嘗試減少搜索空間，也許可以通過計算每個字符串中的字符集，而不是在不相交時計算距離。你對弦的結構有任何額外的瞭解嗎？如果這樣做，可能會進一步限制搜索。 – BrenBarn

計算給定行中的第一個成對距離。現在，對於同一行中的所有其他距離計算，在距離超過此初始距離之後停止它。如果更短，請更新當前最小值並重復。這並不會降低時間複雜度，但可能會有很大幫助，具體取決於您的字符串排序方式。此外，這個問題很簡單，可以在C中重新編碼，並得到另一個不斷減少。 – mmgp

另外，你看過使用'scipy.distance'嗎？它具有漢明距離度量。我不知道Levenshtein圖書館是如何優化的，但有可能通過將您的數據轉換爲大型的數組並使用scipy工具來獲得收益。 – BrenBarn

我試着用numpy。這裏是我的代碼：

#!/usr/bin/env python 

import numpy as np 
import time 

def gen_data(n): 
    arr = np.empty(shape=(n, 16)) 
    for i in range(n): 
     arr[i] = np.random.randint(ord('A'), ord('Z')+1, 16) 
    return arr 

def distance_from_array(i, arr): 
    r = arr[i] != arr 
    r[i,:] = True 
    min_i = np.argmin(np.sum(r, axis=1)) 
    return min_i 

data = gen_data(1000000) 
distances = [] 
start = time.time() 
for i in range(200): 
    distances.append(distance_from_array(i, data)) 
end = time.time() 
print end - start

您可以將字符串列表轉換爲數組數組。然後你可以使用numpy函數來處理數組，例如sum和argmin。我想你不想只找到大於1的距離，如果有可能一個字符串出現兩次。

我在我的電腦上測試過它，處理200個字符串需要大約10秒。對於每一個你必須經歷所有1 000 000個其他字符串，因此我們可以計算出處理所有這些字符所需的時間。它應該在13個小時左右。但是，不要忘記，我們目前只使用一個內核。如果您拆分索引並使用http://docs.python.org/2/library/multiprocessing.html#module-multiprocessing.pool，則可以快速獲得結果。

來源

2013-05-30 20:16:08

如果你只需要近鄰每個bitarry（忽略本身），你可以逃脫的只得到近似最近鄰居一個微小的機會，你可能會考慮實施「位採樣」局部敏感哈希爲海明距離。簡而言之，創建三個哈希表。從每個128位輸入採樣16位3次，使用這些16位採樣作爲密鑰。哈希表的值應該是具有該採樣關鍵字的所有128位輸入的列表。一旦你將你輸入的所有萬成LSH指標，簡單地說：

遍歷萬點
對於每個輸入，執行上述3採樣
查找每個近鄰三個列表（距離> 0），保持最佳整體

加載和測試都是非常快速的。我可能會推薦優秀的bitarray庫來支撐這一點。

來源

2015-03-19 21:22:50 Rob

尋找快速的方式來計算多對字符串的明智的距離

回答

相關問題