NLP-基础任务-中文分词算法(2)-基于词典：基于N-gram语言模型的分词算法【基于词典的分词方法】【利用维特比算法求解最优路径】【比机械分词精度高】【OOV：基于现有词典，不能进行新词发现处理】

秒速五厘米 2023-10-01 20:39 0阅读 0赞

例子：“经常有意见分歧”

词典：["经常","有","意见","意","见","有意见","分歧","分","歧"]
    概率P(x)：{"经常":0.08,"有":0.04,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.002,"分歧":0.04,"分":0.02, "歧":0.005}

概率P(x)代表的是该词x在我们日常生活所见的文本中出现的概率。

step1：根据词典，利用“前向最大匹配算法/后向最大匹配算法”找出所有可能的分词情况，如下：

*  经常 / 有意见 / 分歧
 *  经常 / 有意见 / 分 / 歧
 *  经常 / 有 / 意见 / 分歧
 *  经常 / 有 / 意见 / 分 / 歧

step2：将所有通过最大匹配算法生成的所有分词组合方式通过“语言模型”来计算概率，概率越大的分词方式越好。例如第一个情况的概率为：

P ( 经 常 , 有 意 见 , 分 歧 ) = P ( 经 常 ) ∗ P ( 有 意 见 ) ∗ P ( 分 歧 ) = 0.08 ∗ 0.02 ∗ 0.04 = 0.000064 P(经常,有意见,分歧)=P(经常)∗P(有意见)∗P(分歧)=0.08∗0.02∗0.04=0.000064 P(经常,有意见,分歧)=P(经常)∗P(有意见)∗P(分歧)=0.08∗0.02∗0.04=0.000064

我们考虑到这样算的话值会很小，很容易造成内存溢出，所以引入 − l n −ln −ln 来计算，也就是由算  P ( x ) P(x) P(x) 的最大值变为算  − l n ( P ( x ) ) -ln(P(x)) −ln(P(x)) 的最小值，

-ln(P(x))：{"经常":2.52,"有":3.21,"意见":2.52,"意":4.6,"见":5.29,"有意见":6.21,"分歧":3.21,"分":3.9, "歧":5.29}

− l n \[ P ( 经 常 , 有 意 见 , 分 歧 ) \] = − l n \[ P ( 经 常 ) ∗ P ( 有 意 见 ) ∗ P ( 分 歧 ) \] = − l n ( P ( 经 常 ) − l n ( 有 意 见 ) − l n ( 分 歧 ) = 2.52 + 6.21 + 3.21 = 11.94 \\begin\{aligned\} −ln\[P(经常,有意见,分歧)\]&=−ln\[P(经常)∗P(有意见)∗P(分歧)\]\\\\ &=−ln(P(经常)−ln(有意见)−ln(分歧)\\\\ &=2.52+6.21+3.21=11.94 \\end\{aligned\} −ln\[P(经常,有意见,分歧)\]=−ln\[P(经常)∗P(有意见)∗P(分歧)\]=−ln(P(经常)−ln(有意见)−ln(分歧)=2.52\+6.21\+3.21=11.94

但是这两步下来时间复杂度太高，并不可取。怎么能够优化一下呢？就是接下来的维特比算法

**维特比算法**（Viterbi Algorithm）本质上还是动态规划（Dynamic Programming）

例子：“经常有意见分歧”

我们仍然是有以下几个数据：

词典：["经常","有","意见","意","见","有意见","分歧","分","歧"]
    概率P(x)：{"经常":0.08,"有":0.04,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.002,"分歧":0.04,"分":0.02, "歧":0.005}
    -ln(P(x))：{"经常":2.52,"有":3.21,"意见":2.52,"意":4.6,"见":5.29,"有意见":6.21,"分歧":3.21,"分":3.9, "歧":5.29}

如果某个词不在字典中，我们将认为其  − l n \[ P ( x ) \] −ln\[P(x)\] −ln\[P(x)\] 值为20。

我们构建以下的DAG(有向图），每一个边代表一个词，我们将  − l n \[ P ( x ) \] -ln\[P(x)\] −ln\[P(x)\]的值标到边上，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]

求  − l n \[ P ( x ) \] −ln\[P(x)\] −ln\[P(x)\] 的最小值问题，就转变为求最短路径的问题。

由图可以看出，路径 0—>②—>③—>⑤—>⑦ 所求的值最小，所以其就是最优结果：经常 / 有 / 意见 / 分歧

那么我们应该怎样快速计算出来这个结果呢？

**逆向分析：**

*  我们设  f ( n ) f(n) f(n) 代表从起点  0 0 0 到结点  n n n 的最短路径的值，所以我们想求的就是  f ( 7 ) f(7) f(7)，从DAG图中可以看到，到结点⑦有2条路径：
    
     *  从结点⑤—>结点⑦： f ( 7 ) = f ( 5 ) + 3.21 f(7)=f(5)+3.21 f(7)=f(5)\+3.21
     *  从结点⑥—>结点⑦： f ( 7 ) = f ( 6 ) + 5.29 f(7)=f(6)+5.29 f(7)=f(6)\+5.29
 *  我们应该从2条路径中选择路径短的。
 *  在上面的第1条路径中， f ( 5 ) f(5) f(5) 还是未知的，我们要  f ( 5 ) f(5) f(5)，同理我们发现到结点⑤的路径有3条路径：
    
     *  从结点②—>结点⑤： f ( 5 ) = f ( 2 ) + 6.21 f(5)=f(2)+6.21 f(5)=f(2)\+6.21
     *  从结点③—>结点⑤： f ( 5 ) = f ( 3 ) + 2.52 f(5)=f(3)+2.52 f(5)=f(3)\+2.52
     *  从结点④—>结点⑤： f ( 5 ) = f ( 4 ) + 20 f(5)=f(4)+20 f(5)=f(4)\+20
 *  我们同样从3条路径中选择路径短的。以此类推，直到结点0，所有的路径值都可以算出来。

**正向分析**：和篱笆网络思想一致：**每个节点（ N o d e i Node\_i Nodei）都只保留到达该节点  N o d e i Node\_i Nodei 的所有路径中最短的那条路径**（维特比算法：每个节点  N o d e i Node\_i Nodei 都保留其来时最优路径）：

*  到达  N o d e 1 Node\_1 Node1 的路径有1条：
    
     *  0->①， s c o r e = 20 score=20 score=20，保留；
 *  到达  N o d e 2 Node\_2 Node2 的路径有2条：
    
     *  ①->②， s c o r e = 20 + 20 = 40 score=20+20=40 score=20\+20=40，删除；
     *  0->②， s c o r e = 2.52 score=2.52 score=2.52，保留；
 *  到达  N o d e 3 Node\_3 Node3 的路径有1条：
    
     *  ②->③， s c o r e = 2.52 + 3.21 = 5.73 score=2.52+3.21=5.73 score=2.52\+3.21=5.73，保留；
 *  到达  N o d e 4 Node\_4 Node4 的路径有1条：
    
     *  ③->④， s c o r e = 5.73 + 20 = 25.73 score=5.73+20=25.73 score=5.73\+20=25.73，保留；
 *  到达  N o d e 5 Node\_5 Node5 的路径有3条：
    
     *  ②->⑤， s c o r e = 2.52 + 6.21 = 8.73 score=2.52+6.21=8.73 score=2.52\+6.21=8.73，删除；
     *  ③->⑤， s c o r e = 5.73 + 2.52 = 8.25 score=5.73+2.52=8.25 score=5.73\+2.52=8.25，保留；
     *  ④->⑤， s c o r e = 25.73 + 20 = 45.73 score=25.73+20=45.73 score=25.73\+20=45.73，删除；
 *  到达  N o d e 6 Node\_6 Node6 的路径有1条：
    
     *  ⑤->⑥， s c o r e = 8.25 + 3.9 = 12.15 score=8.25+3.9=12.15 score=8.25\+3.9=12.15，保留；
 *  到达  N o d e 7 Node\_7 Node7 的路径有2条：
    
     *  ⑤->⑦， s c o r e = 8.25 + 3.21 = 11.46 score=8.25+3.21=11.46 score=8.25\+3.21=11.46，保留；
     *  ⑥->⑦， s c o r e = 12.15 + 5.29 = 17.44 score=12.15+5.29=17.44 score=12.15\+5.29=17.44，删除；

我们维护一个列表来表示  f ( n ) f(n) f(n) 的各值：

<table> 
 <thead> 
  <tr> 
   <th>结点</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>f(n)</td> 
   <td>20</td> 
   <td>2.52</td> 
   <td>5.73</td> 
   <td>25.73</td> 
   <td>8.25</td> 
   <td>12.15</td> 
   <td>11.46</td> 
  </tr> 
  <tr> 
   <td>结点的上一个结点</td> 
   <td>0</td> 
   <td>0</td> 
   <td>②</td> 
   <td>③</td> 
   <td>③</td> 
   <td>⑤</td> 
   <td>⑤</td> 
  </tr> 
 </tbody> 
</table>

第2行代表从起点0到该结点的最短路径的值，第3行代表在最短路径中的该节点的上一个结点。

通过表，我们可以找到结点⑦的上一个结点⑤，结点⑤的上一个结点③，结点③的上一个结点②，结点②的上一个结点0，即路径：0—>②—>③—>⑤—>⑦

# -*- coding: utf-8 -*-
    import math
    import collections
    
    
    # 维特比算法(viterbi)
    def word_segmentation(text):
        ####################################################################################################################################################################
        word_dictionaries = ["经常", "有", "意见", "意", "见", "有意见", "分歧", "分", "歧"]
        probability = {
        "经常": 0.08, "有": 0.04, "意见": 0.08, "意": 0.01, "见": 0.005, "有意见": 0.002, "分歧": 0.04, "分": 0.02, "歧": 0.005}
        probability_ln = {
        key: -math.log(probability[key]) for key in probability}
        # probability_ln = {'经常': 2.5257286443082556, '有': 3.2188758248682006, '意见': 2.5257286443082556, '意': 4.605170185988091, '见': 5.298317366548036, '有意见': 6.214608098422191, '分歧': 3.2188758248682006, '分': 3.912023005428146, '歧': 5.298317366548036}
        print("probability_ln = {0}".format(probability_ln))
        # 构造图的代码并没有实现，以下只是手工建立的图【如果某个词不在字典中，我们将认为其 −ln[P(x)] 值为20。】，为了说明 维特比算法
        ####################################################################################################################################################################
        # 有向五环图，存储的格式：key是结点名，value是一个结点的所有上一个结点（以及边上的权重）
        graph = {
        
            0: {
        0: (0, "")},
            1: {
        0: (20, "经")},
            2: {
        0: (2.52, "经常"), 1: (20, "常")},
            3: {
        2: (3.21, "有")},
            4: {
        3: (20, "意")},
            5: {
        2: (6.21, "有意见"), 3: (2.52, "意见"), 4: (5.30, "见")},
            6: {
        5: (3.9, "分")},
            7: {
        5: (3.21, "分歧"), 6: (5.29, "歧")}
        }
        # =====================================================================利用“维特比算法”构建各个节点的最优路径：开始=====================================================================
        print("#"*50, "利用“维特比算法”构建各个节点的最优路径：开始", "#"*50)
        f = collections.OrderedDict()  # 保存结点n的f(n)以及实现f(n)的上一个结点【f(n)：代表从起点 0 到结点 n 的最短路径的值】
        for key, value in graph.items():  # 遍历有向图graph中的所有节点
            print("\nkey = {0}----value = {1}".format(key, value))
            tuple_temp_list = []
            for pre_node_key, pre_node_value in value.items():  # 遍历当前节点的所有上一个节点【pre_node_key：上一个节点的节点号，pre_node_value：本节点距离上一个节点的距离】
                # print("本节点的节点号：key = {0}----上一个节点的节点号：pre_node_key = {1}----本节点距离上一个节点的距离：pre_node_value = {2}".format(key, pre_node_key, pre_node_value))
                distance_from_0 = 0
                if pre_node_key not in f:  # 当遍历到0节点时，该节点的上一个结点还没有计算f(n)；
                    distance_from_0 = pre_node_value[0]  # 0节点的上一节点（依旧时0节点）的距离
                else:  # 当遍历到0节点之后的节点
                    distance_from_0 = pre_node_value[0] + f[pre_node_key][0]  # pre_node_value[0]：当前节点距离上一节点的距离；f[pre_node_key][0]：当前节点的上一节点“pre_node_key”距离0节点的最短距离
                    print("本节点的节点号：key = {0}----本节点可触及的上一节点号：pre_node_key = {1}----本节点距离上一个节点“节点{1}”的距离：pre_node_value = {2}----上一节点“节点{1}”距离0节点的最短距离：f[pre_node_key][0] = {3}----本节点路径上一节点“节点{1}”距离0节点的距离：distance_from_0 = {4}".format(key, pre_node_key, pre_node_value, f[pre_node_key][0], distance_from_0))
                tuple_temp = (distance_from_0, pre_node_key)  # 【pre_node_value[0]：本节点距离0节点的最短距离；pre_node_key：本节点实现距离0节点距离最短时的上一个节点的节点号】
                tuple_temp_list.append(tuple_temp)
            min_temp = min(tuple_temp_list)  # 比较比较当前节点路径所触及的所有上一节点到达0节点的距离，得出当前节点 key 距离0节点的最短距离
            # min_temp = min((pre_node_value[0], pre_node_key) if pre_node_key not in f else (pre_node_value[0] + f[pre_node_key][0], pre_node_key) for pre_node_key, pre_node_value in value.items())  # 高阶写法
            print("本节点的节点号：key = {0}----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = {1}----当前节点 key 距离0节点的最短距离：min_temp = {2}".format(key, tuple_temp_list, min_temp))
            f[key] = min_temp
            print("将当前节点{0}距离0节点的（最短距离,路径的节点号）= ({0},{1}) 加入f---->f = {2}".format(key, min_temp, f))  # f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2)), (4, (25.73, 3)), (5, (8.25, 3)), (6, (12.15, 5)), (7, (11.46, 5))])
        print("#" * 50, "利用“维特比算法”构建各个节点的最优路径：结束", "#" * 50)
        # =====================================================================利用“维特比算法”构建各个节点的最优路径：结束=====================================================================
    
        # =====================================================================提取最优最优路径：开始=====================================================================
        print("\n", "#" * 50, "提取最优路径：开始", "#" * 50)
        last = next(reversed(f))  # 最后一个结点7
        first = next(iter(f))  # 第一个结点0
        path_result = [last, ]  # 保存路径，最后一个结点先添入
        pre_last = f[last]  # 最后一个结点的所有前一个结点
        print("最后一个结点7：last = {0}----第一个结点0：first = {1}----初始化最优路径：path_result = {2}----最后一个结点的所有前一个结点：pre_last = {3}".format(last, first, path_result, pre_last))
    
        while pre_last[1] is not first:  # 没到达第一个结点就一直循环，查找上一个节点的上一个节点号
            path_result.append(pre_last[1])  # 加入一个路径结点X
            pre_last = f[pre_last[1]]  # 定位到路径结点X的上一个结点
        path_result.append(first)  # 第一个结点添入
        print("最优路径：path_result = {0}".format(path_result))  # 结果：[7, 5, 3, 2, 0]
        print("#" * 50, "提取最优路径：结束", "#" * 50)
        # =====================================================================提取最优最优路径：结束=====================================================================
    
        # =====================================================================通过最优路径得到分词结果：开始=====================================================================
        print("\n", "#" * 50, "通过最优路径得到分词结果：开始", "#" * 50)
        text_result = []
        for index, num in enumerate(path_result):  # 找到路径上边的词
            if index + 1 == len(path_result):
                break
            word = graph[num][path_result[index + 1]][1]
            print("最优路径：path_result = {0}----index = {1}----当前节点号：num = {2}----在最优路径里，当前节点号的上一个节点号：path_result[index + 1] = {3}----当前节点号{2}与上一节点号{3}之间的词汇：{4}".format(path_result, index, num, path_result[index + 1], word))
            text_result.append(word)
        print("text_result = {0}".format(text_result))
        text_result.reverse()  # 翻转一下
        print("翻转后：text_result = {0}".format(text_result))
        print("#" * 50, "通过最优路径得到分词结果：结束", "#" * 50)
        return "".join(word + "/" for word in text_result)
        # =====================================================================通过最优路径得到分词结果：结束=====================================================================
    
    
    if __name__ == '__main__':
        content = "经常有意见分歧"
        word_segmentation_result = word_segmentation(content)
        print("word_segmentation_result:", word_segmentation_result)

打印结果：

probability_ln = {
        '经常': 2.5257286443082556, '有': 3.2188758248682006, '意见': 2.5257286443082556, '意': 4.605170185988091, '见': 5.298317366548036, '有意见': 6.214608098422191, '分歧': 3.2188758248682006, '分': 3.912023005428146, '歧': 5.298317366548036}
    ################################################## 利用“维特比算法”构建各个节点的最优路径：开始 ##################################################
    key = 0----value = {
        0: (0, '')}
    本节点的节点号：key = 0----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(0, 0)]----当前节点 key 距离0节点的最短距离：min_temp = (0, 0)
    将当前节点0距离0节点的（最短距离,路径的节点号）= (0,(0, 0)) 加入f---->f = OrderedDict([(0, (0, 0))])
    
    key = 1----value = {
        0: (20, '经')}
    本节点的节点号：key = 1----本节点可触及的上一节点号：pre_node_key = 0----本节点距离上一个节点“节点0”的距离：pre_node_value = (20, '经')----上一节点“节点0”距离0节点的最短距离：f[pre_node_key][0] = 0----本节点路径上一节点“节点0”距离0节点的距离：distance_from_0 = 20
    本节点的节点号：key = 1----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(20, 0)]----当前节点 key 距离0节点的最短距离：min_temp = (20, 0)
    将当前节点1距离0节点的（最短距离,路径的节点号）= (1,(20, 0)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0))])
    
    key = 2----value = {
        0: (2.52, '经常'), 1: (20, '常')}
    本节点的节点号：key = 2----本节点可触及的上一节点号：pre_node_key = 0----本节点距离上一个节点“节点0”的距离：pre_node_value = (2.52, '经常')----上一节点“节点0”距离0节点的最短距离：f[pre_node_key][0] = 0----本节点路径上一节点“节点0”距离0节点的距离：distance_from_0 = 2.52
    本节点的节点号：key = 2----本节点可触及的上一节点号：pre_node_key = 1----本节点距离上一个节点“节点1”的距离：pre_node_value = (20, '常')----上一节点“节点1”距离0节点的最短距离：f[pre_node_key][0] = 20----本节点路径上一节点“节点1”距离0节点的距离：distance_from_0 = 40
    本节点的节点号：key = 2----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(2.52, 0), (40, 1)]----当前节点 key 距离0节点的最短距离：min_temp = (2.52, 0)
    将当前节点2距离0节点的（最短距离,路径的节点号）= (2,(2.52, 0)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0))])
    
    key = 3----value = {
        2: (3.21, '有')}
    本节点的节点号：key = 3----本节点可触及的上一节点号：pre_node_key = 2----本节点距离上一个节点“节点2”的距离：pre_node_value = (3.21, '有')----上一节点“节点2”距离0节点的最短距离：f[pre_node_key][0] = 2.52----本节点路径上一节点“节点2”距离0节点的距离：distance_from_0 = 5.73
    本节点的节点号：key = 3----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(5.73, 2)]----当前节点 key 距离0节点的最短距离：min_temp = (5.73, 2)
    将当前节点3距离0节点的（最短距离,路径的节点号）= (3,(5.73, 2)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2))])
    
    key = 4----value = {
        3: (20, '意')}
    本节点的节点号：key = 4----本节点可触及的上一节点号：pre_node_key = 3----本节点距离上一个节点“节点3”的距离：pre_node_value = (20, '意')----上一节点“节点3”距离0节点的最短距离：f[pre_node_key][0] = 5.73----本节点路径上一节点“节点3”距离0节点的距离：distance_from_0 = 25.73
    本节点的节点号：key = 4----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(25.73, 3)]----当前节点 key 距离0节点的最短距离：min_temp = (25.73, 3)
    将当前节点4距离0节点的（最短距离,路径的节点号）= (4,(25.73, 3)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2)), (4, (25.73, 3))])
    
    key = 5----value = {
        2: (6.21, '有意见'), 3: (2.52, '意见'), 4: (5.3, '见')}
    本节点的节点号：key = 5----本节点可触及的上一节点号：pre_node_key = 2----本节点距离上一个节点“节点2”的距离：pre_node_value = (6.21, '有意见')----上一节点“节点2”距离0节点的最短距离：f[pre_node_key][0] = 2.52----本节点路径上一节点“节点2”距离0节点的距离：distance_from_0 = 8.73
    本节点的节点号：key = 5----本节点可触及的上一节点号：pre_node_key = 3----本节点距离上一个节点“节点3”的距离：pre_node_value = (2.52, '意见')----上一节点“节点3”距离0节点的最短距离：f[pre_node_key][0] = 5.73----本节点路径上一节点“节点3”距离0节点的距离：distance_from_0 = 8.25
    本节点的节点号：key = 5----本节点可触及的上一节点号：pre_node_key = 4----本节点距离上一个节点“节点4”的距离：pre_node_value = (5.3, '见')----上一节点“节点4”距离0节点的最短距离：f[pre_node_key][0] = 25.73----本节点路径上一节点“节点4”距离0节点的距离：distance_from_0 = 31.03
    本节点的节点号：key = 5----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(8.73, 2), (8.25, 3), (31.03, 4)]----当前节点 key 距离0节点的最短距离：min_temp = (8.25, 3)
    将当前节点5距离0节点的（最短距离,路径的节点号）= (5,(8.25, 3)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2)), (4, (25.73, 3)), (5, (8.25, 3))])
    
    key = 6----value = {
        5: (3.9, '分')}
    本节点的节点号：key = 6----本节点可触及的上一节点号：pre_node_key = 5----本节点距离上一个节点“节点5”的距离：pre_node_value = (3.9, '分')----上一节点“节点5”距离0节点的最短距离：f[pre_node_key][0] = 8.25----本节点路径上一节点“节点5”距离0节点的距离：distance_from_0 = 12.15
    本节点的节点号：key = 6----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(12.15, 5)]----当前节点 key 距离0节点的最短距离：min_temp = (12.15, 5)
    将当前节点6距离0节点的（最短距离,路径的节点号）= (6,(12.15, 5)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2)), (4, (25.73, 3)), (5, (8.25, 3)), (6, (12.15, 5))])
    
    key = 7----value = {
        5: (3.21, '分歧'), 6: (5.29, '歧')}
    本节点的节点号：key = 7----本节点可触及的上一节点号：pre_node_key = 5----本节点距离上一个节点“节点5”的距离：pre_node_value = (3.21, '分歧')----上一节点“节点5”距离0节点的最短距离：f[pre_node_key][0] = 8.25----本节点路径上一节点“节点5”距离0节点的距离：distance_from_0 = 11.46
    本节点的节点号：key = 7----本节点可触及的上一节点号：pre_node_key = 6----本节点距离上一个节点“节点6”的距离：pre_node_value = (5.29, '歧')----上一节点“节点6”距离0节点的最短距离：f[pre_node_key][0] = 12.15----本节点路径上一节点“节点6”距离0节点的距离：distance_from_0 = 17.44
    本节点的节点号：key = 7----当前节点路径所触及的所有上一节点到达0节点的距离：tuple_temp_list = [(11.46, 5), (17.44, 6)]----当前节点 key 距离0节点的最短距离：min_temp = (11.46, 5)
    将当前节点7距离0节点的（最短距离,路径的节点号）= (7,(11.46, 5)) 加入f---->f = OrderedDict([(0, (0, 0)), (1, (20, 0)), (2, (2.52, 0)), (3, (5.73, 2)), (4, (25.73, 3)), (5, (8.25, 3)), (6, (12.15, 5)), (7, (11.46, 5))])
    ################################################## 利用“维特比算法”构建各个节点的最优路径：结束 ##################################################
    
     ################################################## 提取最优路径：开始 ##################################################
    最后一个结点7：last = 7----第一个结点0：first = 0----初始化最优路径：path_result = [7]----最后一个结点的所有前一个结点：pre_last = (11.46, 5)
    最优路径：path_result = [7, 5, 3, 2, 0]
    ################################################## 提取最优路径：结束 ##################################################
    
     ################################################## 通过最优路径得到分词结果：开始 ##################################################
    最优路径：path_result = [7, 5, 3, 2, 0]----index = 0----当前节点号：num = 7----在最优路径里，当前节点号的上一个节点号：path_result[index + 1] = 5----当前节点号7与上一节点号5之间的词汇：分歧
    最优路径：path_result = [7, 5, 3, 2, 0]----index = 1----当前节点号：num = 5----在最优路径里，当前节点号的上一个节点号：path_result[index + 1] = 3----当前节点号5与上一节点号3之间的词汇：意见
    最优路径：path_result = [7, 5, 3, 2, 0]----index = 2----当前节点号：num = 3----在最优路径里，当前节点号的上一个节点号：path_result[index + 1] = 2----当前节点号3与上一节点号2之间的词汇：有
    最优路径：path_result = [7, 5, 3, 2, 0]----index = 3----当前节点号：num = 2----在最优路径里，当前节点号的上一个节点号：path_result[index + 1] = 0----当前节点号2与上一节点号0之间的词汇：经常
    text_result = ['分歧', '意见', '有', '经常']
    翻转后：text_result = ['经常', '有', '意见', '分歧']
    ################################################## 通过最优路径得到分词结果：结束 ##################################################
    word_segmentation_result: 经常/有/意见/分歧/
    
    Process finished with exit code 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210303114645601.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70