62
правки
Изменения
Нет описания правки
== Псевдокод ==
Функция возвращает вектор <codetex> //функция возвращает вектор {X {{---}} </tex> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. '''viterbi'''(O, S, <tex> \pi </tex>, Y, A, B): '''for''' i = 1..'''to''' K TState[i, 1] = <tex> \pi </tex>[i] * B[i, Y[1]] TIndex[i, 1] = 0 '''for''' i = 2..'''to''' T '''for''' j = 1..'''to''' K
TState[j, i] = <tex> \max_{1 \leqslant k\leqslant K} \limits </tex>(TState[k, i - 1] * A[k, j] * B[j, Y[i]])
TIndex[j, i] = <tex> \arg\max_{1 \leqslant k\leqslant K} \limits </tex>(TState[k, i - 1] * A[k, j] * B[j, Y[i]])
''<font color=green>//функция arg max() ищет максимум выражения в скобках и возвращает аргумент (в нашем случае <tex>k</tex>), при котором достигается этот максимум.</font>'' X[T] = <tex> \arg\max_{1 \leqslant k\leqslant K} \limits </tex>(TState[k, T]) '''for''' i = T '''downto''' 2 X[i - 1] = TIndex[X[i], i] '''return''' X</code>
Таким образом, алгоритму требуется <tex> O(T\times\left|{K}\right|^2)</tex> времени.
