李康康，龍 華

（昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650000）

0 引 言

中文分詞是中文自然語言處理中最基本的一個(gè)步驟。對于一句話，人可以通過自己的知識(shí)來明白哪些是詞，哪些不是詞。但是，如何讓計(jì)算機(jī)也能理解呢?處理過程就是分詞算法?，F(xiàn)在已有的計(jì)算機(jī)自動(dòng)切分詞算法大致可分為三類：基于理解的分詞方法、基于字符串匹配的分詞方法和基于傳統(tǒng)詞頻統(tǒng)計(jì)的分詞方法

基于理解的分詞方法[1]，是通過讓計(jì)算機(jī)模擬人對句子的理解，達(dá)到識(shí)別詞的效果。它在分詞的同時(shí)進(jìn)行句法、語義分析，利用句法信息和語義信息處理歧義現(xiàn)象。這種分詞方法需要使用大量的語言知識(shí)和信息。由于漢語語言知識(shí)的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機(jī)器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗(yàn)階段。

基于字符串匹配的分詞方法[2]，是按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別出一個(gè)詞）。按照不同長度優(yōu)先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ疃蹋┢ヅ?。最大匹配法的優(yōu)點(diǎn)是原理簡單，易于實(shí)現(xiàn)；缺點(diǎn)是最大匹配長度不易確定，若太大則時(shí)間復(fù)雜度上升，太小則有些超過該長度的詞無法匹配，降低了分詞的準(zhǔn)確率。

基于傳統(tǒng)詞頻統(tǒng)計(jì)的分詞方法[3]，從形式上看，詞是穩(wěn)定的字的組合，因此在上下文中，相鄰的字同時(shí)出現(xiàn)的次數(shù)越多，越有可能構(gòu)成一個(gè)詞。因此，字與字相鄰共現(xiàn)的頻率或概率能夠較好地反映成詞的可信度?？梢越y(tǒng)計(jì)語料中相鄰共現(xiàn)的各個(gè)字的組合頻度，計(jì)算它們的互現(xiàn)信息。定義兩個(gè)字的互現(xiàn)信息，計(jì)算兩個(gè)漢字X、Y的相鄰共現(xiàn)概率?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當(dāng)緊密程度高于某一個(gè)閾值時(shí)，可認(rèn)為此字組可能構(gòu)成了一個(gè)詞。這種方法只需對語料中的字組頻度進(jìn)行統(tǒng)計(jì)，不需要切分詞典，因而又叫做無詞典分詞法或統(tǒng)計(jì)取詞方法。這種方法也有一定的局限性，會(huì)經(jīng)常抽出一些共現(xiàn)頻度高但并不是詞的常用字組，如“這一”“之一”“有的”“我的”“許多的”等，且對常用詞的識(shí)別精度差、時(shí)空開銷大。

因此，本文提供一種基于詞的關(guān)聯(lián)特征的中文分詞方法，用以解決現(xiàn)有技術(shù)中無法從大規(guī)模語料中有效識(shí)別并提取詞的缺陷，實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)在大規(guī)模語料中的有效識(shí)別并提取詞。

1 相關(guān)概念

定義1 前后拼接詞的分詞方法：設(shè)字符串S={A1A2…Ai…An}{i≤n,n∈N+,N+表示自然數(shù)集}。其中，Ai表示字符串S中第i個(gè)字符，令S的子串為Si={Ai…Ai+m}，依次統(tǒng)計(jì)出當(dāng)m=1、2、3時(shí)出現(xiàn)的所有子串。

定義2 自由度：當(dāng)一個(gè)文本片段出現(xiàn)在各種不同的文本集中，且具有左鄰字集合和右鄰字集合時(shí)（左鄰字集合是指出現(xiàn)在文本片段左邊相鄰的字符的集合；右鄰字集合是指出現(xiàn)在文本片段右邊相鄰的字符的集合），假如文本片段{Aij+1Aij+2}在文本集合{AijAij+1Aij+2Aij+3Aij+4Aij+4…Aij-1+nAij+n}中，則左鄰字集合為{Aij}，右鄰字集合為{Aij+3}，其中i指代文本片段集合中元素的序號，j指代構(gòu)成一個(gè)文本片段的序號。通過計(jì)算左鄰字集合和右鄰字集合的信息熵[4]獲取一個(gè)文本片段的信息熵，取左鄰字集合和右鄰字集合中較小信息熵作為自由度。

定義3 凝合度：是指在一個(gè)文本S={A1A2…Ai…An}{i≤n,n∈N+,N+表示自然數(shù)集}中，一個(gè)候選詞詞Si={Ai…Ai+m}單獨(dú)出現(xiàn)的概率高于組合其每一部分{Ai+m}的概率的乘積，即P(S)＞P(Ai)Ai+mP(Ai+m)。令，取最小的m為凝合度，其中表示一個(gè)新詞，P(Si)表示一個(gè)詞在文本中出現(xiàn)的概率，Ai和Ai+m指代組合候選詞的兩部分，P(Ai)和P(Ai+m)分別代表候選詞每一部分在文本中出現(xiàn)的概率。

定義4 三元候選詞的過濾方法：對于三元候選詞，若后兩個(gè)字符存在于二元候選詞庫中，判斷第一個(gè)字是否與左鄰接字構(gòu)成一個(gè)詞，若前兩個(gè)字符存在于二元候選詞庫中，判斷最后一個(gè)字是否與右鄰接字構(gòu)成一個(gè)詞，確定三元候選詞是否是三元詞。若：

則(Ai-1AiAi+1)屬于三元詞。其中，(Ai-1AiAi+1)屬于三元候選詞，Ai-2是三元候選詞的左鄰字，Ai+2是三元候選詞的右鄰接字，{A0…Ai…AN}是語料庫中的字符集合，{(A0,A1)…(Ai,Ai+1)…(Ai-2,Ai-1)}是二元候選詞集合。

定義5 四元后選詞的過濾方法：對可能成詞的四元候選詞，首先進(jìn)行分割，前兩個(gè)字為一個(gè)分詞片段，后兩個(gè)字為另一個(gè)分詞片段，并分別對分詞片段與已分好的二元詞庫進(jìn)行匹配。成功匹配的，則作為預(yù)選詞。然后，在對四元詞的中間兩個(gè)字進(jìn)行分割，并與已分好的二元詞庫進(jìn)行匹配。匹配不成功的，則作為預(yù)選詞。如果兩個(gè)條件都滿足，則作為分詞的結(jié)果。

2 基于詞的關(guān)聯(lián)特征的分詞算法

2.1 算法流程圖

為了便于理解和描述本文使用的算法，采用常規(guī)的流程圖，如圖1所示，包括11個(gè)模塊，最終實(shí)現(xiàn)了分詞效果。

2.2 改進(jìn)的中文算法步驟

2.2.1 構(gòu)建語料庫

為了能夠使改進(jìn)的分詞算法在效率、分詞的長度限制甚至歧義處理上得到提高，必須要有一個(gè)語料庫。首先需要對其進(jìn)行預(yù)處理，包括去符號，然后將各個(gè)段落連接成一條語句，構(gòu)建語料庫[5]。

圖1 算法流程

2.2.2 構(gòu)建候選詞庫

采用前后拼接詞的分詞方法，對語料庫進(jìn)行分詞，形成二元候選詞庫、三元候選詞庫和四元候選詞庫。假設(shè)中文文本的內(nèi)容為S=A1A2…Ai…An{i≤n,n∈N+,N+表示自然數(shù)集}。其中，Ai表示為文本中的一個(gè)字符。當(dāng)文本A被切分為所有{Ai,Ai+1}的組合的集合，稱其為二元候選詞庫，其中i∈N。當(dāng)文本A被切分為所有{Ai,Ai+1Ai+2}的組合的集合，稱其為三元候選詞庫。當(dāng)文本A被切分為{Ai,Ai+1Ai+2Ai+3}的組合的集合，稱其為四元候選詞庫。

2.2.3 新詞庫的構(gòu)建

新詞庫由候選詞和詞頻組成。根據(jù)傳統(tǒng)的統(tǒng)計(jì)模式，本文通過正則表達(dá)式對文本進(jìn)行詞頻統(tǒng)計(jì)。定義TF為候選詞的詞頻，TF0為詞頻門限。如果存在TF＞TF0，則將候選詞作為構(gòu)建新詞庫的一部分；如果不滿足此條件，則不考慮。

2.2.4 基于自由度和擬合度的詞的判決

（1）自由度

自由度是通過計(jì)算并選擇候選詞左右鄰字集信息熵小者得到的：

其中，H表示候選詞的自由度，s′表示候選詞的右熵，n表示左鄰字集合元素總數(shù)。

其中，{bi|i＜K}屬于候選詞的右鄰字集，nAi表示Ai出現(xiàn)在候選詞右邊的頻數(shù)，K表示候選詞的右鄰字集中字元素個(gè)數(shù)，s′′為候選詞的左熵；

其中，{mi|i＜M}屬于候選詞的左鄰字集，nmi表示mi出現(xiàn)在候選詞左邊的頻數(shù)，M表示候選詞的左鄰字集中字元素個(gè)數(shù)，n表示右鄰字集合元素的總數(shù)。

（2）凝合度

凝合度是通過計(jì)算語料中候選詞的獨(dú)立概率和聯(lián)合概率的比值得到，具體步驟如下。

①由候選詞的概率和候選詞的組合概率的比值得到兩元候選詞凝合度M2：

其中，M2表示候選詞的凝合度，Si表示兩元候選詞的第一個(gè)字在語料庫中出現(xiàn)的概率，Si+1表示兩元候選詞第二個(gè)字在語料庫中出現(xiàn)的概率，p(i,i+1)表示兩元候選詞語在語料中出現(xiàn)的概率。

②由候選詞的概率和候選詞的組合概率的比值得到三元候選詞凝合度M3：

其中，M3表示候選詞的凝合度，Si表示三元候選詞的第一個(gè)字在語料庫中出現(xiàn)的概率，Si+1,Si+2表示三元候選詞的后兩個(gè)字同時(shí)在語料庫中出現(xiàn)的概率，Si,i+1表示三元候選詞的前兩個(gè)字同時(shí)在語料庫中出現(xiàn)的概率，Si+2表示三元候選詞的最后一個(gè)字在語料庫中出現(xiàn)的概率，P(i,i+1,i+2)表示三元候選詞語在語料中出現(xiàn)的概率。

③由候選詞的概率和候選詞的組合概率的比值得到四元候選詞凝合度M4：

其中，M4表示候選詞的凝合度，Si表示四元候選詞的第一個(gè)字在語料庫中出現(xiàn)的概率，Si+1,Si+2,Si+3表示四元候選詞的后三個(gè)字同時(shí)在語料庫中出現(xiàn)的概率，Si,Si+1,Si+2表示四元候選詞的前三個(gè)字同時(shí)在語料庫中出現(xiàn)的概率，Si,i+1表示四元候選詞的前兩個(gè)字在語料庫中出現(xiàn)的概率，Si+2,i+3表示四元候選詞的后兩個(gè)字在語料庫中出現(xiàn)的概率，P(i,i+1,i+2,i+3)表示四元候選詞在語料庫中出現(xiàn)的概率。

2.2.5 采用三元和四元分詞過濾方法

采用分詞過濾方法對篩選出來的三元候選詞和四元候選詞進(jìn)行進(jìn)一步過濾，形成最終的詞庫。

3 基于特征的分詞算法在對《西游記》分詞中的應(yīng)用

3.1 建立語料庫

步驟1：利用While(sequence=br.readLine())讀取語料庫中的每一句。

步驟2：利用Link(Delete(sequene.contains(chat)))刪除語句中的標(biāo)點(diǎn)符號并連成一句話。部分《西游記》[6]經(jīng)過文本處理的結(jié)果如圖2所示。

圖2 文本處理結(jié)果

3.2 構(gòu)建候選詞庫

本文通過采用正則表達(dá)式[7]，對文本進(jìn)行詞頻統(tǒng)計(jì)。

（1）While((line=br.readLine())!=null)讀取文本集合中的每一行；

（2）Matcher m=p.matcher(line)通過引入正則表達(dá)式對每一行進(jìn)行處理；

（3）如果if(map.containsKey(data))滿足正則表達(dá)式；

（4）map.put(data,count+1)加 1；

（5）重復(fù)以上步驟，分別統(tǒng)計(jì)文本集合中的二元候選詞、三元候選詞和四元候選詞。判別二元候選詞正則表達(dá)式為[u4e00-u9fa5]{2}，判別三元候選詞正則表達(dá)式為[u4e00-u9fa5]{3}，判別四元候選詞正則表達(dá)式為[u4e00-u9fa5]{4}。

對文本進(jìn)行詞頻統(tǒng)計(jì)的部分結(jié)果，如圖3所示。

圖3 詞頻統(tǒng)計(jì)結(jié)果

3.3 構(gòu)建新詞庫

定義TF為候選詞的詞頻，TP0為詞頻門限，如果存在TF≤TF0，則將候選詞作為構(gòu)建新詞庫的一部分；如果不滿足此條件，則不考慮。

（1）While(word=br.readline())讀取候選語料庫的每一行；

（2）If(TF=word.value()＞TP0)大于門限值；

（3）yList.add(word)，存到列表中。

統(tǒng)計(jì)的部分結(jié)果如圖4所示。

圖4 統(tǒng)計(jì)的部分結(jié)果

3.4 計(jì)算自由度和凝合度并進(jìn)行判決

3.4.1 計(jì)算自由度實(shí)現(xiàn)過程及部分最后結(jié)果

（1）If(i=str,contains(sequence))在一個(gè)句子中存在候選詞，將其所在位置返回i；

（2）List.add(i-1)統(tǒng)計(jì)與其左邊相鄰的字；

（3）List2.add(i+1)統(tǒng)計(jì)與其右邊相鄰的字；

（4）Sum( List.get()/Sum(List))計(jì)算其左熵；

（5）Sum(List.get()/Sum(List2))計(jì)算其右熵；

（6）Min(Sum( List.get()/Sum(List))，Sum( List.get()/Sum(List2)))。

圖5為自由度部分的最后結(jié)果。

圖5 自由度部分最后結(jié)果

3.4.2 計(jì)算凝合度實(shí)現(xiàn)過程及部分最后結(jié)果

（1）While(word=br.readline())讀取新詞庫的每一個(gè)詞；

（2）number1=count(Word.get())計(jì)算構(gòu)成詞的第一部分在語料庫中出現(xiàn)的次數(shù)；

（3）number2=count(Word.other())計(jì)算構(gòu)成詞的另外一部分在語料庫中出現(xiàn)的次數(shù)；

（4）number3=count(Word)計(jì)算構(gòu)完整詞在語料庫中出現(xiàn)的次數(shù)；

（5）number4=count(text)計(jì)算整個(gè)語料庫字符出現(xiàn)的個(gè)數(shù)。Min((number1/number4)/(number2/number4))/(number3/number4)，計(jì)算凝合度。

圖6為凝合度部分的最后結(jié)果。

圖6 凝合度部分最后結(jié)果

3.4.3 分別給自由度和凝合度一個(gè)門限，滿足條件的作為新詞庫

自由度和凝合度的門限是動(dòng)態(tài)獲取的。針對不同的語料庫給出的自由度和凝合度門限值是不同的，本文采用的語料庫是四大名著之一《西游記》。通過多次進(jìn)行實(shí)驗(yàn)比較，選出了效果最好的自由度和凝合度門限值。

（1）Zthreshold=10;//初始化自由度門限值Mthreshold=20;//初始化擬合度門限值

（2）If(text(Zthreshold,Mthresold).getWords())

LastText(Zthresold,Mthresold).getwords()&&words.accuracy()＞lastwords.accuracy())

{Zthresold++;Mthreshold++;}//如果根據(jù)當(dāng)前的自由度和凝合度的門限值所獲取的詞庫和正確率大于前一個(gè)門限值所獲取的詞庫和正確率，將自由度和凝合度進(jìn)行自加，直至不滿足條件，結(jié)束。

3.5 采用三元和四元分詞過濾方法對新詞庫進(jìn)行過濾

3.5.1 三元分詞方法

（1）While(word=br.readLine())讀取三元詞庫的每一個(gè)詞；

（2）arr= Word.split(i)將三元詞分成兩部分，第一部分為第一個(gè)字，第二部分為末尾兩個(gè)字；

（3）if(arr[1].exist(2-gram)&&arr[1]+arr[0]not word)第二部分存在二元新詞庫，且第一部分與其前一個(gè)字符不存在二元語料庫，則判定為一個(gè)詞。

3.5.2 四元分詞方法

（1）While(word=br.readLine())讀取四元詞庫的每一個(gè)詞；

（2）arr=Word.split()將四元詞分成兩部分，第一部分為前兩個(gè)字符，第二部分為后兩個(gè)字符；

（3）If(arr[0].exist(2-gram)&&arr[1]exist(2-gram)&&(arr[0][2]+arr[1][1])not in 2-gram)，四元詞的第一部分存在于二元新詞庫，且第二部分也存在二元詞庫，但四元詞的中間兩個(gè)字構(gòu)成的詞不存在二元新詞庫，則將其作為新詞庫。

3.6 采用基于詞的關(guān)聯(lián)特征的分詞方法所取得的分詞結(jié)果

通過采用本文提出的基于詞的關(guān)聯(lián)特征的分詞算法，對四大名著《西游記》進(jìn)行了分詞處理，部分結(jié)果如圖7所示。

3.7 采用基于詞頻統(tǒng)計(jì)的分詞方法所取得的分詞結(jié)果

傳統(tǒng)的基于詞頻統(tǒng)計(jì)的中文分詞方法步驟由本文提出方法的前三步組成，所以這里不再重復(fù)。圖8為基于詞頻統(tǒng)計(jì)的中文分詞方法對四大名著《西游記》進(jìn)行了分詞后，部分分詞結(jié)果。

圖7 基于詞的關(guān)聯(lián)特征的分詞方法所取得的分詞結(jié)果

圖8 基于詞頻統(tǒng)計(jì)的中文分詞方法所取得的分詞結(jié)果

4 實(shí)驗(yàn)結(jié)果分析

為了比較幾種分詞方法在中文分詞中的效果，本文提出了相對準(zhǔn)確率[8]作為比較指標(biāo)。

相對準(zhǔn)確率按照如下方法計(jì)算：

準(zhǔn)確率=識(shí)別出的詞語總數(shù)出現(xiàn)在標(biāo)準(zhǔn)結(jié)果中的詞語數(shù)/標(biāo)準(zhǔn)結(jié)果中的詞語總數(shù)×100% （8）

其中標(biāo)準(zhǔn)結(jié)果是指海量分詞的結(jié)果，實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 幾種中文分詞分詞方法實(shí)驗(yàn)結(jié)果

從表1可以看出，文章提出的分詞算法相對于基于詞頻統(tǒng)計(jì)的分詞方法具有較高的相對正確率，能夠在一定程上解決中文分詞的問題，但是分詞的準(zhǔn)確度依然不高。因?yàn)槲恼绿岢龅乃惴ㄊ腔诖笠?guī)模語料庫的，即語料庫規(guī)模越大，分詞的準(zhǔn)確率越高。

5 結(jié) 語

在進(jìn)行中文文本分詞的研究工作中，本文提出了一種基于詞的關(guān)聯(lián)特征的中文算法。首先計(jì)算出可能成詞的文本片段的詞頻、自由度和凝合度，然后采用閾值過濾的方法，過濾掉不滿足條件的文本片段。之后，對三元詞和四元次采用過濾方法，過濾掉不可靠的三元詞和四元詞，以提高分詞算法的正確率。