Алгоритм Витерби

Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.

Является алгоритмом динамического программирования. Применяется в алгоритме свёрточного декодирования Витерби.

Алгоритм делает несколько предположений:

• наблюдаемые и скрытые события должны быть последовательностью. Последовательность чаще всего упорядочена по времени.
• две последовательности должны быть выровнены: каждое наблюдаемое событие должно соответствовать ровно одному скрытому событию
• вычисление наиболее вероятной скрытой последовательности до момента t должно зависеть только от наблюдаемого события в момент времени t, и наиболее вероятной последовательности до момента t − 1.

Ссылки

• The Viterbi Algorithm: A Personal History. G. David Forney Jr; Viterbi Conference, University of Southern California, Los Angeles, March 8, 2005