動态規劃 維特比 viterbi python實作

**

動态規劃

**

最近在做關于拼音糾錯的項目, 需要用到大量算分的步驟,笛卡爾積是在太慢, 在網上查一下,維特比比較好用, 于是找一找搜一搜原理

看到了這個仁兄的https://blog.csdn.net/athemeroy/article/details/79339546

于是動手寫個python 實作

def viterbi(data, get_score, big=True):
    def most(some):
        if big:
            return max(some)
        else:
            return min(some)
    short_data = []
    for left_index, right_index in enumerate(range(1, len(data))):
        before = data[left_index]
        after = data[right_index]
        if left_index == 0:
            for before_one in before:
                for after_one in after:
                    k = before_one + '_' + after_one
                    short_data.append((get_score(k), after_one, [before_one, after_one]))
        else:
            temp_data = []
            for after_one in after:
                temp_short_data = []
                for before_one in short_data:
                    k = before_one[1] + '_' + after_one
                    temp_short_data.append((before_one[0] + get_score(k), after_one, before_one[2] + [after_one]))
                temp_data.append(most(temp_short_data))
            short_data = temp_data
    return max(short_data)[2]


if __name__ == '__main__':
    data = [
        ['a'],
        ['b1', 'b2', 'b3'],
        ['c1', 'c2', 'c3'],
        ['d1', 'd2', 'd3'],
        ['e'],
    ]


    def get_score(k):
        try:
            relation_score = {
                'a_b1': 6, 'a_b2': 7, 'a_b3': 5, 'b1_c1': 5, 'b1_c2': 6, 'b1_c3': 9,
                'b2_c1': 4, 'b2_c2': 3, 'b2_c3': 7, 'b3_c1': 4, 'b3_c2': 6, 'b3_c3': 6, 'c1_d1': 7, 'c1_d2': 8, 'c1_d3': 3,
                'c2_d1': 5, 'c2_d2': 4, 'c2_d3': 3, 'c3_d1': 5, 'c3_d2': 7, 'c3_d3': 6, 'd1_e': 4, 'd2_e': 8, 'd3_e': 5, }
            score = relation_score[k]
        except:
            score = 0
        return score

    print(viterbi(data=data, get_score=get_score, big=False))

           

參數名還算清楚,

get_score函數可以自己改動成其他的擷取方式

big=True就是最大路徑,False就是最小路徑

資料就是按照我上面那個連結裡的仁兄的資料寫的

本來想把實作附在他的評論區得,可是由于字數限制, 就自己發一篇吧

請各位跑過去點贊~