jieba分詞學習筆記（三）

nevermind 發布于2019-07-24 18:16 / 2822人閱讀

摘要：由此得到了，下一步就是使用動態規劃對最大概率路徑進行求解。最大概率路徑值得注意的是，的每個結點，都是帶權的，對于在詞典里面的詞語，其權重為其詞頻，即。動態規劃求解法滿足的條件有兩個重復子問題最優子結構我們來分析最大概率路徑問題。

DAG（有向無環圖）

有向無環圖，directed acyclic graphs，簡稱DAG，是一種圖的數據結構，其實很naive，就是沒有環的有向圖_(:з」∠)_

DAG在分詞中的應用很廣，無論是最大概率路徑，還是后面套NN的做法，DAG都廣泛存在于分詞中。

因為DAG本身也是有向圖，所以用鄰接矩陣來表示是可行的，但是jieba采用了python的dict，更方便地表示DAG，其表示方法為:

{prior1:[next1,next2...,nextN]，prior2:[next1",next2"...nextN"]...}

以句子 "國慶節我在研究結巴分詞"為例，其生成的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] 節[2] 我[3] 在[4] 研[5] 究[6] 結[7] 巴[8] 分[9] 詞[10]

get_DAG()函數代碼如下：

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，可以看到代碼循環切片句子，FREQ即是詞典的{word:frequency}的dict

因為在載入詞典的時候已經將word和word的所有前綴加入了詞典，所以一旦frag not in FREQ，即可以斷定frag和以frag為前綴的詞不在詞典里，可以跳出循環。

由此得到了DAG，下一步就是使用dp動態規劃對最大概率路徑進行求解。

最大概率路徑

值得注意的是，DAG的每個結點，都是帶權的，對于在詞典里面的詞語，其權重為其詞頻，即FREQ[word]。我們要求得route = (w1, w2, w3 ,.., wn)，使得Σweight(wi)最大。

動態規劃求解法

滿足dp的條件有兩個

重復子問題

最優子結構

我們來分析最大概率路徑問題。

重復子問題

對于結點Wi和其可能存在的多個后繼Wj和Wk，有:

任意通過Wi到達Wj的路徑的權重為該路徑通過Wi的路徑權重加上Wj的權重{Ri->j} = {Ri + weight(j)} ；
任意通過Wi到達Wk的路徑的權重為該路徑通過Wi的路徑權重加上Wk的權重{Ri->k} = {Ri + weight(k)} ；

即對于擁有公共前驅Wi的節點Wj和Wk，需要重復計算到達Wi的路徑。

最優子結構

對于整個句子的最優路徑Rmax和一個末端節點Wx，對于其可能存在的多個前驅Wi，Wj，Wk...,設到達Wi，Wj，Wk的最大路徑分別為Rmaxi，Rmaxj，Rmaxk，有：

Rmax = max(Rmaxi,Rmaxj,Rmaxk...) + weight(Wx)

于是問題轉化為

求Rmaxi, Rmaxj, Rmaxk...

組成了最優子結構，子結構里面的最優解是全局的最優解的一部分。

狀態轉移方程

由上一節，很容易寫出其狀態轉移方程

Rmax = max{(Rmaxi,Rmaxj,Rmaxk...) + weight(Wx)}

代碼

上面理解了，代碼很簡單，注意一點total的值在加載詞典的時候求出來的，為詞頻之和，然后有一些諸如求對數的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])

云服務器 GPU云服務器 jieba分詞學習筆記學習筆記一基礎學習筆記

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37649.html

jieba分詞學習筆記（二）

分詞模式 jieba分詞有多種模式可供選擇。可選的模式包括：全切分模式精確模式搜索引擎模式同時也提供了HMM模型的開關。其中全切分模式就是輸出一個字串的所有分詞，精確模式是對句子的一個概率最佳分詞，而搜索引擎模式提供了精確模式的再分詞，將長詞再次拆分為短詞。效果大抵如下： # encoding=utf-8 import jieba seg_list = jieba.cut(我...

fxp 2019-07-24 18:16 評論0 收藏0
分詞，難在哪里？科普+解決方案！

摘要：分詞的算法中文分詞有難度，不過也有成熟的解決方案。例如通過人民日報訓練的分詞系統，在網絡玄幻小說上，分詞的效果就不會好。三的優點是開源的，號稱是中，最好的中文分詞組件。 showImg(https://segmentfault.com/img/remote/1460000016359704?w=1350&h=900); 題圖：by Lucas Davies 一、前言分詞，我想是大多數...

Steven 2019-07-30 17:48 評論0 收藏0
Python第三方庫jieba庫與中文分詞全面詳解

　　Python在工作中的應用還是比較的廣泛的，市場上面對于這類人才開出的薪資還是比較的高的。那么，如何使用第三方庫jieba庫與中文分詞進行一個分解呢？下面小編就給大家詳細的做出一個解答。　　一、什么是jieba庫　　jieba是優秀的中文分詞第三方庫，由于中文文本之間每個漢字都是連續書寫的，我們需要通過特定的手段來獲得其中的每個詞組，這種手段叫做分詞，我們可以通過jieba庫來完成這個過程。　...

89542767 2022-11-05 11:41 評論0 收藏0
python 實現中文分詞統計

摘要：利用我們集成的目前世界上規模最大的人工分詞和詞性標注中文語料庫約含萬字訓練而成，模型標注能力強大。據說是最好的中文分詞組件，支持等多種語言。總是看到別人用Python搞各種統計，前端菜鳥的我也來嘗試了一把。有各種語義分析庫在，一切好像并不是很復雜。不過Python剛開始看，估計代碼有點丑。一、兩種中文分詞開發包 thulac (http://thulac.thunlp.org/)...

Honwhy 2019-07-30 14:52 評論0 收藏0