Нахождение самого похожего участка в сигнале, БПФ, БПХ и другие методы Опции

[getch]

Приветствую всех!

Я от ЦОС далек, но задача, по-моему, найдет здесь понимание.

Постановка задачи:
1. Есть ВР (временной ряд (вещественный), LEN точек), который с определенной частотой дополняется новым членом.
2. Есть Шаблон - N точек.
3. Надо найти в ВР участок, который наиболее сильно "похож" на Шаблон. Соответственно, в этом участке тоже N точек.

Критерием похожести я выбрал КК (коэффициент корреляции). Т.е. задача сводится к нахождению максимума абсолютного значения КК.

Нашел два оптимизированных алгоритма расчета быстрой корреляции: через БПФ (вещественное) и БПХ (Хартли).

Честно говоря, математическую часть алгоритмов слабо понимаю. И у меня возникло несколько вопросов:
1. Имеет ли смысл для моей задачи (с точки зрения скорости выполнения) использовать алгоритм БПФ для длин векторов, не являющихся степенями двойки? Это работы Бейли, Просекова и другие.
2. БПФ Винограда?
3. Возможно, есть другой эффективный критерий похожести, отличный от КК.
4. Задача, очевидно, стандартная и максимально эффективный велосипед уже давно изобретен. Подскажите, как официально она называется?
5. Какие могут быть оптимизации, чтобы не проделывать полностью вычисления БПФ? Поясню ниже на примере двух случаев:

1. Шаблон - это крайние N точек исходного ВР из Len точек. Пришло новое значение ВР, т.е. его длина стала (Len + 1) точек. Шаблон, соответсвенно "сместился" вправо (изменился) тоже на одно значение. БПФ заново пересчитывать?
2. Шаблон - это какой-то участок из N точек исходного ВР. Если я сдвигаю шаблон на одну точку в какую-то сторону, БПФ надо будет полностью пересчитывать?

И еще один вопрос, если надо найти похожий участок не только на шаблон, но и на "перевернутый шаблон" - точки в обратном направлениии (Было {1, 2, 5, 7}, стало {7, 5, 2, 1}), то можно ли из "нормального" БПФ перейти эффективно к "перевернутому" БПФ?

Уверен, моя косноязычная формулировка задачи вызовет улыбку у форумчан, особенно у гуру. Но это все же хорошие эмоции. Готов учиться и вникать.

P.S. Если возможно, разъясните на более понятном языке, что имелось в виду в этом посте (Сообщение #28)?

[eugen_pcad_ru]

Кхм, может я глупый вопрос задам, но:
метод наименьших квадратов не подходит? Корень из суммы квадратов разностей реального фрагмента и идеального фрагмента?
Минимальная сумма соответствует наибольшей "похожести". При полном соответсвии получите нуль.

P.S.: Хотя может я чего и не понял

[getch]

метод наименьших квадратов не подходит?

Алгоритмическая сложность такого метода "лобовая" - O(N^2).
Быстрая корреляция через БПФ значительно эффективнее - O(N * log(N)).

[xemul]

Алгоритмическая сложность такого метода "лобовая" - O(N^2).

Ещё хуже, т.к. один из сравниваемых фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент.

[getch]

Ещё хуже, т.к. какой-то из фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент.

Существует итерационный алгоритм расчета СКО сдвинутого окна через СКО окна до сдвига.
Нормировка делается через деление фрагмента на его почти бесплатно полученное СКО.

При этом Среднее каждого фрагмента обнулять не требуется при сравнении. Надо лишь один раз отнормировать сам шаблон (что ищется) к СКО = 1 и Ср. = 0.