0

~100 万個の一意の 16 文字の文字列 (VEC と呼ばれる配列) のリストがあり、Python でそれぞれの最小ペアワイズ ハミング距離 (RES と呼ばれる配列) を計算したいと考えています。基本的に、完全なペアワイズ距離行列を一度に 1 行ずつ計算していますが、各行の 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

わずか 10,000 の短い VEC には約 70 秒かかりましたが、それを 100 万に推定すると 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

おそらく驚くべきことではありませんが、この 2 番目のアプローチはほぼ 2 倍の時間 (117 秒) かかるため、あまり良くありません。とにかく、これを高速化するための改善/変更を推奨できる人はいますか?

4

2 に答える 2

1

各 bitary (それ自体を無視する) に最近傍のみが必要で、おおよその最近傍のみを取得する可能性がほとんどない場合は、ハミング距離に「ビット サンプリング」局所性依存ハッシュを実装することを検討してください。簡単に言えば、3 つのハッシュ テーブルを作成します。各 128 ビット入力から、16 ビットを 3 回サンプリングし、それらの 16 ビット サンプルをキーとして使用します。ハッシュ テーブルの値は、そのサンプリングされたキーを持つすべての 128 ビット入力のリストである必要があります。何百万もの入力をすべて LSH インデックスに配置したら、次のようにします。

  • 100万点以上繰り返す
  • 入力ごとに、上記の 3 サンプリングを実行します。
  • 3 つのリストのそれぞれで (距離が 0 より大きい) 最も近いものを見つけ、全体的に最良のものを維持します。

読み込みとテストは、ばかばかしいほど高速です。これを支える優れたbitarrayライブラリをお勧めします。

于 2015-03-19T21:22:50.027 に答える
0

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 つの文字列が 2 回出現する可能性がある場合は、1 より大きい距離だけを見つけたくないと思います。

コンピューターでテストしたところ、200 個の文字列を処理するのに約 10 秒かかりました。1 つにつき、他の 1 000 000 個の文字列すべてを調べる必要があるため、それらすべてを処理するのにかかる時間をかなり簡単に計算できます。約13時間のはずです。ただし、現時点では 1 つのコアしか使用していないことを忘れないでください。インデックスを分割してhttp://docs.python.org/2/library/multiprocessing.html#module-multiprocessing.poolを使用すると、結果をすぐに取得できます。

于 2013-05-30T20:16:08.807 に答える