Алгоритм Витерби за линейное время

Question

У меня проблема с заданной скрытой марковской моделью и состояниями S. Мне нужно найти алгоритм, который возвращает наиболее вероятный путь через скрытую марковскую модель для данной последовательности X за время O (| S |).

Я думал о разработке графа, в котором у меня были бы все разные состояния в разных позициях в X, и я запустил алгоритм на кратчайшем пути на этом графе. Однако у меня будет n | S | ^ 2 ребер (где n - число состояний в X) и n | S | вершины.

Лучший алгоритм, который я нашел, - это ациклический кратчайший путь, который проходит во времени O (| E | + | V |), который в моем случае равен O (| S | ^ 2). Есть ли какой-нибудь алгоритм, который я могу разработать, чтобы он выполнялся за время O (| S |)? Все, что мне нужно, это общая идея.

Спасибо

Answer 1

Я думаю, что если вы хотите получить точную наиболее вероятную последовательность, вы не можете сделать это за линейное время во всех случаях.Однако, если ваше пространство символов дискретно, сложность времени среднего случая может быть уменьшена.Взгляните на оптимизацию Укконена для вычисления расстояний редактирования и ее обобщений .Также взгляните на методы, основанные на сжатии , это также основано на работе Укконена.