1. <dd id="erndk"></dd>
                1. 機器學習:維特比算法(Viterbi Algorithm)【場景:HMM模型中的解碼問題(求給定觀測序列的條件概率P(I|O,λ)最大時的隱藏狀態序列)、“籬笆網絡”最短/最大路徑、分詞】【動態規劃】

                  互聯網 2022/1/4 1:08:27

                  一、維特比算法(Viterbi Algorithm)講解方式01:籬笆網絡(Lattice)的最短路徑問題 已知下圖的籬笆網絡,每個節點之間的數字表示相鄰節點之間的距離,舉個例子來說,如果我走,這個距離是。那么如果讓你從A走到E,最短路徑是哪一條呢? 顯然大家都知道,通過窮舉的方…

                  一、維特比算法(Viterbi Algorithm)講解方式01:籬笆網絡(Lattice)的最短路徑問題

                  已知下圖的籬笆網絡,每個節點之間的數字表示相鄰節點之間的距離,舉個例子來說,如果我走,這個距離是。那么如果讓你從A走到E,最短路徑是哪一條呢?
                  在這里插入圖片描述
                  顯然大家都知道,通過窮舉的方法是很容易得到最短路徑,可是問題就在于如果窮舉的話,需要的加法次數不用算你也知道實在是太多啦(每條路徑需要計算次加法,一共條路徑共次計算)!像這種沒幾層的籬笆網絡也就罷了,如果每層13個節點,一共12層(然而這個規模對于標注問題來說也依然根本不算什么),可想而知那個線有多亂,如果僅僅窮舉的話,這個計算量(大致是每條次計算,一共條路徑共大約次計算)怕是超級計算機也吃不消。

                  如下圖,假如你從S和E之間找一條最短的路徑,除了遍歷完所有路徑,還有什么更好的方法?答案:viterbi (維特比)算法。

                  在這里插入圖片描述

                  viterbi維特比算法解決的是籬笆型的圖的最短路徑問題,圖的節點按列組織,每列的節點數量可以不一樣,每一列的節點只能和相鄰列的節點相連,不能跨列相連,節點之間有著不同的距離,距離的值就不在圖上一一標注出來了,大家自行腦補。

                  為了找出S到E之間的最短路徑,我們先從S開始從左到右一列一列地來看。

                  首先起點是S,從S到A列的路徑有三種可能:S-A1、S-A2、S-A3,如下圖:

                  在這里插入圖片描述

                  我們不能武斷地說S-A1、S-A2、S-A3中的哪一段必定是全局最短路徑中的一部分,目前為止任何一段都有可能是全局最短路徑的備選項。

                  我們繼續往右看,到了B列。按B列的B1、B2、B3逐個分析。

                  先看B1:

                  在這里插入圖片描述
                  在這里插入圖片描述

                  如上圖,經過B1的所有路徑只有3條:

                  S-A1-B1

                  S-A2-B1

                  S-A3-B1

                  以上這三條路徑,各節點距離加起來對比一下,我們就可以知道其中哪一條是最短的。假設S-A3-B1是最短的,那么我們就知道了經過B1的所有路徑當中S-A3-B1是最短的,其它兩條路徑路徑S-A1-B1和S-A2-B1都比S-A3-B1長,絕對不是目標答案,可以大膽地刪掉了。刪掉了不可能是答案的路徑,就是viterbi算法(維特比算法)的重點,因為后面我們再也不用考慮這些被刪掉的路徑了?,F在經過B1的所有路徑只剩一條路徑了,如下圖:

                  在這里插入圖片描述

                  接下來,我們繼續看B2:

                  在這里插入圖片描述

                  同理,如上圖,經過B2的路徑有3條:

                  S-A1-B2

                  S-A2-B2

                  S-A3-B2

                  這三條路徑中,各節點距離加起來對比一下,我們肯定也可以知道其中哪一條是最短的,假設S-A1-B2是最短的,那么我們就知道了經過B2的所有路徑當中S-A1-B2是最短的,其它兩條路徑路徑S-A2-B2和S-A3-B1也可以刪掉了。經過B2所有路徑只剩一條,如下圖:

                  在這里插入圖片描述

                  接下來我們繼續看B3:

                  在這里插入圖片描述

                  同理,如上圖,經過B3的路徑也有3條:

                  S-A1-B3

                  S-A2-B3

                  S-A3-B3

                  這三條路徑中我們也肯定可以算出其中哪一條是最短的,假設S-A2-B3是最短的,那么我們就知道了經過B3的所有路徑當中S-A2-B3是最短的,其它兩條路徑路徑S-A1-B3和S-A3-B3也可以刪掉了。經過B3的所有路徑只剩一條,如下圖:

                  在這里插入圖片描述
                  現在對于B列的所有節點我們都過了一遍,B列的每個節點我們都刪除了一些不可能是答案的路徑,看看我們剩下哪些備選的最短路徑,如下圖:

                  在這里插入圖片描述
                  上圖是我們刪掉了其它不可能是最短路徑的情況,留下了三個有可能是最短的路徑:S-A3-B1、S-A1-B2、S-A2-B3?,F在我們將這三條備選的路徑放在一起匯總到下圖:

                  在這里插入圖片描述
                  S-A3-B1、S-A1-B2、S-A2-B3都有可能是全局的最短路徑的備選路徑,我們還沒有足夠的信息判斷哪一條一定是全局最短路徑的子路徑。

                  如果我們你認為沒毛病就繼續往下看C列,如果不理解,回頭再看一遍,前面的步驟決定你是否能看懂viterbi算法(維特比算法)。

                  接下來講到C列了,類似上面說的B列,我們從C1、C2、C3一個個節點分析。

                  經過C1節點的路徑有:

                  S-A3-B1-C1、

                  S-A1-B2-C1、

                  S-A2-B3-C1

                  在這里插入圖片描述
                  和B列的做法一樣,從這三條路徑中找到最短的那條(假定是S-A3-B1-C1),其它兩條路徑同樣道理可以刪掉了。那么經過C1的所有路徑只剩一條,如下圖:

                  在這里插入圖片描述

                  同理,我們可以找到經過C2和C3節點的最短路徑,匯總一下:

                  在這里插入圖片描述
                  到達C列時最終也只剩3條備選的最短路徑,我們仍然沒有足夠信息斷定哪條才是全局最短。

                  最后,我們繼續看E節點,才能得出最后的結論。

                  到E的路徑也只有3種可能性:

                  在這里插入圖片描述
                  E點已經是終點了,我們稍微對比一下這三條路徑的總長度就能知道哪條是最短路徑了。

                  在這里插入圖片描述
                  在效率方面相對于粗暴地遍歷所有路徑,viterbi 維特比算法到達每一列的時候都會刪除不符合最短路徑要求的路徑,大大降低時間復雜度。

                  二、維特比算法(Viterbi Algorithm)講解方式02:分詞算法

                  維特比算法(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)]的值標到邊上,
                  在這里插入圖片描述

                  求 ? 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,所有的路徑值都可以算出來。我們維護一個列表來表示 f ( n ) f(n) f(n) 的各值:

                  結點1234567
                  f(n)202.525.7325.738.2512.511.46
                  結點的上一個結點00

                  第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
                  
                  隨時隨地學軟件編程-關注百度小程序和微信小程序
                  關于找一找教程網

                  本站文章僅代表作者觀點,不代表本站立場,所有文章非營利性免費分享。
                  本站提供了軟件編程、網站開發技術、服務器運維、人工智能等等IT技術文章,希望廣大程序員努力學習,讓我們用科技改變世界。
                  [機器學習:維特比算法(Viterbi Algorithm)【場景:HMM模型中的解碼問題(求給定觀測序列的條件概率P(I|O,λ)最大時的隱藏狀態序列)、“籬笆網絡”最短/最大路徑、分詞】【動態規劃】]http://www.yachtsalesaustralia.com/tech/detail-279710.html

                  贊(0)
                  關注微信小程序
                  程序員編程王-隨時隨地學編程

                  掃描二維碼或查找【程序員編程王】

                  可以隨時隨地學編程啦!

                  技術文章導航 更多>
                  国产在线拍揄自揄视频菠萝

                        1. <dd id="erndk"></dd>