Python 当它们都是数字和巨大时，在另一个序列中找到最相似的子序列

由于您正在处理一个大型数据集，因此算法的efficiency比使用更多的计算资源(例如.核)以更快地计算结果.

看起来你想要在一个更大的一维数组中检测一个一维图案，而可能有一个很好的resistance to noise.此操作通常可以使用correlation来完成，更具体地说，是cross-correlation.这一操作可以使用fast Fourrier transform(FFT)有效地完成.我们的 idea 是计算FFT^-1(FFT(a) * FFT(b)).这种方法也经常用于有效地计算卷积.这对于有效地检测模式非常有用.事实上，在冷战期间，FFT已经被开发出来用来检测地震仪中的核武器试验.因为它们已经被用于许多科学项目，包括引力方式的检测(更具体地说，检测两个黑洞的合并，这将在非常巨大的数据集中留下特定的事件信号形状).使用FFT通常是有效的，因为它们在O(n log n)中运行(而在O(n²)中运行的是朴素的相关性).

手动完成此处理相当繁琐.希望Scipy提供可以使用FFT:scipy.signal.correlate的关联函数.需要对信号进行归一化以进行关联，以提供有趣的结果.在实践中，减go 平均值通常就足够了.下面是一个例子:

import scipy.signal
import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

# What needs to be found
needle = np.array([0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1])

# The "large" dataset containing the searched pattern,but with some small noise
haystack = np.hstack([np.random.rand(3000), needle + np.random.rand(len(needle))*0.001, np.random.rand(2000)])

# Actual correlation (with a simple pseudo-normalization)
mean = haystack.mean()
corr = scipy.signal.correlate(haystack-mean, needle-mean, method='fft')

# Clean the results to make the interesting part more visible in plots
plotted = np.choose(corr<0, [corr**2, 0])

# Print the 5 best candidates
print(argpartition(corr, -5)[-5:])

plt.plot(plotted)
plt.show()

以下是生成的输出:

[2331 3017 2743 2742 3016]

在这里，我们可以看到，相关性成功地找到了5个最佳候选者中的模式，尽管有噪音.它的位置是3016.它实际上是这里的最佳候选者，但不能保证相关性直接找到最佳候选者.您需要先取K，然后逐个判断以找到正确的位置.数据集越大，K越大.如果数据集很大，并且搜索到的模式与数据集中的值相比明显可识别，则可以将K设置为数据集的1%.可以对K First值进行排序，以首先判断最佳候选者(在K个值中).可以使用L2规范np.sum((haystack_block - needle)**2)**0.5进行判断.具有最好的二语范数的候选人是最好的.这种相关性是为了避免计算所有可能候选者的L2正态(5个，而在上面的例子中是几千个).