Как написать или в каком направлении копать алгоритм на C++?

Question

[Leonid Fedotov]

Есть большой массив данных, причём их можно хранить в любом виде, как и в TXT-файле, так и в MySQL-базе для скорости. Данные являются ежеминутными измерениями и выглядят вот так:
15.02.2016/18:49 13
15.02.2016/18:48 10
15.02.2016/18:47 11
15.02.2016/18:46 9
15.02.2016/18:45 27
...и так далее, отсортировано по дате записи, в порядке убывания

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

Comments

[tsarevfs]

Большой массив это сколько? Линейный поиск не устраивает? Длина последовательности?

[Leonid Fedotov]

tsarevfs: длина - несколько десятков миллионов записей (записи ведутся аж с 2000 года). Длина последовательности произвольная, но чем больше, тем лучше. Линейный поиск - думал, но как реализовать "похожесть", то есть вероятность небольшого отклонения, но в целом значения похожие?

Answer 1

[ADRian]

Алгоримт. По сути там среднеквадратическое отклонение используется.

Только вам придется писать цикл типа:

for count = минимальное количество данних для кореляции
    to максимальное количество данних для кореляции
  for i = 0 to length(DataArray) - count
    correlationList.append(caclCorrelation(DataArray, i, count)

Что бы найти найболее подобною последовательность.

Для оптимизации можно на первом этапе выбросить большую часть даних. (ака метод Монте-Карло). Обычно достаточно и 2% даних.
А на втором этапе (когда у тебе уже будут "правильные" диапазоны) уже все даные посмотреть.

Один из методов считания уровня ошибки это имерить в 2 разы точнее — разница межну измерениями и будет оценкой уровня ошибки.
т. е. можна сделать алгоритм типа:

dataCountCoeficient = 0.001 // 0.1%
needAccuracy = 0.01 // 1%
oldResult = calcCorrelation(dataCountCoeficient / 2);
newResult = calcCorrelation(dataCountCoeficient)
while Abs(oldResult - newResult) / Max(Abs(OldResult), Abs(NewResult)) > needAccuracy do
  dataCountCoeficient *= 2
  oldResult = newResult
  newResult = calcCorrelation(dataCoutCoeficient)