@SergeySerge11

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

Как найти в 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 ) понятен(все с всем сравнить). Но очевидно что есть быстрее?

Что нужно знать?
  • Вопрос задан
  • 104 просмотра
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Формализуйте метрику корелляции. Там если расписать - то в итоге все придет к свертке (если одну последовательность развернуть сначала). Ее можно за n log n подсчитать быстрым преобразованием фурье.
Ответ написан
Комментировать
Griboks
@Griboks
Корреляция вычисляет схожеть на всей области определения. Вам нужны вейвлеты - они вычисляют схожесть произвольной ширины.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы