Szybki algorytm wyszukiwania wzorca w pliku tekstowym

Question

Mam tablicę podwójnych, z grubsza 200 000 wierszy po 100 kolumnach, i szukam szybkiego algorytmu do znalezienia wierszy zawierających sekwencje najbardziej podobne do danego wzorca (wzór może mieć od 10 do 100 elementów). Używam Pythona, więc metoda brute force (kod poniżej: pętla nad każdym wierszem i początkowy indeks kolumny i obliczanie odległości euklidesowej w każdym punkcie) zajmuje około trzech minut.

Funkcja numpy.correlate obiecuje znacznie szybsze rozwiązanie tego problemu (przeszukiwanie tego samego zestawu danych w czasie krótszym niż 20 sekund). Jednak po prostu wylicza przesuwający się produkt wzoru na całym wierszu, co oznacza, że ​​aby porównać podobieństwo, najpierw muszę znormalizować wyniki. Normalizowanie korelacji krzyżowej wymaga obliczenia odchylenia standardowego dla każdego fragmentu danych, co natychmiast neguje poprawę szybkości używania numpy.correlate w pierwszej kolejności.

Czy możliwe jest szybkie obliczenie znormalizowanej korelacji krzyżowej w pythonie? Czy będę musiał uciekać się do kodowania metody brute force w 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

Jeśli dane w tablicy 2D NumPy, można wziąć z niej kawałek 2D (200000 wierszy przez len (wzór) kolumny) i obliczyć normę dla wszystkich wierszy naraz. Następnie przesuń okno w prawo w pętli 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)