維特比算法原理可以參考以下文章，講解的非常詳細(xì)，那么接下來將講解維特比算法如何應(yīng)用到分詞算法中，并如何用python代碼實(shí)現(xiàn)。如何通俗地講解 viterbi 算法？?www.zhihu.com

一、過程分析

句子：經(jīng)常有意見分歧

詞典：「“經(jīng)常”，“經(jīng)”，“有”，“有意見”，“意見”，“分歧”，“見”，“意”，“見分歧”，“分”」

概率：「0.1，0.05，0.1，0.1，0.2，0.2，0.05，0.05，0.05，0.1」

-log(x)：「2.3，3，2.3，2.3，1.6，1.6，3，3，3，2.3」

解決方案：

有的字在列表中沒有概率值，那么我們就賦予一個(gè)很小很小的概率，比如

。

那么取-log之后呢是一個(gè)很大的數(shù)，我們暫且假設(shè)為20。

首先構(gòu)造有向圖：根據(jù)詞典和-log(x)畫出有向圖

圖中的每條路徑都可以成為一個(gè)分詞結(jié)果，那么哪個(gè)是最優(yōu)路徑呢？

比較 分詞結(jié)果 經(jīng)常，有，意見，分歧 和 經(jīng)常，有意見，分歧誰更優(yōu)

就是比較P(經(jīng)常，有，意見，分歧)和 P(經(jīng)常，有意見，分歧)的大小，我們選擇概率值大的分詞結(jié)果為最優(yōu)分詞結(jié)果。

對概率值取-log是因?yàn)楦怕手当緛砭秃苄?#xff0c;如果相乘的話會下溢出，所以取了一個(gè)log，負(fù)數(shù)是因?yàn)樗惴ㄖ薪鉀Q最小值問題更為方便，所以取負(fù)號：-logP(經(jīng)常，有，意見，分歧)和 -logP(經(jīng)常，有意見，分歧)那么就選擇結(jié)果值最小的為最優(yōu)分詞結(jié)果

-logP(經(jīng)常，有，意見，分歧)= -(logP(經(jīng)常) + logP(有) + logP(意見) + logP(分歧))

那么就轉(zhuǎn)化為一個(gè)數(shù)值相加的問題了，就是路徑上值之和最小的路徑為最優(yōu)路徑。

那么轉(zhuǎn)化為尋找最短路徑問題，有很多算法可以解決這個(gè)問題，那么在這個(gè)地方我們用維特比算法可以很方便的計(jì)算出來。

我們計(jì)算從1到8的最短路徑，那么首先假定一個(gè)函數(shù)：

f(8): 從節(jié)點(diǎn)1到8的最短路徑的值

f(7): 從節(jié)點(diǎn)1到7的最短路徑的值

往下依次相同的定義

f(8) = f(7) + 20

= f(6) + 1.6

= f(5) + 3

以上3個(gè)路徑中選擇一個(gè)最小的作為從1到8的最優(yōu)路徑

f(7)= f(6) + 2.3

f(6) = f(5) + 2

= f(4)+1.6

= f(3) + 2.3

從上面3個(gè)路徑中選擇最小的作為從1到6的最優(yōu)路徑

如果用遞歸算法計(jì)算的話，有的節(jié)點(diǎn)會重復(fù)計(jì)算很多次，所以可以用動態(tài)規(guī)劃算法來實(shí)現(xiàn)。

我們維護(hù)兩個(gè)個(gè)數(shù)組：

一個(gè)數(shù)組中每個(gè)節(jié)點(diǎn)里面存放從節(jié)點(diǎn)1到當(dāng)前節(jié)點(diǎn)的最短路徑值

另一個(gè)數(shù)組中每個(gè)節(jié)點(diǎn)存放到當(dāng)前節(jié)點(diǎn)的最短路徑值的直接前驅(qū)節(jié)點(diǎn)

由圖可以找到從1到8的最短路徑：

到達(dá)8的最短路徑是從6過來的

到達(dá)6的最短路徑是從3過來的

到達(dá)3的最短路徑是從1過來的

節(jié)點(diǎn)：1,3,6,8

所以最終的分詞結(jié)果是：[經(jīng)常，有意見，分歧]

二、python代碼實(shí)現(xiàn)

總結(jié)

以上是生活随笔為你收集整理的维特比算法 python_维特比算法实现分词的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。