二阶HMM词性标注

def good_turing(counts):
    N = sum(counts)  # 总的出现次数
    prob = [0] * len(counts)
    
    if N == 0:
        return prob
        
    Nr = [0] * (max(counts) + 1) # 出现r次的词个数
    for r in counts:
        Nr[r] += 1
        
    smooth_boundary = min(len(Nr)-1, 8)  # 使用good-turing方法进行平滑
    for r in range(smooth_boundary):
        if Nr[r] != 0 and Nr[r+1] != 0:
            Nr[r] = (r+1) * Nr[r+1] / Nr[r]
        else:
            Nr[r] = r
    for r in range(smooth_boundary, len(Nr)):
        Nr[r] = r
        
    for i in range(len(counts)):
        prob[i] = Nr[counts[i]]
    total = sum(prob)
    return [p/total for p in prob]  # 归一化输出

def viterbi(self, sent):
        n = len(sent)
        nt = self.ntags
        y = [None] * n
        path = [[[0]*nt for i in range(nt)] for j in range(n-1)]
        val = [[[0]*nt for i in range(nt)] for j in range(n-1)]
        
        # 如果句子只有一个单词，则单独处理
        if (n == 1):
            max_val = -100000
            for v in range(nt):
                tmp = self.tr_prob[nt][nt][v] * self.em_prob[v][self.word2num[sent[0]]] * self.tr_prob[nt][v][nt]
                if tmp > max_val:
                    max_val = tmp
                    y[0] = v
            return [self.num2tag[y[0]]]
        
        # 句子开头
        for u in range(nt):
            for v in range(nt):
                val[0][u][v] = self.tr_prob[nt][nt][u] * self.em_prob[u][self.word2num[sent[0]]] * \
                    self.tr_prob[nt][u][v] * self.em_prob[v][self.word2num[sent[1]]]
                path[0][u][v] = -1
        # 动态规划求解
        for k in range(1, n-1):
            for u in range(nt):
                for v in range(nt):
                    max_val = -100000
                    best_tag = -1
                    for w in range(nt):
                        tmp = val[k-1][w][u] * self.tr_prob[w][u][v] * self.em_prob[v][self.word2num[sent[k+1]]]
                        if tmp > max_val:
                            max_val = tmp
                            best_tag = w
                    val[k][u][v] = max_val
                    path[k][u][v] = best_tag
        # 结尾
        max_val = -100000
        for u in range(nt):
            for v in range(nt):
                tmp = val[n-2][u][v] * self.tr_prob[u][v][nt]
                if tmp > max_val:
                    max_val = tmp
                    y[-1] = v; y[-2] = u
                    
        # 找到最佳标注
        for k in range(n-3, -1, -1):
            y[k] = path[k+1][y[k+1]][y[k+2]]
            
        return [self.num2tag[t] for t in y]