資訊專欄INFORMATION COLUMN
摘要：由此得到了，下一步就是使用動態(tài)規(guī)劃對最大概率路徑進(jìn)行求解。最大概率路徑值得注意的是，的每個結(jié)點，都是帶權(quán)的，對于在詞典里面的詞語，其權(quán)重為其詞頻，即。動態(tài)規(guī)劃求解法滿足的條件有兩個重復(fù)子問題最優(yōu)子結(jié)構(gòu)我們來分析最大概率路徑問題。
有向無環(huán)圖，directed acyclic graphs，簡稱DAG，是一種圖的數(shù)據(jù)結(jié)構(gòu)，其實很naive，就是沒有環(huán)的有向圖_(:з」∠)_
DAG在分詞中的應(yīng)用很廣，無論是最大概率路徑，還是后面套NN的做法，DAG都廣泛存在于分詞中。
因為DAG本身也是有向圖，所以用鄰接矩陣來表示是可行的，但是jieba采用了python的dict，更方便地表示DAG，其表示方法為:
{prior1:[next1,next2...,nextN]，prior2:[next1",next2"...nextN"]...}
以句子 "國慶節(jié)我在研究結(jié)巴分詞"為例，其生成的DAG的dict表示為：
{0: [0, 1, 2], 1: [1], 2: [2], 3: [3], 4: [4], 5: [5, 6], 6: [6], 7: [7, 8], 8: [8], 9: [9, 10], 10: [10]}
其中，
國[0] 慶[1] 節(jié)[2] 我[3] 在[4] 研[5] 究[6] 結(jié)[7] 巴[8] 分[9] 詞[10]
get_DAG()函數(shù)代碼如下：
def get_DAG(self, sentence):
self.check_initialized()
DAG = {}
N = len(sentence)
for k in xrange(N):
tmplist = []
i = k
frag = sentence[k]
while i < N and frag in self.FREQ:
if self.FREQ[frag]:
tmplist.append(i)
i += 1
frag = sentence[k:i + 1]
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
frag即fragment，可以看到代碼循環(huán)切片句子，F(xiàn)REQ即是詞典的{word:frequency}的dict
因為在載入詞典的時候已經(jīng)將word和word的所有前綴加入了詞典，所以一旦frag not in FREQ，即可以斷定frag和以frag為前綴的詞不在詞典里，可以跳出循環(huán)。
由此得到了DAG，下一步就是使用dp動態(tài)規(guī)劃對最大概率路徑進(jìn)行求解。
最大概率路徑值得注意的是，DAG的每個結(jié)點，都是帶權(quán)的，對于在詞典里面的詞語，其權(quán)重為其詞頻，即FREQ[word]。我們要求得route = (w1, w2, w3 ,.., wn)，使得Σweight(wi)最大。
動態(tài)規(guī)劃求解法滿足dp的條件有兩個
重復(fù)子問題
最優(yōu)子結(jié)構(gòu)
我們來分析最大概率路徑問題。
重復(fù)子問題對于結(jié)點Wi和其可能存在的多個后繼Wj和Wk，有:
任意通過Wi到達(dá)Wj的路徑的權(quán)重為該路徑通過Wi的路徑權(quán)重加上Wj的權(quán)重{Ri->j} = {Ri + weight(j)} ；
任意通過Wi到達(dá)Wk的路徑的權(quán)重為該路徑通過Wi的路徑權(quán)重加上Wk的權(quán)重{Ri->k} = {Ri + weight(k)} ；
即對于擁有公共前驅(qū)Wi的節(jié)點Wj和Wk，需要重復(fù)計算到達(dá)Wi的路徑。
最優(yōu)子結(jié)構(gòu)對于整個句子的最優(yōu)路徑Rmax和一個末端節(jié)點Wx，對于其可能存在的多個前驅(qū)Wi，Wj，Wk...,設(shè)到達(dá)Wi，Wj，Wk的最大路徑分別為Rmaxi，Rmaxj，Rmaxk，有：
Rmax = max(Rmaxi,Rmaxj,Rmaxk...) + weight(Wx)
于是問題轉(zhuǎn)化為
求Rmaxi, Rmaxj, Rmaxk...
組成了最優(yōu)子結(jié)構(gòu)，子結(jié)構(gòu)里面的最優(yōu)解是全局的最優(yōu)解的一部分。
狀態(tài)轉(zhuǎn)移方程由上一節(jié)，很容易寫出其狀態(tài)轉(zhuǎn)移方程
Rmax = max{(Rmaxi,Rmaxj,Rmaxk...) + weight(Wx)}
代碼上面理解了，代碼很簡單，注意一點total的值在加載詞典的時候求出來的，為詞頻之和，然后有一些諸如求對數(shù)的trick，代碼是典型的dp求解代碼。
def calc(self, sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(self.total)
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/37649.html
分詞模式 jieba分詞有多種模式可供選擇。可選的模式包括： 全切分模式 精確模式 搜索引擎模式 同時也提供了HMM模型的開關(guān)。 其中全切分模式就是輸出一個字串的所有分詞， 精確模式是對句子的一個概率最佳分詞， 而搜索引擎模式提供了精確模式的再分詞，將長詞再次拆分為短詞。 效果大抵如下： # encoding=utf-8 import jieba seg_list = jieba.cut(我...
摘要：分詞的算法中文分詞有難度，不過也有成熟的解決方案。例如通過人民日報訓(xùn)練的分詞系統(tǒng)，在網(wǎng)絡(luò)玄幻小說上，分詞的效果就不會好。三的優(yōu)點是開源的，號稱是中，最好的中文分詞組件。 showImg(https://segmentfault.com/img/remote/1460000016359704?w=1350&h=900); 題圖：by Lucas Davies 一、前言 分詞，我想是大多數(shù)...
Python在工作中的應(yīng)用還是比較的廣泛的，市場上面對于這類人才開出的薪資還是比較的高的。那么，如何使用第三方庫jieba庫與中文分詞進(jìn)行一個分解呢？下面小編就給大家詳細(xì)的做出一個解答。 一、什么是jieba庫 jieba是優(yōu)秀的中文分詞第三方庫，由于中文文本之間每個漢字都是連續(xù)書寫的，我們需要通過特定的手段來獲得其中的每個詞組，這種手段叫做分詞，我們可以通過jieba庫來完成這個過程。 ...
摘要：利用我們集成的目前世界上規(guī)模最大的人工分詞和詞性標(biāo)注中文語料庫約含萬字訓(xùn)練而成，模型標(biāo)注能力強大。據(jù)說是最好的中文分詞組件，支持等多種語言。 總是看到別人用Python搞各種統(tǒng)計，前端菜鳥的我也來嘗試了一把。有各種語義分析庫在，一切好像并不是很復(fù)雜。不過Python剛開始看，估計代碼有點丑。 一、兩種中文分詞開發(fā)包 thulac (http://thulac.thunlp.org/)...
閱讀 3573·2023-04-26 00:05
閱讀 960·2021-11-11 16:55
閱讀 3539·2021-09-26 09:46
閱讀 3525·2019-08-30 15:56
閱讀 919·2019-08-30 15:55
閱讀 2942·2019-08-30 15:53
閱讀 1954·2019-08-29 17:11
閱讀 822·2019-08-29 16:52
