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