Изменения

Первая проблема — природа коэффициентов разложения. Их Они распределены весьма плотно по сравнению с типичным размером окрестности поиска, а распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 1-2 порядка. Причины две — во-первых, в реальных данных низкочастотные гармоники всегда оказываются больше, во-вторых, в нашем случае высокочастотные гармоники приглушены нами же — исходный вектор длины K => разница между двумя соседними значениями в нём по модулю раскладываемом векторе значений не больше 1, если сетка полная (размер сетки = A), и не больше отношения длины окна A к размеру сетки A/KL, если она меньше A, так как разница между двумя соседними значениями в профиле последовательности равна либо 0, либо 1, либо −1. Следовательно, максимум i-го коэффициента разложения равен примерно (K+1-i)*A/KL. И всё это — распределено околонормальнооколо-нормально (чему, видимо, тоже есть обоснование — там же везде суммы «случайных» значений, а закон больших чисел никто не отменял).  Таким образом, разбиение пространства на какие-то области (построение индекса) уже становится проблемой — «полезных» измерений с большим относительно размера окрестности поиска диапазоном мало (3-5), бОльшая часть спектральных векторов распределена в центре всей области, центр маленький. То есть, при поиске приходится просматривать довольно много лишних векторов.

Кроме того, с очевидной оптимизацией линейный поиск становится ещё проще. При попарном сравнении всех векторов не нужно делать их сравнивать полностью! Их достаточно сравнивать с искомой окрестностью последовательно от первой координаты к последней K-ой. Учитывая природу коэффициентов разложения — это примерно соответствует порядку убывания абсолютных значений коэффициентов, а значит, в среднем и разности.

* Поиск по заданной области, требуемый как раз в нашем случае. В нашем случае не требуется ни внешнее хранение, ни обновляемость индекса(с ней у R-деревьев получше), поэтому более эффективными оказываются разделяющие деревья.

* После поиска нужно произвести окончательную фильтрацию неточного найденного набора элементов. Фильтрация по каждому измерению производится одним из двух способов, оптимальный из которых выбирается программносравнением размера фильтруемого набора с количеством элементов, которые придётся отсечь на шаге 2:*# Простым * Либо простым сравнением значения каждого элемента с искомой окрестностью — эффективно, если фильтруемый набор мал.*# Двоичным * Либо отсечением кусков вариационного ряда по ассоциативному массиву. Для этого двоичным поиском находится положение минимального и максимального значения измерения искомой окрестности (c-ε, c+ε) в соответствующем вариационном ряде и отсечением участков по нужной координате, а потом участки вариационного ряда от «известного» минимального/до «найденного» максимального, сохранённого /минимального значения удаляются из результата. Под «известным» диапазоном понимается найденный на этапе обхода дерева до найденного. Технически — во временный массив по номерам элементов из этих участков вариационного ряда сохраняется «1», а фильтруемый набор одним проходом фильтруется с помощью проверки элементов временного массива. На самом деле, при многократном поиске временный массив можно не обнулять, а вместо «1» можно использовать увеличиваемый при каждом следующем поиска счётчик. Эта стратегия эффективна в двух случаях — во-первых, если фильтруемый набор достаточно великбольше, и во-вторыхчем сумма размеров удаляемых участков. Обычно это случается, либо если какое-то измерение почти ничего не фильтрует — фильтрует (то есть, если полный диапазон значений по этому измерению сопоставим с размером окрестности поиска), либо если просто найдено очень много элементов.