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

我有一个双打数组，大约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]

来源

2012-02-06 sbrother

我不知道numpy好，所以只是抛出一个想法：也许有一个更快的滑动方法来计算stddev？ – liori 2012-02-06 17:18:45

我只是想增加好奇心：我在机器上试过了你的代码，它在7秒内运行。我会建议不要创建这个数量的切片数组对象，但我不知道如何去做。 – 2012-02-06 18:30:26

如果你的数据是在2D numpy的数组，你可以（通过LEN（模式）列200000行）取2D切片从它和一次计算规范的所有行。然后在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)

来源

2012-02-06 20:47:48

正是我在找的，谢谢！ – sbrother 2012-02-06 21:42:38

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

回答

相关问题