寻找最接近的连续（浮点数）采样信号的搜索引擎/算法？

Question

给定两个包含M个实数的序列/向量，我可以使用多种度量标准轻松计算它们的相似度或相关性。但是，在一组序列中查找最接近的M序列或更长序列的最接近子序列是否有高效的结构？滑动窗口可能是朴素/暴力的方法。不过，有没有更好的方法呢？

编辑：当我打字时，我在想像在K-d树中搜索可能有效，其中每个偏移量是M维空间中的一个单独维度？

- btown

Answer 1

加速结构（如K-d树）存在的问题在于，随着维度（问题中的M）的增加，它们变得越来越不有效。如果你的M非常大，最好使用线性搜索。

如果你的M是适度大小的（大约6左右），可以尝试使用K-d树。针对高维空间有可用的搜索结构；我建议查阅Samet的《多维和度量数据结构基础》。

- comingstorm

Answer 2

如果滑动窗口可以使用，你可能正在进行交叉相关，在这种情况下，你可以使用FFT来通过O(n/log(n))的速度因子更快地解决问题。

所以，如果你有一个向量V和C个其他向量的语料库，所有向量的大小都是N，那么滑动窗口的解决方案将需要O(N^2 * C)的时间。通过使用FFT，你可以将单个滑动窗口从O(N^2)降至O(N log N)，因此总时间将为O(CN log N)。

如果你不熟悉FFT，则在使用它们之前可能需要阅读相关资料，但总体思路是这样的：

# If you forget to take the complex conjugate of V you'll be doing a
# convolution instead of a correlation
V' := Fft(Conjugate(V))

for each vector W in C:
    W' := Fft(W)
    P := W' * V'   # Multiplication here is the dot product
    R := inverse_Fft(P)
    # Check through the vector R for any spikes, a large value at
    # R[i] indicates that if you shift W' by i then it will
    # correlate strongly with W

警告：

1）如果您正在进行相关性分析，您需要对向量进行归一化，或者至少要做些什么来确保您不会从值仅比其他向量更大且更正的向量中获得错误的结果。但是，如果您的典型用例是在噪声中寻找信号，那么您就没问题了。

2）FFT在假定所有这些信号都是循环的情况下进行相关分析。如果您不想将它们视为循环，则需要在每个向量的末尾添加0的缓冲区以使其长度加倍。

- Running Wild

---

这真的很酷！我实际上正在攻读电气工程专业，但我不知道频域对于解决这个问题会有用！可悲的是，我正在尝试在ActionScript中实现它（o_o），所以说起来容易做起来难，但我期待着尝试一下！ - btown