== Псевдокод ==
/* fwd = {}, bkw -- матрицы размера |S|*T, которым во время работы присваиваются промежуточные результаты alpha и beta */ bkw = {} '''for ''' s '''in ''' S: fwd[s, 1] = emit_probability[s][observations[1]] * П[s] bkw[s, len(observations) - 1] = 1 '''function''' alpha(s, t): '''if ''' (s, t) '''in ''' fwd: '''return ''' fwd[s, t] f = 0 '''for ''' j '''in ''' S: f += alpha(j, t-1) * transition_probability[j][s] f *= emit_probability[s][observations[t]] fwd[s, t] = f '''return ''' fwd[s, t] '''function''' beta(s, t): '''if ''' (s, t) '''in ''' bkw: '''return ''' bkw[s, t] b = 0 '''for ''' j '''in ''' S: b += beta(j, t+1) * transition_probability[s][j] * emit_probability[j][O[t+1]] bkw[s, t] = b '''return ''' bkw[s, t] '''function''' forward_backward(s, t): probabilities = {} chain_probability = 0 '''for ''' j '''in ''' S: chain_probability += alpha(j, t)*beta(j, t) return '''for''' s '''in''' S '''for''' t '''in''' [1, T] probabilities[s, t] = (alpha(s, t)*beta(s, t)) / chain_probability '''return''' probabilities
