Быстрый алгоритм поиска шаблона в текстовом файле

Question

У меня есть массив удвоений, примерно 200 000 строк по 100 столбцов, и я ищу быстрый алгоритм для поиска строк, которые содержат последовательности, наиболее похожие на данный шаблон (шаблон может быть от 10 до 100 элементов). Я использую python, поэтому метод грубой силы (код ниже: цикл по каждой строке и начальный индекс столбца и вычисление евклидова расстояния в каждой точке) занимает около трех минут.

Функция 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, вы можете взять 2D кусочка от него (200000 строк Лена (шаблон) столбцы) и вычислить норму для всех строк сразу. Затем сдвиньте окно вправо в цикле 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)