ICTCLAS初步分詞包括：1）原子切分；2）找出原子之間所有可能的組詞方案；3）N-最短路徑中文詞語(yǔ)粗分三步。
例如：“他說(shuō)的確實(shí)在理”這句話(huà)。
1）原子切分的目的是完成單個(gè)漢字的切分。經(jīng)過(guò)原子切分后變成“始##始/他/說(shuō)/的/確/實(shí)/在/理/末##末”。
2）然后根據(jù)“詞庫(kù)字典”找出所有原子之間所有可能的組詞方案。經(jīng)過(guò)詞庫(kù)檢索后，該句話(huà)變?yōu)?#8220;始##始/他/說(shuō)/的/的確/確/確實(shí)/實(shí)/實(shí)在/在/在理/末##末”。
3）N-最短路徑中文詞語(yǔ)粗分。下面的過(guò)程就比較復(fù)雜了，首先我們要找出這些詞之間所有可能的兩兩組合的距離（這需要檢索BigramDict.dct詞典庫(kù)）。對(duì)于上面的案例而言，得到的BiGraph結(jié)果如下：
row: 0, col: 1, eWeight: 3.37, nPOS: 1, sWord:始##始@他
row: 1, col: 2, eWeight: 2.25, nPOS: 0, sWord:他@說(shuō)
row: 2, col: 3, eWeight: 4.05, nPOS: 0, sWord:說(shuō)@的
row: 2, col: 4, eWeight: 7.11, nPOS: 0, sWord:說(shuō)@的確
row: 3, col: 5, eWeight: 4.10, nPOS: 0, sWord:的@確
row: 3, col: 6, eWeight: 4.10, nPOS: 0, sWord:的@確實(shí)
row: 4, col: 7, eWeight: 11.49, nPOS: 25600, sWord:的確@實(shí)
row: 5, col: 7, eWeight: 11.63, nPOS: 0, sWord:確@實(shí)
row: 4, col: 8, eWeight: 11.49, nPOS: 25600, sWord:的確@實(shí)在
row: 5, col: 8, eWeight: 11.63, nPOS: 0, sWord:確@實(shí)在
row: 6, col: 9, eWeight: 3.92, nPOS: 0, sWord:確實(shí)@在
row: 7, col: 9, eWeight: 10.98, nPOS: 0, sWord:實(shí)@在
row: 6, col: 10, eWeight: 10.97, nPOS: 0, sWord:確實(shí)@在理
row: 7, col: 10, eWeight: 10.98, nPOS: 0, sWord:實(shí)@在理
row: 8, col: 11, eWeight: 11.17, nPOS: 0, sWord:實(shí)在@理
row: 9, col: 11, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 10, col: 12, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 11, col: 12, eWeight: 11.95, nPOS: 0, sWord:理@末##末
可以從上表中可以看出“的@確實(shí)”的距離為4.10，而“的確@實(shí)”間的距離為11.49，這說(shuō)明“的@確實(shí)”的組合可能性要大一些。不過(guò)這只是一面之詞，究竟如何組詞需要放到整句話(huà)的環(huán)境下通盤(pán)考慮，達(dá)到整體最優(yōu)。這就是N最短路徑需要完成的工作。
在求最短路徑前我們需要將上表?yè)Q一個(gè)角度觀(guān)察，其實(shí)上表可以等價(jià)的表述成如下圖所示的“有向圖”：
上表中詞與詞的組合（例如“的@確實(shí)”）在該圖中對(duì)應(yīng)一條邊（由節(jié)點(diǎn)“的”到節(jié)點(diǎn)“確實(shí)”），其路徑長(zhǎng)度就是上表中的eWeight值。這樣一來(lái)，求最優(yōu)分詞方案就成了求整體最短路徑。
由于是初次切分，為了提高后續(xù)優(yōu)化質(zhì)量，這里求的是N最短路徑，即路徑長(zhǎng)度由小到大排序后的前N種長(zhǎng)度的所有路徑。對(duì)于上面案例，我們假設(shè)N=2，那么求解得到的路徑有2條（注意也可能比兩條多，關(guān)于這點(diǎn)我 將在后續(xù)專(zhuān)門(mén)介紹NShortPath時(shí)再說(shuō)）：
路徑（1）：
0, 1, 2, 3, 6, 9, 11, 12, 13
始##始 / 他 / 說(shuō) / 的 / 確實(shí) / 在 / 理 / 末##末
路徑（2）：
0, 1, 2, 3, 6, 10, 12, 13
始##始 / 他 / 說(shuō) / 的 / 確實(shí) / 在理 / 末##末
如果要想真正搞清楚上述過(guò)程，必須對(duì)下面的數(shù)據(jù)結(jié)構(gòu)以及它的幾種不同的表述方式有個(gè)透徹的了解。
DynamicArray是什么？其實(shí)它的本質(zhì)是一個(gè)經(jīng)過(guò)排序的鏈表。為了表達(dá)的更明白些，我們不妨看下面這張圖：
（圖一）
上面這張圖是一個(gè)按照index值進(jìn)行了排序的鏈表，當(dāng)插入新結(jié)點(diǎn)時(shí)必須確保index值的有序性。DynamicArray類(lèi)完成的功能基本上與上面這個(gè)鏈表差不多，只是排序規(guī)則不是index，而是row和col兩個(gè)數(shù)據(jù)，如下圖：
（圖二）
大家可以看到，這個(gè)有序鏈表的排序規(guī)則是先按row排序，row相同的按照col排序。當(dāng)然排序規(guī)則是可以改變的，如果先按col排，再按row排，則上面的鏈表必須表述成：
（圖三）
原有ICTCLAS實(shí)現(xiàn)時(shí)，在一個(gè)類(lèi)里面綜合考慮了row先排序和col先排序的兩種情況，這在SharpICTCLAS中做了很大調(diào)整，將DynamicArray類(lèi)作為父類(lèi)提供一些基礎(chǔ)操作，同時(shí)設(shè)計(jì)了RowFirstDynamicArray和ColumnFirstDynamicArray類(lèi)作為子類(lèi)提供專(zhuān)門(mén)的方法，這使得代碼變得清晰多了（有關(guān)DynamicArray的實(shí)現(xiàn)我在下一篇文章中再做介紹）。
在本文最前面給出的案例中，根據(jù)“詞庫(kù)字典”找出所有原子字間的組詞方案，其結(jié)果為“始##始/他/說(shuō)/的/的確/確/確實(shí)/實(shí)/實(shí)在/在/在理/末##末”，而內(nèi)容就是靠一個(gè)RowFirstDynamicArray存儲(chǔ)的，如下：
row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 19823.00, nPOS: 0, sWord:他
row: 2, col: 3, eWeight: 17649.00, nPOS: 0, sWord:說(shuō)
row: 3, col: 4, eWeight: 358156.00, nPOS: 0, sWord:的
row: 3, col: 5, eWeight: 210.00, nPOS: 25600, sWord:的確
row: 4, col: 5, eWeight: 181.00, nPOS: 0, sWord:確
row: 4, col: 6, eWeight: 361.00, nPOS: 0, sWord:確實(shí)
row: 5, col: 6, eWeight: 357.00, nPOS: 0, sWord:實(shí)
row: 5, col: 7, eWeight: 295.00, nPOS: 0, sWord:實(shí)在
row: 6, col: 7, eWeight: 78484.00, nPOS: 0, sWord:在
row: 6, col: 8, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 7, col: 8, eWeight: 129.00, nPOS: 0, sWord:理
row: 8, col: 9, eWeight:2079997.00, nPOS: 4, sWord:末##末
如果根據(jù)RowFirstDynamicArray中row和col的坐標(biāo)信息將DynamicArray放到一個(gè)二維表格中的話(huà)，我們就得到了DynamicArray的二維圖表表示。如下圖所示：
（圖四）
在這張圖中，行和列有一個(gè)非常有意思的關(guān)系：col為 n 的列中所有詞可以與row為 n 的所有行中的詞進(jìn)行組合。例如“的確”這個(gè)詞，它的col = 5，需要和它計(jì)算平滑值的有兩個(gè)，分別是row = 5的兩個(gè)詞：“實(shí)”和“實(shí)在”。
如果將所有行與列之間詞與詞之間的關(guān)系找到，我們就可以得到另外一個(gè)ColumnFirstDynamicArray，如本文第一張表中內(nèi)容所示。將該ColumnFirstDynamicArray的內(nèi)容放到另外一個(gè)二維表中就得到如下圖所示內(nèi)容：
（圖五）
- ColumnFirstDynamicArray的有向圖表示
上面這張表可以和一張有向圖所對(duì)應(yīng)，就如前文所說(shuō)，詞與詞的組合（例如“的@確實(shí)”）在該圖中對(duì)應(yīng)一條邊（由節(jié)點(diǎn)“的”到節(jié)點(diǎn)“確實(shí)”），其路徑長(zhǎng)度就是上表中的eWeight值，如下圖所示：
剩下的事情就是針對(duì)該圖求解N最短路徑了，這將在后續(xù)文章中介紹。
ICTCLAS的初步分詞是一個(gè)比較復(fù)雜的過(guò)程，涉及的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)表示以及相關(guān)算法都頗有難度。在SharpICTCLAS中，對(duì)原有C++代碼做了比較多的更改，重新設(shè)計(jì)了DynamicArray類(lèi)與NShortPath方法，在犧牲有限性能的同時(shí)力爭(zhēng)大幅度簡(jiǎn)化代碼的復(fù)雜度，提高可讀性。
有關(guān)SharpICTCLAS中DynamicArray類(lèi)的實(shí)現(xiàn)以及在代碼可讀性與性能之間的權(quán)衡將在下一篇文章中加以介紹。
來(lái)源：http://www.cnblogs.com/zhenyulu/category/85598.html