1. transition_probability

state H L end
start 0.6 0.4 0.0
H 0.4 0.4 0.2
L 0.2 0.5 0.3

2. emission_probability

A C G T
H 0.2 0.3 0.3 0.3
L 0.3 0.2 0.2 0.3

对概率取以2为底的对数

state H L end
start -0.74 -1.32
H -1.32 -1.32 -2.32
L -2.32 -1 -1.74
A C G T
H -2.32 -1.74 -1.74 -2.32
L -1.74 -2.32 -2.32 -1.74 
# Function: Viterbi algorithm

# 状态的样本空间
import math
state_set = ('H', 'L')

# 观测的样本空间
observation_set = ('A', 'G', 'C', 'T',)

# 起始的状态概率
start_probability = {'H': 0.6, 'L': 0.4, }

# 状态转移概率矩阵
transition_probability = {
    'H': {'H': 0.4, 'L': 0.4, },
    'L': {'H': 0.2, 'L': 0.5, },
}

# 状态->观测的发射概率矩阵B
emission_probability = {
    'H': {'A': 0.2, 'G': 0.3, 'C': 0.3, 'T': 0.2},
    'L': {'A': 0.3, 'G': 0.2, 'C': 0.2, 'T': 0.3},
}

# 观测结果
observation_seq = ['G', 'C', 'A', 'C', 'T', 'G']


def viterbi(observation_seq, state_set, start_prob, trans_prob, emit_prob):
    # 初始化
    V = [{}]
    path = {}

    # 初始化初始状态
    for state in state_set:
        start_log_prob = math.log2(start_prob[state])
        emit_log_prob = math.log2(emit_prob[state][observation_seq[0]])
        V[0][state] = start_log_prob + emit_log_prob
        path[state] = [state]

    # 动态规划过程
    for t in range(1, len(observation_seq)):
        V.append({})
        new_path = {}

        for current_state in state_set:
            max_transition_prob = float('-inf')
            prev_state_selected = None

            for prev_state in state_set:
                transition_log_prob = math.log2(
                    trans_prob[prev_state][current_state])
                prev_state_prob = V[t - 1][prev_state]
                current_prob = prev_state_prob + transition_log_prob

                if current_prob > max_transition_prob:
                    max_transition_prob = current_prob
                    prev_state_selected = prev_state

            emit_log_prob = math.log2(
                emit_prob[current_state][observation_seq[t]])
            V[t][current_state] = max_transition_prob + emit_log_prob
            new_path[current_state] = path[prev_state_selected] + \
                [current_state]

            # 打印每一次计算的结果
            print(f"时刻 {t}, 状态 {current_state}: {V[t][current_state]}")

        path = new_path

    # 找到最终路径
    max_prob = float('-inf')
    final_state_selected = None

    for final_state in state_set:
        final_prob = V[len(observation_seq) - 1][final_state]

        if final_prob > max_prob:
            max_prob = final_prob
            final_state_selected = final_state

    return max_prob, path[final_state_selected]


# 调用函数
probability, path = viterbi(observation_seq, state_set,
                            start_probability, transition_probability, emission_probability)

# 打印结果
print("\n最大概率:", probability)
print("最可能的隐藏状态序列:", path)

最大概率: -17.972540350380477
最可能的隐藏状态序列: [‘H’, ‘H’, ‘L’, ‘L’, ‘L’, ‘L’]