搜索引擎/算法找到最接近的连续(浮点)采样信号？

Question

给定M个实数的任意两个序列/向量，我可以使用各种度量/规范轻松地计算它们的贴近度或相关性。但是，有没有一种有效的结构来在序列语料库中查找最接近的M序列，或者更长序列中最接近的子序列？滑动窗口将是一种幼稚/暴力的方法。不过，还有比这更好的吗？

编辑:当我输入这段文字时，我在想，像在K-d树中搜索这样的东西可能会起作用，其中每个偏移量都是M维空间中的一个单独维度？

Answer 1

如果滑动窗口可以工作，那么您可能正在执行cross-correlation，在这种情况下，您可以使用FFTs以O(n/cross-correlation(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的缓冲区，以使其长度加倍。

Answer 2

加速结构(如K-d树)的问题是，随着维数(问题中的M)的增加，它们变得不那么有效。如果你的M很大，你最好使用线性搜索。

如果你的M是中等大小的(大概6个左右，大概猜一下？)，那么可能值得尝试K-d树。有一些搜索结构可用于高维空间；我建议您查找Samet的《多维和度量数据结构的基础》。