詞圖指的是句子中所有詞可能構(gòu)成的圖。如果一個(gè)詞A的下一個(gè)詞可能是B的話，那么A和B之間具有一條路徑E(A,B)。一個(gè)詞可能有多個(gè)后續(xù)，同時(shí)也可能有多個(gè)前驅(qū)，它們構(gòu)成的圖我稱作詞圖。

需要稀疏2維矩陣模型，以一個(gè)詞的起始位置作為行，終止位置作為列，可以得到一個(gè)二維矩陣。例如：“他說(shuō)的確實(shí)在理”這句話

圖詞的存儲(chǔ)方法：一種是的DynamicArray法，一種是快速offset法。Hanlp代碼中采用的是第二種方法。

1、DynamicArray（二維數(shù)組）法

在詞圖中，行和列的關(guān)系：col為n 的列中所有詞可以與row為n 的所有行中的詞進(jìn)行組合。例如“的確”這個(gè)詞，它的col =5，需要和它計(jì)算平滑值的有兩個(gè)，分別是row =5的兩個(gè)詞：“實(shí)”和“實(shí)在”。但是在遍歷和插入的時(shí)候，需要一個(gè)個(gè)比較col和row的關(guān)系，復(fù)雜度是O(N)。

2、快速offset

一個(gè)一維數(shù)組，每個(gè)元素是一個(gè)單鏈表

“的確”的行號(hào)是4,長(zhǎng)度是2,4+2=6，于是第六行的兩個(gè)詞“實(shí)/實(shí)在”就是“的確”的后續(xù)。

同時(shí)這種方法速度非?？?，插入和查詢的時(shí)間都是O(1)。

Hanlp核心詞典：

最短路徑算法—viterbi（動(dòng)態(tài)規(guī)劃路徑）

Frequency:核心詞典中的詞頻

nTwoWordsFreq:共現(xiàn)詞頻

intMAX_FREQUENCY= 25146057

double dTemp =(double) 1 / MAX_FREQUENCY +0.00001

dSmoothingPara =0.1

Viterbi最短路徑有向圖

1、計(jì)算過(guò)程從上至下，根據(jù)計(jì)算出的權(quán)重值

變更前驅(qū)結(jié)點(diǎn)，保證前驅(qū)結(jié)點(diǎn)唯一（動(dòng)態(tài)規(guī)劃路徑）

2、計(jì)算結(jié)束后，從最后一個(gè)結(jié)點(diǎn)開(kāi)始取出term

,依次取出該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即可

分詞結(jié)果：理，在，確實(shí)，的，說(shuō)，他

文章來(lái)源于亞當(dāng)-adam的博客