基于詞的關(guān)聯(lián)特征的中文分詞方法*

李康康，龍 華

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

0 引 言

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

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

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

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

2.1 算法流程圖

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

2.2 改進的中文算法步驟

2.2.1 構(gòu)建語料庫

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

圖1 算法流程

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

采用前后拼接詞的分詞方法，對語料庫進行分詞，形成二元候選詞庫、三元候選詞庫和四元候選詞庫。假設(shè)中文文本的內(nèi)容為S=A1A2…Ai…An{i≤n,n∈N+,N+表示自然數(shù)集}。其中，Ai表示為文本中的一個字符。當(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)計模式，本文通過正則表達式對文本進行詞頻統(tǒng)計。定義TF為候選詞的詞頻，TF0為詞頻門限。如果存在TF＞TF0，則將候選詞作為構(gòu)建新詞庫的一部分；如果不滿足此條件，則不考慮。

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

（1）自由度

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

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

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

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

（2）凝合度

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

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

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

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

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

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

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

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

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

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

3.1 建立語料庫

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

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

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

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

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

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

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

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

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

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

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

圖3 詞頻統(tǒng)計結(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)計的部分結(jié)果如圖4所示。

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

3.4 計算自由度和凝合度并進行判決

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 采用三元和四元分詞過濾方法對新詞庫進行過濾

3.5.1 三元分詞方法

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

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

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

3.5.2 四元分詞方法

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

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

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

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

表1 幾種中文分詞分詞方法實驗結(jié)果

從表1可以看出，文章提出的分詞算法相對于基于詞頻統(tǒng)計的分詞方法具有較高的相對正確率，能夠在一定程上解決中文分詞的問題，但是分詞的準(zhǔn)確度依然不高。因為文章提出的算法是基于大規(guī)模語料庫的，即語料庫規(guī)模越大，分詞的準(zhǔn)確率越高。

5 結(jié) 語

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