利用統(tǒng)計(jì)進(jìn)行中文分詞與詞性分析
添加評(píng)論[作者：
早晨 分類：
所有文章 ]
今天，翻出了我以前在本科階段寫(xiě)的一些論文，雖然有幾篇沒(méi)有發(fā)表。突然發(fā)現(xiàn)很多還是比較實(shí)用，雖然學(xué)術(shù)價(jià)值并不是很大，于是我重新整理了下，用最簡(jiǎn)單的方式，摘要了部分出來(lái)拼成此文，當(dāng)然拼的原料都是自己的，本文適合初學(xué)者，如若轉(zhuǎn)載，請(qǐng)著名版權(quán)。
中文分詞已經(jīng)是老調(diào)重彈的話題了，傳統(tǒng)的基于詞庫(kù)的分詞技術(shù)應(yīng)該是目前最基本的分詞技術(shù)，在這里我不去深入挖掘，什么好什么不好的問(wèn)題，今天我只想根據(jù)我自己的經(jīng)驗(yàn)，來(lái)設(shè)計(jì)和實(shí)現(xiàn)一套中文分詞與詞性分析的一套系統(tǒng)，系統(tǒng)其實(shí)已經(jīng)實(shí)現(xiàn)與Iveely Search Engine中。
我們采用隱馬爾可夫模型(HMM)來(lái)實(shí)現(xiàn)中文分詞和詞性分析。在使用HMM之前，我們先了解下HMM的基本內(nèi)容，然后在編碼上我們才知道為什么要這樣去寫(xiě)（這對(duì)讀編碼非常重要）。當(dāng)然會(huì)和code對(duì)比起來(lái)。
利用學(xué)院派的講解是這樣：隱馬爾可夫模型是馬爾可夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過(guò)觀測(cè)向量序列觀察到，每個(gè)觀測(cè)向量都是通過(guò)某些概率密度分布表現(xiàn)為各種狀態(tài)，每一個(gè)觀測(cè)向量是由一個(gè)具有相應(yīng)概率密度分布的狀態(tài)序列產(chǎn)生。也許看完這個(gè)，你一頭霧水，因?yàn)樵贜年前，我最開(kāi)始接觸HMM的時(shí)候，也是領(lǐng)悟了一段時(shí)間，當(dāng)然如果你很熟悉HMM，直接跳過(guò)。從工程的角度：
HMM的五元素(學(xué)術(shù)名)統(tǒng)計(jì)中含義(工程含義)
隱含狀態(tài)S詞有的4種隱含狀態(tài)：?jiǎn)巫殖稍~、詞頭、詞中、詞尾
觀察狀態(tài)O所有語(yǔ)料庫(kù)中的漢字
初始狀態(tài)概率矩陣Pi詞中各種隱含狀態(tài)的初始概率
隱含狀態(tài)轉(zhuǎn)移概率矩陣A4種隱含狀態(tài)的轉(zhuǎn)移概率，例如：詞頭到詞尾的轉(zhuǎn)移概率，是一個(gè)4*4的矩陣
觀察狀態(tài)轉(zhuǎn)移概率矩陣B語(yǔ)料庫(kù)中每一個(gè)漢字到4種隱含狀態(tài)的概率。例如：漢字“我”到詞頭的概率，到詞尾的概率。
第一步：統(tǒng)計(jì)HMM五種元素值
通過(guò)上圖的表，你似乎可以開(kāi)始工作了，但是你知道，沒(méi)有Corpus，這件事是做不好的，所以，Corpus的選擇，是非常好的，我們選用這個(gè)Corpus，下一步工作，我們就是利用工程學(xué)統(tǒng)計(jì)出上述五個(gè)元素的。
語(yǔ)料庫(kù)中的形式如下：
“…廢/B除/E 存/B在/E 的/S 所/B有/M制/E 關(guān)/B系/E 并/S 不/S 是/S 共/B產(chǎn)/M主/M義/E 所/S 獨(dú)/B具/E 的/S 特/B征/E…”
B表示：begin（詞頭），M表示：Middle（詞中），S表示Single（單字成詞），E表示End（詞尾），我想給你這樣一個(gè)語(yǔ)料庫(kù)，讓你統(tǒng)計(jì)上面五個(gè)元素的值，應(yīng)該不是什么問(wèn)題了。當(dāng)然我也會(huì)附加上主要的代碼：
private void Train(string corpus)
{
string[] states = new string[] { “單字成詞“, “詞頭“, “詞中“, “詞尾“ };
//添加隱含狀態(tài)
this.AddStates(states);
string[] sentences = corpus.Split(this.Delimiter.ToArray(), StringSplitOptions.RemoveEmptyEntries);
string lastwordType = states[0];
string currentWordType = string.Empty;
foreach (var sentence in sentences)
{
char[] list = sentence.ToArray();
for (int i = 0; i < list.Length; i = i + 3)
{
string word = list[i].ToString(CultureInfo.InvariantCulture);
string wordType = list[i + 2].ToString(CultureInfo.InvariantCulture).ToLower();
//添加觀察狀態(tài)元素
this.AddObserver(word);
if (wordType.Equals(“s“))
{
currentWordType = states[0];
}
else if (wordType.Equals(“e“))
{
currentWordType = states[3];
}
else if (wordType.Equals(“m“))
{
currentWordType = states[2];
}
else if (wordType.Equals(“b“))
{
currentWordType = states[1];
}
//初始狀態(tài)轉(zhuǎn)移矩陣
AddInitialStateProbability(currentWordType, 1);
//觀察狀態(tài)轉(zhuǎn)移矩陣
AddComplexProbability(currentWordType, word);
//隱含狀態(tài)轉(zhuǎn)移矩陣
AddTransferProbability(lastwordType, currentWordType, 1);
lastwordType = currentWordType;
}
}
}
第二步：維特比最佳路徑
維特比是什么？維特比算法是一種動(dòng)態(tài)規(guī)劃算法用于尋找最有可能產(chǎn)生觀測(cè)事件序列的-維特比路徑-隱含狀態(tài)序列,特別是在馬爾可夫信息源上下文和隱馬爾可夫模型中。術(shù)語(yǔ)“維特比路徑”和“維特比算法”也被用于尋找觀察結(jié)果最有可能解釋相關(guān)的動(dòng)態(tài)規(guī)劃算法。例如在統(tǒng)計(jì)句法分析中動(dòng)態(tài)規(guī)劃算法可以被用于發(fā)現(xiàn)最可能的上下文無(wú)關(guān)的派生(解析)的字符串，有時(shí)被稱為“維比特分析”。
有了上面維特比的基礎(chǔ)知識(shí)以及統(tǒng)計(jì)完HMM的基本五種元素之后，你會(huì)很納悶，這五種元素計(jì)算出來(lái)后，意義是什么？如何利用它解決分詞問(wèn)題？下面的問(wèn)題，我們以一個(gè)實(shí)例來(lái)解說(shuō)：用戶輸入了關(guān)鍵字“Iveely 是一款開(kāi)源的搜索引擎。” 我們?cè)撊绾畏衷~（解碼過(guò)程）？
首先，將輸入詞組分為一個(gè)Array：
Iveely是一款開(kāi)源搜索引擎
SSSSSSSSSS
BBBBBBBBBB
MMMMMMMMMM
EEEEEEEEEE
那么分詞的作用就是，在每一個(gè)詞有不同的狀態(tài)的時(shí)候，怎么使得他們的概率最大？這就變成了一個(gè)路徑選擇問(wèn)題。我們可以不利用維特比算法來(lái)解決，因?yàn)楸┝Ψ椒ㄒ欢ㄊ且粋€(gè)解決思路，但是算法效率太低，每個(gè)字有4種狀態(tài)，假設(shè)10個(gè)字，就有4的10次方計(jì)算量，然后取出概率最大的那一組就是我們所求的最佳路徑。但是我們需要高效率解決這些問(wèn)題，所以維特比是一種常用的方式。維比特怎么解決這個(gè)問(wèn)題的呢？參考
這里 （我開(kāi)始寫(xiě)了很多，但是都不如這位兄弟專業(yè),偷個(gè)小懶啦，哈哈 ^_^）
當(dāng)然，我不會(huì)吝嗇的保存自己的代碼，Share 給大家：
public int[] Decode(string[] input, out double probability)
{
int inputLength = input.Length;
int stateCount = this.state.Length;
int minState;
double minWeight;
int[,] s = new int[stateCount,inputLength];
double[,] a = new double[stateCount,inputLength];
for(int i = 0; i < stateCount; i++)
{
object obj = complex.Table[this.state[i]][input[0]];
if(obj != null)
{
a[i, 0] = (1.0*Math.Log(initialState[this.state[i]])) -
Math.Log(double.Parse(obj.ToString()))
;
}
}
for(int t = 1; t < inputLength; t++)
{
for(int j = 0; j < stateCount; j++)
{
minState = 0;
minWeight = a[0, t - 1] -
Math.Log(double.Parse(this.transition.Table[this.state[0]][this.state[j]].ToString()));
for(int i = 0; i < stateCount; i++)
{
double weight = a[i, t - 1] -
Math.Log(double.Parse(this.transition.Table[this.state[i]][this.state[j]].ToString()));
if(weight < minWeight)
{
minState = i;
minWeight = weight;
}
}
object obj = complex.Table[this.state[j]][input[t]];
if(obj != null)
{
a[j, t] = minWeight – Math.Log(double.Parse(obj.ToString()));
s[j, t] = minState;
}
}
}
minState = 0;
minWeight = a[0, inputLength - 1];
for(int i = 1; i < stateCount; i++)
{
if(a[i, inputLength - 1] < minWeight)
{
minState = i;
minWeight = a[i, inputLength - 1];
}
}
int[] path = new int[input.Length];
path[inputLength - 1] = minState;
for(int m = inputLength – 2; m >= 0; m–)
{
path[m] = s[path[m + 1], m + 1];
}
probability = Math.Exp(-minWeight);
return path;
}
利用維特比算法，它返回了一個(gè)路徑數(shù)組，數(shù)組是一個(gè)長(zhǎng)度跟我們輸入的字符串的長(zhǎng)度一樣，數(shù)組值是0-3的隱含狀態(tài)，表示該次更屬于哪一個(gè)狀態(tài)，通過(guò)維特比算法處理后，將詞與狀態(tài)路徑合并，我們可以得到這樣的一張表：
Iveely是一款開(kāi)源搜索引擎
SSSSSSSSSS
BBBBBBBBBB
MMMMMMMMMM
EEEEEEEEEE
我想看到上面的表，你已經(jīng)知道具體的含義了，不用我多說(shuō)吧？呵呵，讓我們看看程序跑完的截圖吧：
上面，講完了基本的分詞后，你一定想知道，我們?cè)趺醋鲋形脑~性分析，在自然語(yǔ)言處理(NLP)中，詞性分析難度是很大的，目前據(jù)我所知，
哈工大NLP實(shí)驗(yàn)室的，感覺(jué)還挺不錯(cuò)，而且是開(kāi)源。好了，繼續(xù)我們的詞性分析。
第一步：分詞
幸運(yùn)的是，我們上面已經(jīng)做好了分詞，那么用戶給定的輸入，我們已經(jīng)切分好詞了：”iveely/是/一款/開(kāi)源/搜索引擎/“。
第二步：統(tǒng)計(jì)學(xué)習(xí)
對(duì)，我們?cè)俅芜M(jìn)行統(tǒng)計(jì)學(xué)習(xí)，依然利用HMM，不過(guò)語(yǔ)料庫(kù)變了，我們利用1998年01月份人民日?qǐng)?bào)的語(yǔ)料庫(kù)，大致形式如下：
”…邁向/v 充滿/v 希望/n 的/u 新/a 世紀(jì)/n ——/w 一九九八年/t 新年/t 講話/n （/w 附/v 圖片/n １/m 張/q ）/w …”
每一個(gè)詞的后面都有一個(gè)詞性，詞性表？查看
這里是不是感覺(jué)跟分詞的時(shí)候統(tǒng)計(jì)類似？看看下表你就知道了：
HMM的五元素(學(xué)院名)統(tǒng)計(jì)中含義(工程含義)
隱含狀態(tài)S詞有的N種隱含狀態(tài)：名詞、動(dòng)詞、介詞…
觀察狀態(tài)O所有語(yǔ)料庫(kù)中的詞語(yǔ)
初始狀態(tài)概率矩陣Pi詞中各種隱含狀態(tài)的初始概率
隱含狀態(tài)轉(zhuǎn)移概率矩陣AN種隱含狀態(tài)的轉(zhuǎn)移概率，例如：動(dòng)詞到到名詞的轉(zhuǎn)移概率。
觀察狀態(tài)轉(zhuǎn)移概率矩陣B語(yǔ)料庫(kù)中每一個(gè)詞語(yǔ)到N種隱含狀態(tài)的概率。例如：漢字“我”是名詞的概率。
我想看到這里，大家都應(yīng)該很清楚了。后面利用維特比算法解碼，算出給定的路徑，然后將詞性附加給我們的詞組。
作者說(shuō):HMM并不是一種很完美的方法，只是從某種角度，它可以做分詞，可以做詞性分析，所有的code，點(diǎn)擊
這里查看，當(dāng)然效果需要不斷調(diào)整和修復(fù)。還有很多網(wǎng)友發(fā)郵件問(wèn)我，為何IveelySE 0.4.0還沒(méi)有發(fā)布，原因是很多方面的，最重要的是準(zhǔn)確率上不去，不忍心將效果很差的智能搜索給大家，但是在繼續(xù)整改之后，我也期待早日和大家分享。謝謝一直以來(lái)對(duì)IveelySE支持的朋友。
————————————————————
我的郵箱：
liufanping@iveely.com我的微博：
weibo.com/liufanping世界上最快樂(lè)的事情，莫過(guò)于為理想而奮斗
