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

Question

我有一个 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]

Answer 1

如果您的数据位于二维 Numpy 数组中，您可以从中获取一个二维切片(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)