Как найти похожие отрезки в 2 множествах данных, или корреляцию с смещением?

Question

[SergeySerge11]

Как найти в 2 множествах значениях(или 2 функциях) наиболее похожие отрезки? Множества СО СДВИГОМ.
То есть найти наивысший отрезок корреляции?
Допустим для данных описанных уравнением
1. функция y=sin(x)
2. и функция y=sin(x + bias)
Я хочу получить Корреляцию(или что-то там) 1.0 =100% (так как очевидно это сдвинутая функция)
Понятно для таких примеров Фурье даст 100% схожие коэффициенты. Но что если только на участке есть схожесть?
ИЛИ
К примеру массив 1 2 3 4 5 6 и массив 9 8 7 6 5 -1 0 2.5 4 5 11 массив 2* имеет корреляцию на отрезке (-1;5) с массивом 1. Как ее найди.

Общая задача. Найти в 2 Мелодиях наиболее похожий момент.
Наиболее интуитивный алгоритм, это О(N^2 /2 ) понятен(все с всем сравнить). Но очевидно что есть быстрее?

Что нужно знать?

Comments

[U235U235]

Посмотрите литературу по алгоритмам на строках и/или биоинформатике (поиск последовательностей в ДНК). Возможно это то, что вы ищите.

Answer 1

[Wataru]

Формализуйте метрику корелляции. Там если расписать - то в итоге все придет к свертке (если одну последовательность развернуть сначала). Ее можно за n log n подсчитать быстрым преобразованием фурье.

Answer 2

[Griboks]

Корреляция вычисляет схожеть на всей области определения. Вам нужны вейвлеты - они вычисляют схожесть произвольной ширины.