テキストファイル内のパターンを検索するための高速アルゴリズム

Question

私は二重の配列、約200,000行×100列を持っています、そして、私は与えられたパターンに最も似たシーケンスを含む行を見つける高速アルゴリズムを探していますパターンは10〜100要素のどこにでもあり得る）。私はPythonを使用しているので、ブルートフォース方式（以下のコード：各行をループし、列インデックスを開始し、各点でユークリッド距離を計算する）には約3分かかります。

numpy.correlate関数は、この問題をはるかに迅速に解決することを約束します（20秒以内に同じデータセットで実行する）。しかし、単純に完全な行に渡ってパターンのスライディングドット積を計算します。つまり、類似性を比較するために、結果を最初に正規化する必要があります。相互相関を正規化するには、データの各スライスの標準偏差を計算する必要があります。これは、最初にnumpy.correlateを使用する速度向上を即座に無効にします。

Pythonで正規化相互相関をすばやく計算することはできますか？または、Cでブルートフォース方式をコーディングする必要がありますか？

def norm_corr(x,y,mode='valid'): 
    ya=np.array(y) 
    slices=[x[pos:pos+len(y)] for pos in range(len(x)-len(y)+1)] 
    return [np.linalg.norm(np.array(z)-ya) for z in slices] 

similarities=[norm_corr(arr,pointarray) for arr in arraytable] 

Answer 1

あなたのデータは、2D numpyの配列である場合、あなたはそれから（lenで200000行（パターン）の列が）2Dスライスを取り、一度にすべての行のノルムを計算することができます。次に、forループ内のウィンドウを右にスライドさせます。

ROWS = 200000 
COLS = 100 
PATLEN = 20 
#random data for example's sake 
a = np.random.rand(ROWS,COLS) 
pattern = np.random.rand(PATLEN) 

tmp = np.empty([ROWS, COLS-PATLEN]) 
for i in xrange(COLS-PATLEN): 
    window = a[:,i:i+PATLEN] 
    tmp[:,i] = np.sum((window-pattern)**2, axis=1) 

result = np.sqrt(tmp)