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

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

10 голосов
/ 06 февраля 2012

У меня есть массив значений типа double, примерно 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]

1 Ответ

1 голос
/ 07 февраля 2012

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