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

Question

我有一个包含大约20万行和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

如果你的数据是一个二维的Numpy数组，你可以从中提取一个二维的切片（比如200000行和与模式长度相同的列数），然后一次性计算所有行的范数。接着，你可以在一个循环中将这个窗口向右移动。

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)