Поисковые системы / алгоритмы для поиска ближайшего непрерывного (с плавающей запятой) дискретизированного сигнала?

Question

Учитывая любые две последовательности / векторы M действительных чисел, я могу легко вычислить их близость или корреляцию, используя различные метрики / нормы. Но существует ли эффективная структура для поиска ближайшей M-последовательности в совокупности последовательностей или ближайшей подпоследовательности более длинной последовательности? Раздвижное окно было бы наивным / грубым подходом. Кто-нибудь знает что-нибудь лучше, хотя?

РЕДАКТИРОВАТЬ: Поскольку я набираю это, я думаю, что что-то вроде поиска в дереве K-d может работать, где каждое смещение является отдельным измерением в M-мерном пространстве?

Answer 1

Проблема с ускоряющими структурами (такими как K-d-деревья) состоит в том, что они становятся менее эффективными по мере увеличения размерности (M, в вопросе). Если ваш М очень большой, вам лучше использовать линейный поиск.

Если ваш М среднего размера (примерно до 6 или около того, как приблизительный пример?), Возможно, стоит попробовать дерево K-d. Существуют поисковые структуры, доступные для многомерных пространств; Я рекомендую поискать Основы многомерных и метрических структур данных , по Самет.

Answer 2

Если скользящее окно будет работать, вы, вероятно, делаете взаимную корреляцию , и в этом случае вы можете использовать FFT , чтобы решить вашу проблему быстрее с коэффициентом O ((n / log (n)).

Так что, если у вас есть вектор V и корпус из C других векторов, и все векторы имеют размер N, тогда решение скользящего окна будет принимать O (N ^ 2 *В) времяИспользуя БПФ, вы можете уменьшить одно скользящее окно с O (N ^ 2) до O (N log N), поэтому общее время будет равно O (CN log N).

Если вы не знакомыс БПФ тогда вам, вероятно, придется прочитать их перед использованием, но общая идея такова:

# 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) БПФ коррелируют в предположении, что все эти сигналы являются круговыми.Если вы не хотите обращаться с ними как с круглыми, то вам нужно добавить буфер 0 в конец каждого вектора, чтобы удвоить его длину.