在文本文件中搜索模式的快速算法

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 行乘 len(pattern) 列）并立即计算所有行的范数。然后在 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)