私信小編007即可自動獲取大量Python視頻教程以及各類 PDF!
這個項目我有視頻教程,私信即可。
閒來無事,在博客園的論壇裡隨意遊蕩,看到一個開源的python庫,名字叫做結巴分詞,一直很好奇這些自然語言的處理方式,但是網上的相關介紹卻少的可憐,僅有的一些博客寫介紹的比較淺。幸好代碼量不多,花了兩週的時間把代碼和設計的算法仔細的梳理了一邊,供大家參考,也希望能夠拋磚引玉。
分詞算法介紹
先看一下分詞用到了哪些算法,文檔裡面如下介紹:
• 基於Trie樹結構實現高效的詞圖掃描,生成句子中漢字所有可能成詞情況所構成的有向無環圖(DAG)
• 採用了動態規劃查找最大概率路徑, 找出基於詞頻的最大切分組合
• 對於未登錄詞,採用了基於漢字成詞能力的HMM模型,使用了Viterbi算法
實現方案
估計是我水平比較菜,反正我看完之後不知所云。廢話也不說了,下面好好來講講代碼,結巴分詞最頂層的目錄jieba下有如下文件,dict.txt是一個詞庫,裡面記錄了大約350000個詞語的詞頻和詞性,結巴分詞提供的功能接口都定義和實現在__init__.py中,finalseg文件夾中提供了隱馬爾科夫維特比算法相關的代碼,用於文本切詞;analyse中提供了TF-IDF算法和textrank算法相關的實現,可以用於提取文章關鍵詞以及文本摘要;唯一讓我比較抑或的是posseg文件夾中的代碼,和finalseg極其相似,實在猜測不出添加這麼一個文件夾的意圖。
概括的講完結巴分詞的文件結構後,再詳細的講一講各個文件的內容。dict.txt的內容如下圖所示,裡面有每個詞的統計次數和詞性,在文檔中提到的算法二中用到了詞的統計次數,但是似乎所有的算法都沒有用到詞性,有想法的小夥伴可以嘗試改進一下。
_compat.py文件是處理python2和python3之間差異的一個文件,有一個函數strdecode專門用來將字符串轉換unicode, 感覺還蠻有用的
def strdecode(sentence): if not isinstance(sentence, text_type): try: sentence = sentence.decode('utf-8') except UnicodeDecodeError: sentence = sentence.decode('gbk', 'ignore') return sentence
__main__.py文件將底層的接口通過命令行的方式暴露給用戶,用戶可以設置自己的詞典,需要處理的文件,是否使用隱馬爾可夫模型,這個文件不涉及分詞的算法,看起來沒有什麼難度,原來一直沒有搞清楚__main__.py和__init__.py這兩個文件的關係,通過萬能的度娘總算搞清楚了,這裡貼一個鏈接,http://www.tuicool.com/articles/iYRfe2 寫的非常通俗易懂。
__init__.py這個文件是結巴分詞的核心,裡面提供了分詞的接口:cut。它有三種模式:
1. 全模式,把句子中所有在詞庫中出現的詞都找出來
2. 不使用隱馬爾科夫模型的精確模式,基於最大概率路徑, 找出基於詞頻的最大切分組合
3. 同時使用最大概率路徑和隱馬爾科夫模型,對於未登錄詞也有比較好的切分效果
這三種模式都會根據字典生成句子中漢字構成的有向無環圖(DAG),實現的函數如下:
def get_DAG(sentence): global FREQ DAG = {} N = len(sentence) for k in xrange(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in FREQ: if FREQ[frag]: tmplist.append(i) i += 1 frag = sentence[k:i + 1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG
以“但也並不是那麼出乎意料或難以置信”這句話作為輸入,生成的DAG如下,簡單的講就是把句子中詞的位置標記出來
0 [0] 但
1 [1] 也
2 [2] 並
3 [3, 4] 不是
4 [4] 是
5 [5, 6] 那麼
6 [6] 麼
7 [7, 8, 10] 出乎意料
8 [8] 乎
9 [9, 10] 意料
10 [10] 料
11 [11] 或
12 [12, 13, 15] 難以置信
13 [13] 以
14 [14, 15] 置信
15 [15] 信
一、全模式 現在看一下全模式的代碼:
def __cut_all(sentence): dag = get_DAG(sentence) old_j = -1 for k, L in iteritems(dag): if len(L) == 1 and k > old_j: yield sentence[k:L[0] + 1] old_j = L[0] else: for j in L: if j > k: yield sentence[k:j + 1] old_j = j
就是把上面生成的DAG中的所有的組合顯示出來,還是以上面的句子為例,全模式切分的結果如下,是不是覺得這麼非常的easy。
但/也/並/不是/那麼/出乎/出乎意料/意料/或/難以/難以置信/置信
二、 不使用隱馬爾科夫模型的精確模式,用一個比較簡單的句子為例,輸入的句子是“難以置信”,按照全模式會輸出:難以/置信/難以置信 三個組合。作為一個將漢語的人,我們明顯知道最佳的分詞結果就是“難以置信”這一種結果。下面用最大概率的方法解釋為什麼是這個結果。子啊字典中我們可以查詢“難以置信”所有的組合以及它們出現的概率(除以所有詞出現的總次數)如下:
詞次數出現概率
難185053.08*10-4
以1361362.27*10-3
置111451.85*10-4
信111881.86*10-4
難以56819.45*10-5
置信641.06*10-6
難以置信1692.81*10-6
根據上面各詞的概率,可以算出“難以置信”所有分詞方式的概率,而最大出現的可能就是“難以置信”,而且它的概率相比其他組合高的可不是一倍兩倍。
分詞方式出現概率
難 以 置 信1.37*10-14
難以 置 信3.65*10-14
難 以 置信7.41*10-13
難以 置信1.01*10-10
難以置信2.81*10-6
實現的代碼如下,相信參考我的例子,看下面的代碼也就不是什麼大難題了,在計算概率的時候,結巴分詞用的方式是log函數
def calc(sentence, DAG, route): N = len(sentence) route[N] = (0, 0) logtotal = log(total) for idx in xrange(N - 1, -1, -1): route[idx] = max((log(FREQ.get(sentence[idx:x + 1]) or 1) - logtotal + route[x + 1][0], x) for x in DAG[idx]) def __cut_DAG_NO_HMM(sentence): DAG = get_DAG(sentence) route = {} calc(sentence, DAG, route) x = 0 N = len(sentence) buf = '' while x < N: y = route[x][1] + 1 l_word = sentence[x:y] if re_eng.match(l_word) and len(l_word) == 1: buf += l_word x = y else: if buf: yield buf buf = '' yield l_word x = y if buf: yield buf buf = ''三、 同時使用最大概率路徑和隱馬爾科夫模型
由於這一部分設計到的理論知識比較多,建議先看一下相關的論文和博客。然後再通過代碼驗證對理論算法的知識,可以更深刻的理解隱馬爾科夫模型。在這個地方中文句子作為可觀測序列,對應的隱藏狀態值集合為(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分別代表每個狀態代表的是該字在詞語中的位置,B代表該字是詞語中的起始字,M代表是詞語中的中間字,E代表是詞語中的結束字,S則代表是單字成詞。
在HMM模型中文分詞中,我們的輸入是一個句子(也就是觀察值序列),輸出是這個句子中每個字的狀態值。比如:“小明碩士畢業於中國科學院計算所”,隱藏序列為
BEBEBMEBEBMEBES,根據這個狀態序列我們可以進行切詞:BE/BE/BME/BE/BME/BE/S,所以切詞結果如下:小明/碩士/畢業於/中國/科學院/計算/所。
finalseg中有BMES各個狀態間的轉移概率以及隱藏狀態對應於各個中文的發射概率,再根據維特比算法,計算分詞
閱讀更多 編程新世界 的文章