Metin dosyası içinde desen aramak için hızlı algoritma

Question

Ben bir çift, bir dizi var 100.000 tarafından yaklaşık 200.000 satır, ve ben belirli bir desenle en benzer dizileri içeren satırları bulmak için hızlı bir algoritma arıyorum desen 10 ila 100 element arasında olabilir). Ben python kullanıyorum, bu yüzden kaba kuvvet yöntemi (aşağıdaki kod: her satırın üstünden döngü ve sütun indeksini başlatma ve her noktada Euclidean mesafesini hesaplama) üç dakika kadar sürer.

numpy.correlate işlevi, bu sorunu çok daha hızlı bir şekilde çözmeyi vaat eder (aynı veri kümesi üzerinde 20 saniyeden daha kısa bir süre boyunca çalışır). Bununla birlikte, modelin sürgülü bir nokta çarpımını tam satır üzerinde hesaplar, yani benzerliği karşılaştırmak için sonuçları ilk önce normalleştirmek zorundayım. Çapraz korelasyonun normalleştirilmesi, verilerin her bir diliminin standart sapmasının hesaplanmasını gerektirir ve bu da numpy.correlate'in ilk etapta kullanılmasının hızını hemen ortadan kaldırır.

Python'da normalize çapraz korelasyonu hızlı bir şekilde hesaplamak mümkün müdür? Yoksa C'deki kaba kuvvet yöntemini kodlamak zorunda mıyım? Veri 2D Numpy dizide ise

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

, sen (len (pattern) sütunlarına göre 200000 satırları) ondan bir 2D dilim almak ve bir kerede tüm satırlar için normunu hesaplayabilir. Ardından pencereyi for döngüsünde sağa kaydırın.

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)