與拉丁語(yǔ)系語(yǔ)言不同维雇，漢藏語(yǔ)系的自然語(yǔ)言中詞匯是沒有自然分割開的，因此中文分詞是中文自然語(yǔ)言處理的第一步（不過(guò)可以考慮和后面的步驟結(jié)合在一起來(lái)降低算法復(fù)雜度啊……然后還可以考慮仿生算法）着逐，所以先研究和總結(jié)一下現(xiàn)有的中文分詞算法赏廓。
本文許多內(nèi)容參考這篇文獻(xiàn)格遭，感謝分享狠鸳。本文就是在理解這篇文獻(xiàn)的基礎(chǔ)上加點(diǎn)私貨揣苏。
文獻(xiàn)中看到（當(dāng)然這個(gè)不是權(quán)威文獻(xiàn)悯嗓，可能不夠可靠），斯坦福的CRF好像是現(xiàn)在效果最好的算法（中文分詞算法最好的竟然是外國(guó)研究機(jī)構(gòu)也是醉了）卸察，但是算法復(fù)雜度比較大脯厨，效率不夠高，所以我們來(lái)討論一下一些常用的模型坑质。
字典匹配
最簡(jiǎn)單的就是字典匹配合武，其實(shí)跟暴力破解里面的一些想法比較類似，就是搞個(gè)詞庫(kù)涡扼，然后遍歷對(duì)比詞庫(kù)里有沒有這個(gè)詞稼跳。當(dāng)然有時(shí)候還要考慮到整個(gè)句子分解的完整性，最經(jīng)典的就是“最大匹配”的思想吃沪，就是盡可能的匹配最長(zhǎng)的詞岂贩，比如我的句子里有“馬克思主義”這個(gè)詞，而我的詞典里有“馬克思”和“馬克思主義”這兩個(gè)詞巷波，肯定是去匹配“馬克思主義”這個(gè)最長(zhǎng)的詞。其實(shí)可以理解為“馬克思主義”的匹配優(yōu)先級(jí)比“馬克思”高卸伞，其實(shí)我覺得都不需要額外的計(jì)算量抹镊，只要把合成詞的優(yōu)先級(jí)調(diào)整在原詞前面就好了。
[個(gè)人疑惑：在這個(gè)過(guò)程中是不是要保證匹配出的詞匯數(shù)也盡量小]
統(tǒng)計(jì)與消除歧義
當(dāng)然荤傲，我在Day 0里就提到了垮耳，所有的計(jì)算機(jī)項(xiàng)目如果沒有“社科經(jīng)驗(yàn)”的指導(dǎo)是很難提高效率的，其實(shí)這就是所謂的“啟發(fā)式”算法遂黍，在分詞算法中比較有名的之一就是MMSEG终佛。在這個(gè)算法中也延伸到了第二種分詞思路，統(tǒng)計(jì)消除歧義雾家。
舉個(gè)簡(jiǎn)單的例子铃彰，“黑鍵盤/算什么”在沒有消除歧義的情況下有可能被分成“黑鍵/盤算/什么”。
MMSEG算法采取了以下四個(gè)規(guī)則來(lái)消除歧義：
- 選取最大匹配詞匯芯咧；
- 最大平均單詞長(zhǎng)度牙捉；
- 單詞長(zhǎng)度的最小方差；
- 單字單詞的語(yǔ)素自由度的最大和（一個(gè)漢字的出現(xiàn)頻率可以作為它的語(yǔ)素自由度的索引敬飒。一個(gè)高頻率的漢字更可能是一個(gè)單字單詞邪铲，反之亦然。）
具體規(guī)則內(nèi)容和實(shí)例可以查看這篇文獻(xiàn)翻譯无拗。
而統(tǒng)計(jì)算法的實(shí)例可以參見這篇文章
對(duì)于一個(gè)中文字符串“a1a2a3...an”如何正確的用詞語(yǔ)c1,c2..cm表示就是中文分詞的任務(wù)带到，也就是說(shuō)我們要去找尋P(c1c2..cm)最大的分詞，按照馬爾科夫鏈的想法就是說(shuō)我們就是求P(c1)P(c1|c2)P(c1c2|c3)...P(c1c2...cm-1|cm)最大英染。按照阿卡姆剃刀的想法我們可以假設(shè)一個(gè)最可能的實(shí)現(xiàn)揽惹，于是google黑板報(bào)的假設(shè)就是每個(gè)詞只跟前面的詞有關(guān)被饿，于是變?yōu)榍驪(c1)P(c1|c2)P(c2|c3)...P(cm-1|cm)最大。進(jìn)一步的其實(shí)我們可以假設(shè)每個(gè)詞都是相對(duì)獨(dú)立的永丝，也就是求P(c1)P(c2)...P(cm)最大锹漱，那么這個(gè)怎么求呢，就是用dp的方法慕嚷。
解決字典中不存在的詞語(yǔ)
隱馬爾可夫模型HMM（Hidden Markov Model）(<-這個(gè)項(xiàng)目簡(jiǎn)直就是救星哥牍，感覺基礎(chǔ)模型就可以照做了，不過(guò)千萬(wàn)不能抄襲喝检。)基于字標(biāo)注的分詞嗅辣，把分詞問(wèn)題轉(zhuǎn)變?yōu)闃?biāo)注問(wèn)題。
例如：“我s喜b歡e天b安m門e”
其中標(biāo)注的含義為
s：single（標(biāo)注前為單字）
b：begin（標(biāo)注前為詞語(yǔ)開始）
m：middle（標(biāo)注前為詞語(yǔ)中間）
e：end（標(biāo)注前衛(wèi)詞語(yǔ)末尾）
進(jìn)一步的概率模型
在對(duì)語(yǔ)義處理的過(guò)程中最大熵模型ME（Maximum Entropy）挠说、最大熵馬爾可夫模型MEMM（Maximum-entropy Markov model）和條件隨機(jī)場(chǎng)CRF（Conditional Random Field）被分別提出（這也是我在開頭提到的澡谭，既然都開始分析語(yǔ)義了，自然可以把分詞和后續(xù)的語(yǔ)義分析過(guò)程結(jié)合在一起了）损俭。
這篇文章介紹了信息熵的概念蛙奖，信息熵越大不確定性也就越大，信息熵最大時(shí)表示各種概率的均等分布杆兵，也就是個(gè)不偏不倚的猜測(cè)雁仲，最大熵模型一般就是在已知條件下，來(lái)求是的熵最大的情況琐脏。
pˉ(f)=Σpˉ(ai,ci)?f(ai,ci)=p(f)=Σp(ci|ai)?pˉ(ai)?f(ai,ci)
在已知條件下就是求熵最大的情況
argmaxH(ci|ai)
因?yàn)檫@些算法我還沒有深入了解攒砖，就不繼續(xù)抄襲這篇文獻(xiàn)了，有興趣的同學(xué)可以去看看日裙，如果我有深入了解和新的理解之后之后過(guò)幾天再更新吹艇，并且會(huì)在這篇更新鏈接。
Deep Learning
這篇2013年的文獻(xiàn)已經(jīng)采用了Deep Learning的方法解決分詞問(wèn)題昂拂。具體而簡(jiǎn)潔地說(shuō)就是神經(jīng)網(wǎng)絡(luò)什么的受神，有空再深入挖掘。
（PS：昨天的Intro我沒忘政钟，不過(guò)今天晚上跟男神去電影院刷了一下<Big Hero 6>路克，所以明天再戰(zhàn)咯~）
That's all for today. See you tomorrow.
Kevin Ham@Wuhu
Department of Internet Engineering, Anhui Normal University, Wuhu, China
3.2.2015
