Algoritmo rápido para buscar un patrón dentro del archivo de texto

Question

Tengo una matriz de dobles, aproximadamente 200,000 filas por 100 columnas, y estoy buscando un algoritmo rápido para encontrar las filas que contienen secuencias más similares a un patrón dado (el patrón puede estar en cualquier lugar de 10 a 100 elementos). Estoy usando Python, por lo que el método de fuerza bruta (código a continuación: iterando sobre cada fila e iniciando el índice de columna, y calculando la distancia euclidiana en cada punto) toma alrededor de tres minutos.

La función numpy.correlate promete resolver este problema mucho más rápido (ejecutando el mismo conjunto de datos en menos de 20 segundos). Sin embargo, simplemente calcula un producto de punto deslizante del patrón sobre la fila completa, lo que significa que para comparar la similitud, primero tendría que normalizar los resultados. La normalización de la correlación cruzada requiere calcular la desviación estándar de cada segmento de los datos, lo que al instante niega la mejora de la velocidad de uso de numpy.correlate en primer lugar.

¿Es posible calcular la correlación cruzada normalizada rápidamente en python? ¿O tendré que recurrir a la codificación del método de fuerza bruta en 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

Si los datos están en una matriz 2D Numpy, se puede tomar una rebanada de ella 2D (200000 filas por Len (patrón) columnas) y calcular la norma para todas las filas a la vez. A continuación, deslice la ventana hacia la derecha en un ciclo 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)