软件工程应用与实践课程jieba分词小组—

2021SC@SDUSC

接上篇，继续对posseg中的词性标注部分代码进行分析。

viterbi函数是在jieba/posseg/viterbi.py文件中实现。viterbi函数接受的参数情况：

①obs是观测序列，也即待标注的句子。

②states是每个词可能的状态，在jieba/posseg/char_state_tab.py文件中定义，格式如代码段所示，表示字“\u4e00”可能的状态包括“B”表明位于词的开始位置，“m”表示词性为为数词等等状态。

P={'\u4e00': (('B', 'm'),
             ('S', 'm'),
             ('B', 'd'),
             ('B', 'a'),
             ('M', 'm'),
             ('B', 'n'),
            ······
}

③start_p，是初始状态，在jieba/posseg/prob_start.py文件中定义，格式如下代码段所示，表示“B”表明位于词的开始位置，“a”表示为形容词，其对数概率为-4.762305214596967等等状态。

P={('B', 'a'): -4.762305214596967,
 ('B', 'ad'): -6.680066036784177,
 ('B', 'ag'): -3.14e+100,
 ('B', 'an'): -8.697083223018778,
 ('B', 'b'): -5.018374362109218,
 ······
}

④trans_p，是状态转移概率，在jieba/posseg/prob_trans.py文件中定义中定义，格式如代码段所示，表示前一时刻的状态为（“B”和“a”），也即前一个字为词的开始位置，词性为形容词，当前时刻的状态为（“E”和“a”），也即当前字位于词的末尾位置，词性为形容词，它的状态转移概率的对数值为-0.0050648453069648755等等状态。

P={('B', 'a'): {('E', 'a'): -0.0050648453069648755,
              ('M', 'a'): -5.287963037107507},
 ('B', 'ad'): {('E', 'ad'): -0.0007479013978476627,
               ('M', 'ad'): -7.198613337130562},
 ······
}

⑤emit_p，是状态发射概率，在jieba/posseg/prob_emit.py文件中定义中定义，格式如代码段所示，表示当前状态为（“B”和“a”），也即当前字位于词的开始位置，词性为形容词，到汉字“\u4e00”的发射概率的对数值为-3.618715666782108等等。

P={('B', 'a'): {'\u4e00': -3.618715666782108,
              '\u4e07': -10.500566885381515,
              '\u4e0a': -8.541143017159477,
              '\u4e0b': -8.445222895280738,
······
}

viterbi函数会先计算各个初始状态的对数概率值，然后递推计算，依次获取前一时刻所有的状态集合；根据前一时刻的状态和状态转移矩阵，提前计算当前时刻的状态集合，再根据当前的观察值获得当前时刻的可能状态集合，再与上一步骤计算的状态集合取交集；根据每时刻当前所处的状态，其对数概率值取决于上一时刻的对数概率值、上一时刻的状态到这一时刻的状态的转移概率、这一时刻状态转移到当前的字的发射概率三部分组成。最后再根据最大概率路径依次回溯，得到最优的路径，也即为要求的各个时刻的状态。

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]  # tabular
    mem_path = [{}]
    # 根据状态转移矩阵，获取所有可能的状态
    all_states = trans_p.keys()
    # 时刻t=0，初始状态
    for y in states.get(obs[0], all_states):  # init
        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
        mem_path[0][y] = ''
    # 时刻t=1,...,len(obs) - 1
    for t in xrange(1, len(obs)):
        V.append({})
        mem_path.append({})
        #prev_states = get_top_states(V[t-1])
        # 获取前一时刻所有的状态集合
        prev_states = [
            x for x in mem_path[t - 1].keys() if len(trans_p[x]) > 0]

       # 根据前一时刻的状态和状态转移矩阵，提前计算当前时刻的状态集合
        prev_states_expect_next = set(
            (y for x in prev_states for y in trans_p[x].keys()))

        # 根据当前的观察值获得当前时刻的可能状态集合，再与上一步骤计算的状态集合取交集
        obs_states = set(
            states.get(obs[t], all_states)) & prev_states_expect_next

        # 如果当前状态的交集集合为空
        if not obs_states:
            # 如果提前计算当前时刻的状态集合不为空，则当前时刻的状态集合为提前计算当前时刻的状态集合，否则为全部可能的状态集合
            obs_states = prev_states_expect_next if prev_states_expect_next else all_states

        # 当前时刻所处的各种可能的状态集合
        for y in obs_states:
            # 分别获取上一时刻的状态的概率对数，该状态到本时刻的状态的转移概率对数，本时刻的状态的发射概率对数
            # prev_states是当前时刻的状态所对应上一时刻可能的状态集合
            prob, state = max((V[t - 1][y0] + trans_p[y0].get(y, MIN_INF) +
                               emit_p[y].get(obs[t], MIN_FLOAT), y0) for y0 in prev_states)
            V[t][y] = prob
            mem_path[t][y] = state

    # 最后一个时刻
    last = [(V[-1][y], y) for y in mem_path[-1].keys()]
    # if len(last)==0:
    #     print obs
    prob, state = max(last)

    # 从时刻t = len(obs) - 1,...,0，依次将最大概率对应的状态保存在列表中
    route = [None] * len(obs)
    i = len(obs) - 1
    while i >= 0:
        route[i] = state
        state = mem_path[i][state]
        i -= 1
    # 返回最大概率及各个时刻的状态
    return (prob, route)

软件工程应用与实践课程jieba分词小组——⑬代码分析