Простое прогнозирование байтовой информации

Нулевой уровень поиска зависимостей

Оно же классическое прогнозирование временных рядов, видоизмененное под прогнозирование информации.

Пусть будет поток байтов (или скажем текст UTF-8) — входящие прогнозируемые данные. Поступающие данные сохраняем во множество сохраненной истории:

Делаем накопление повторяющихся кусочков информации - паттернов, с последующими за ними распределением вероятностей значений. Для этого используем следующую структуру:

Это ветвящаяся структура. Переменная root содержит паттерн нулевой длины. В этом паттерне в поле next_level_ptrn накапливается множество паттернов длиной в единицу. У каждого такого узла, дальше в поле next_level_ptrn следуют паттерны уже длиной в два. И т.д ветвится дерево паттернов. Корень это правая сторона паттерна, а углубление в ветви удлиняет паттерн добавлением символа к левой стороне паттерна.

По мере накопления истории, увеличивается количество упоминаний паттерна. Это количество суммируем в count_use_ptrn. Когда это количество достигает некоторого "достаточного" количества, то этот паттерн считается созревшим, и он дает ветви в next_level_ptrn, которые будут длиннее на единицу. При этом ветвлении, потребуется посчитать из сохраненной истории, сколько раз встречались эти более длинные паттерны. Позиции берутся из list_pos_meet_ptrn.

Каждый из таких паттернов накапливает в поле map_forecast_counter распределение вероятностей, следующих за паттерном значений. Вероятность возникновения одного из таких значений вычисляется методом forecast_probability().

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

Следует учитывать, что это приведены упрощенные структуры, совсем не оптимальные по скорости алгоритмов работающих с ними и расходу памяти, но которые проще и наглядней для понимания.

Для прогнозирования очередного значения, по последним запомненным в истории значениям, находим соответствующий паттерн наибольшей длины, и считаем, которое из значений имеет наибольшую вероятность forecast_probability(). Оно и будет наиболее вероятным прогнозом. Если этот прогноз не встретился сто раз подряд из ста случаев упоминания паттерна, то значит более точный прогноз пока не доступен, для более длинных паттернов пока не хватило статистики.

Пытаемся спрогнозировать очередное значение. Определили значение с максимальной вероятностью. После на вход приходит реальное значение, которое сравниваем с прогнозным. Суммируем удачные прогнозы: количество удачных прогнозов, деленное на всего прошедших значений будет вероятностью правильного прогноза.

Пришедшее реальное значение после добавляем в map_forecast_counter - накапливаем вероятности прогнозов.