Имеются разные последовательности событий:

• Набор возможных событий ограничен. Скажем, от 2-х до 10-и (монетку бросаем - 2 возможных события; кубик - 6; и т.п.).
• Каждое событие происходит в опеределенный момент времени в определенной точке пространства.
• Для простоты картины пространство одномерное.

Последовательности можно проиллюстрировать картинкой. Оси - время и координата одномерного пространства. Цвета символов соответствуют разным событиям.


Хочется написать программу сравнивающую пары таких последовательностей. На рисунке черная и малиновая последовательности больше похоже, чем каждая из них с желтой. Но хотелось бы посчитать некий коеффициент похожести.

-------------------------------

Мне кажется, что подобные задачи решают алгоритмы сравнения последовательностей нуклеотидов на хромосоме (или аминокислот в белках). Например, очень милый алгоритм Смита-Уотермана. 

В этих алгоритмах априори задаются коэффициенты похожести. Например, если в последовательностях два члена, стоящие в одинаковых положениях, не совпадают - штраф 10 баллов. Если в одной из последовательностей член пропущен - штраф 15 баллов Похожесть последовательностей оценивается суммой штрафов.

Но все эти алгоритмы не подразумевают развертки по непрерывным осям. В них следующий член последовательности идет непосредственно за предидущим. Допускается только пропустить/вставить один или несколько членов.

А мне нужно как-то сравнивать и положения событий по отношению к осям.

Подскажите, пожалуйста, кто что знает. Или просто идеи выскажите.

А для начала попробовать простую корреляцию пар (y_1i, y_2i) посчитать? (Если координаты x совпадают. Если нет - можно проинтерполировать.)

Просто как самое простое показалось. Конечно, надо поэкспериментировать на реальных данных, априори не говорю, что метод хорош - но зато очень прост 

Это не годится, к сожалению. Стоит задача не сравнения получаемых по точкам-событиям функций, а сравнения последовательностей событий. Так, например, с точки зрения функций прямая с тремя точками
(1,1)(2,2)(3,3)
и с двумя точками
(1,1)(3,3)
идентичны, т.к. описываются одной и той же функцией Y=X. Однако, в первом случае имеем три события, а во втором только два - совершенно разные сценарии.

ЗЫ: на моей первой картинке линии, соединяющие точки-события, смысла никакого не имеют. Они только показывают какое событие относится к какой последовательности.

Тогда конечно корреляция ни при чем...