hadoop小學生
圣騎士
圣騎士
  • 注冊日期2018-09-13
  • 發帖數142
  • QQ3234520070
  • 火幣319枚
  • 粉絲0
  • 關注0
閱讀:670回復:0

HanLP-最短路徑分詞

樓主#
更多 發布于:2019-06-05 11:16
今天介紹的內容是最短路徑分詞。最近換回了thinkpad x1,原因是mac的13.3寸的屏幕看代碼實在是不方便,也可能是人老了吧,^_^。等把hanlp詞法分析介紹結束后,還是會換回macbook pro的。個人有強迫癥,只要看或寫java或C/C++代碼或者用開發機的化,還是喜歡在windows下工作。看論文特別是理論的研究還是習慣用mac了。感覺開發還是windows比較順手,理論研究還是mac比較順手。

基本思想:首先根據詞典,找出字串中所有可能的詞(也稱全切分),然后構造詞語切分有向無環圖(也稱作粗分詞圖或粗分詞網)。每個詞對應圖中的一條有向邊。若賦給相應的邊長一個權值(該權值可以是常數,也可以是所構成的詞的屬性值),然后根據該切分圖,在起點到終點的所有路徑中,求出長度值(包括權值)為最短的一條路徑,這條路徑上包含的詞就是該句子的切分結果。若每個結點處記錄N個最短路徑值,則該方法也稱N-最短路徑算法。
為進一步提高切分精度,在詞典中增加詞的屬性值,即給每個詞也給權重。這樣每個詞在漢字串中的權重不同(即構成的有向圖的邊不為等長)。最簡單的詞的權重可以用詞頻表示,高頻詞的權重大,低頻詞的權重小。具體的權重值可以通過大規模語料庫獲得。
雖然HanLP中提供了dijkstra算法的實現,但是當前HanLP中最短路徑分詞使用的是viterbi算法。
例子:他說的確實在理

圖片:圖1.JPG


遍歷計算過程和回溯分詞過程

圖片:圖2.JPG


1) node列與to列
node列的詞語為粗分詞網中所有的詞,to列為在node列為詞word_node的情況下,后邊接的所有可能的詞word_to。第1個詞語前邊有一個“始”詞,最后一個詞語后邊有一個“末”詞。
2) begin2node_w的計算
表示從“始”到node詞的最短路徑權值。可以從待計算值所在行的node列讀取出word詞,在to列中以待計算值所在行開始向上查找word,找到word所在行后(以首次遇到的詞為準),begin2to_w列所對應的值就是待計算值。見圖中下劃線。第一個詞對“始-他”的begin2node_w的值為0。
3) node2to_w的計算

node+w構成的2gram串的概率,也就是轉移概率,計算公式為

圖片:圖3.jpg


計算的HanLP代碼為https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/utility/MathUtility.java calculateWeight(Vertex from, Vertex to)。“始”的頻次取為MAX_FREQUENCY,“始-他”的共現頻次值為“他”作為句首的頻次,“理-末”的共現頻次值為“理”作為句末的頻次。
4) begin2to_w_n的計算
表示從“始”到to詞的最短路徑權值。begin2to_w_n = begin2node_w + node2to_w。
5) begin2to_w_o
表示記錄在to詞下的,到to詞的最短路徑權值,它的初始值為0,之后由begin2to_w來更新。
6) from
表示詞語to的前驅詞。

圖片:圖4.jpg


可以看表中(7,9),(8,10),(11,13),(12,14),(15,16),(17,18)成對行來驗證該公式,其中只有(17.18)行滿足了第3個式子。
6)和(7)的HanLP實現代碼https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/seg/common/Vertex.java updateFrom(Vertex from)
8) 回溯確定分詞路徑
“末”開始向前回溯,末->理->在->確實->的->說->他,可以看表中黃色單元格進行驗證。
經過(6)、(7)兩步,可以確保粗分詞網中任意詞的前驅都是最短路徑的。
遍歷計算過程和回溯過程的HanLP代碼https://github.com/hankcs/HanLP/blob/master/src/main/java/com/hankcs/hanlp/seg/Viterbi/ViterbiSegment.java viterbi(WordNet wordNet)

圖片:圖5.JPG


喜歡0 評分0
DKHadoop用著還不錯!
游客

返回頂部
广东体彩26选5