基于Aho-Corasick自動機(jī)算法的概率模型中文分詞CPACA算法

徐懿彬

?

基于Aho-Corasick自動機(jī)算法的概率模型中文分詞CPACA算法

徐懿彬

(女王大學(xué)工程與應(yīng)用科學(xué)學(xué)院加拿大安大略省金斯頓市 K7L 3N6)

Aho-Corasick自動機(jī)算法是著名的多模式串匹配算法，它在模式串失配時(shí)，通過fail指針轉(zhuǎn)移至有效的后續(xù)狀態(tài)，存在一個或多個有效的后續(xù)狀態(tài)可能。據(jù)此特性，該文提出了一種適應(yīng)于中文分詞的自動機(jī)算法。該算法使用動態(tài)規(guī)劃的方法，計(jì)算上下文匹配概率，轉(zhuǎn)移至最佳的有效后續(xù)狀態(tài)，即實(shí)現(xiàn)了基于字符串匹配的機(jī)械分詞方法與基于統(tǒng)計(jì)概率模型的方法結(jié)合。實(shí)驗(yàn)結(jié)果表明，該算法分詞準(zhǔn)確率高。

AC自動機(jī); 中文分詞; 動態(tài)規(guī)劃; Trie樹

詞是最小的能獨(dú)立運(yùn)行的語言單位，因此中文分詞是自然語言處理的第一步，它廣泛應(yīng)用于機(jī)器翻譯、搜索引擎、拼音輸入法、文章關(guān)鍵詞提取、漢語語音合成、數(shù)據(jù)挖掘等領(lǐng)域。中文分詞主要可以分為機(jī)械分詞和統(tǒng)計(jì)學(xué)分詞兩類。

機(jī)械分詞利用詞典作為主要的資源，將字符串以特定規(guī)則與詞典中的詞條比對，得出切分方案。此類分詞方法根據(jù)掃描方向和匹配規(guī)則的不同，有最大正向匹配法、最大逆向匹配法、最小切分法等，但此類分詞方法有兩個缺點(diǎn)：1) 對交集型歧義、組合型歧義和真歧義三類歧義句子的檢測、糾正能力低：使用正向最大匹配法的錯誤分詞率為1/169，逆向最大匹配法的錯誤切分率為1/245[1-2]；2) 分詞準(zhǔn)確性和效率受到詞庫容量的約束。為解決這兩個問題，近年來已有諸多方法被提出，文獻(xiàn)[3]和文獻(xiàn)[4]分別提出了一種消除交集型歧義的方法；文獻(xiàn)[5]給出了一種基于分詞排序的消除歧義算法；文獻(xiàn)[6]提出了一種基于最大匹配法、取得96.7%分詞準(zhǔn)確率的算法。

統(tǒng)計(jì)學(xué)分詞是根據(jù)模式串在字符串中與上下文聯(lián)合出現(xiàn)的概率來構(gòu)建統(tǒng)計(jì)模型，從而決定分詞的方案。統(tǒng)計(jì)分詞方法不受詞庫容量大小的約束，能有效地減小切分歧義、識別未登錄詞(新詞、怪詞)。但在跨領(lǐng)域方面存在不足，需要針對不同領(lǐng)域進(jìn)行不同的語料訓(xùn)練。此類分詞算法有如互信息、N元文法模型、神經(jīng)網(wǎng)絡(luò)模型和隱馬爾可夫模型等[7]；統(tǒng)計(jì)學(xué)分詞的算法有如文獻(xiàn)[8-10]等?？筛鶕?jù)是否需要人工處理過的語料，將統(tǒng)計(jì)學(xué)算法分為監(jiān)督學(xué)習(xí)模型和無監(jiān)督學(xué)習(xí)模型兩種。有監(jiān)督學(xué)習(xí)模型需要大量人工處理過的語料，取得準(zhǔn)確的語料需要很高的人力物力，而無監(jiān)督學(xué)習(xí)模型可以輕易地使用大量未經(jīng)處理過的資源，但就分詞準(zhǔn)確率而言，文獻(xiàn)[11]提出的通過改進(jìn)VE算法并結(jié)合BVE和MDL (minimum description length)是VE算法中最好成績的算法，以及文獻(xiàn)[12]提出的ESA被認(rèn)為是目前中文語料上效果最好的無監(jiān)督分詞方法[13]，這些算法的分詞準(zhǔn)確度相較于有監(jiān)督學(xué)習(xí)模型的分詞效果還有一定差距[11-13]。

通常，詞典和未處理過的語料等材料可以輕易地獲取，如果可以把有監(jiān)督分詞、無監(jiān)督分詞方法和機(jī)械分詞方法結(jié)合起來，則可以在分詞準(zhǔn)確率與語料規(guī)模之間找到平衡點(diǎn)。

為更好地提高中文分詞的準(zhǔn)確度，本文提出基于Aho-Corasick automation(AC自動機(jī))的概率模型中文分詞CPACA算法(a Chinese word segmentation algorithm of probability model based on Aho-Corasick automata algorithm)，采用動態(tài)規(guī)劃的方法處理，結(jié)合上下文來失配轉(zhuǎn)移，同時(shí)使用無監(jiān)督學(xué)習(xí)語料與有監(jiān)督學(xué)習(xí)語料，將基于統(tǒng)計(jì)的分詞法與基于字符串匹配的分詞方法相結(jié)合，加強(qiáng)了消除歧義、識別未登錄詞的能力，提高了分詞的準(zhǔn)確度。

1 相關(guān)概念

定義1 交集型歧義和組合型歧義：設(shè)字符串=12…A…A+m…A…A+n…A(,,,∈{|1≤≤,∈+},-≥2，+表示自然數(shù)集)，其中A表示字符串中第個字符(∈[1，])。令的子串1=…+…，2=+……+，3=1∩2(3≠)。如果滿足S1、S2皆為詞，則稱為交集型歧義字符串。令的子串3=…+n，4=+…，(3ì4)如果滿足3是詞，4也是詞，則稱為子集型歧義字符串。

定義2 結(jié)點(diǎn)路徑和結(jié)點(diǎn)長度：從根節(jié)點(diǎn)(root)到某個特定結(jié)點(diǎn)，經(jīng)過的結(jié)點(diǎn)集合稱為這個結(jié)點(diǎn)的結(jié)點(diǎn)路徑。經(jīng)過結(jié)點(diǎn)的總數(shù)稱為這個結(jié)點(diǎn)的結(jié)點(diǎn)長度。

定義3 后綴結(jié)點(diǎn)：設(shè)結(jié)點(diǎn)E，若存在結(jié)點(diǎn)E，使得E∈({E,E})，都有–≥0，則稱E為E的后綴結(jié)點(diǎn)。其中，結(jié)點(diǎn)E的路徑為123…a；結(jié)點(diǎn)E的路徑為123…b(<)，且滿足a=b,∈{|1≤≤,∈N}；結(jié)點(diǎn)E路徑為12?c(<)，且滿足a=c,∈{|1≤≤,∈N}。

定義4 匹配點(diǎn)和匹配性：若一個結(jié)點(diǎn)的結(jié)點(diǎn)路徑與一個模式串的結(jié)點(diǎn)路徑相等，稱這個結(jié)點(diǎn)為匹配點(diǎn)。對于一個結(jié)點(diǎn)，如果它是匹配點(diǎn)或者它的后綴結(jié)點(diǎn)是匹配點(diǎn)，則認(rèn)為該結(jié)點(diǎn)具有匹配性。

定義5 有限自動機(jī)[14]：一個五元組=(,,,0,) 稱為五元組自動機(jī)，其中：是狀態(tài)的有限集合(所有Tire 樹上的結(jié)點(diǎn))；是有限輸入字母表(模式串集合)；是一個從×到的函數(shù)，稱作的轉(zhuǎn)移函數(shù)，這個函數(shù)指向下一個狀態(tài)；0∈指的是初始結(jié)點(diǎn)(Tire樹上的根結(jié)點(diǎn)以及無關(guān)點(diǎn))；∈指的是自動機(jī)上的匹配點(diǎn)(接受狀態(tài))。

定義6 最長后綴模式子串[14]：設(shè)有結(jié)點(diǎn)E，若E∈，E∈({E,E})，都有–≥0，則12…b構(gòu)成的串叫作結(jié)點(diǎn)E的最長后綴模式子串；定義結(jié)點(diǎn)E結(jié)點(diǎn)E的模式后綴結(jié)點(diǎn)。其中，結(jié)點(diǎn)E的路徑為12…a；結(jié)點(diǎn)E的路徑為12…b(<)，且滿足a=b,∈{|1≤≤,∈N}，并使得12…b構(gòu)成的串是模式串集合中的一個串；結(jié)點(diǎn)E的路徑為12…c(<)，同時(shí)滿足a?=c,∈{|1≤≤,∈}，并讓12…c構(gòu)成的串是模式串集合中的一個串。

定義7 耦合度和存在度：在封閉語料庫(有監(jiān)督)中，分別以表示結(jié)點(diǎn)路徑、結(jié)點(diǎn)路徑出現(xiàn)的次數(shù)，表示結(jié)點(diǎn)路徑與結(jié)點(diǎn)路徑作為兩個相連的詞出現(xiàn)的次數(shù)，令，則稱為與的耦合度。在開放語料庫(無監(jiān)督)中，分別以表示結(jié)點(diǎn)路徑、結(jié)點(diǎn)路徑出現(xiàn)的次數(shù)，表示結(jié)點(diǎn)路徑與結(jié)點(diǎn)路徑相連出現(xiàn)的次數(shù)，令，則稱為與的存在度。

2 CPACA中文分詞算法

2.1 CPACA中文分詞算法的定義及步驟

定義8 CPACA中文分詞算法：設(shè)字符串=12…A(∈+)，其中A表示字符串中第個字(∈[1,])；設(shè)A的匹配點(diǎn)集合為T=12…B(∈+)，T按結(jié)點(diǎn)長度降序排序，匹配點(diǎn)集合使用Aho-Corasick Automation算法取得，表示分詞進(jìn)行到個字符時(shí)，恰以T的第個匹配點(diǎn)B為結(jié)尾的匹配概率，；表示B對應(yīng)的結(jié)點(diǎn)路徑；表示B的結(jié)點(diǎn)長度(∈[1,])。的匹配概率為：，其中，為的匹配點(diǎn)集合中選中的匹配點(diǎn)編號，對于每個：1) 當(dāng)時(shí)，temp=0；2) 當(dāng)時(shí)，，其中，g為的匹配點(diǎn)總數(shù)，為的匹配結(jié)點(diǎn)集合中選中的匹配點(diǎn)編號。根據(jù)統(tǒng)計(jì)概率，當(dāng)時(shí)，需考慮兩種可能性：①當(dāng)前模式串和選定的前一個詞為詞與詞的關(guān)系；②當(dāng)前模式串與選定的前一個詞共同組成一個詞。當(dāng)時(shí)，即當(dāng)前模式串B與選定的前一個詞共同組成的詞的長度小于或等于T的最長后綴模式子串長度，則僅考慮可能性。在的情況下，設(shè)B與選定的前一個詞共同組成的詞存在，則這個詞為新詞的可能性很小，如設(shè)“勤奮”“刻苦”是既有的詞，同時(shí)，“勤”“奮”“刻”“苦”也分別以單字詞的形式存在，出現(xiàn)由“奮”“刻苦”組成的未登錄詞“奮刻苦”使“勤奮”/“刻苦”被切分成“勤”/“奮刻苦”的可能性很小，并且如“勤”“奮”組成“勤奮”也已為既有詞。故這種情況下即使能組成合法的詞，極大概率下也是模式串11…B-1中的一個，并非新詞且已經(jīng)計(jì)算過概率了，所以僅需考慮可能性②。綜上，分詞進(jìn)行到個字符時(shí)，恰以B為結(jié)尾的分詞方案為#分隔符或+#分隔符。稱使用上述方法取得分詞方案的算法稱為CPACA中文分詞算法。

CPACA算法屬于機(jī)械切分算法，也符合基于統(tǒng)計(jì)模型算法的定義。CPACA算法分為4個步驟：1) 語料訓(xùn)練，2) Trie 樹構(gòu)建，3) 自動機(jī)構(gòu)建，4) 字符串分割。

2.2 語料訓(xùn)練

語料訓(xùn)練分為封閉語料庫訓(xùn)練(有監(jiān)督)與開放語料庫訓(xùn)練(無監(jiān)督)，其中，訓(xùn)練封閉語料庫即給定已完成切分操作的文段，作為語料，在語料中逐詞計(jì)算當(dāng)前詞與上一個詞作為詞與詞的關(guān)系，同時(shí)出現(xiàn)的次數(shù)，生成CP函數(shù)所需的語料庫；開放語料庫的語料為未進(jìn)行切分操作的文段，逐字符計(jì)算當(dāng)前字符或詞與上一個字符或詞同時(shí)出現(xiàn)的次數(shù)，生成OP函數(shù)所需的語料庫。語料訓(xùn)練算法的本質(zhì)是在線性掃描給定數(shù)據(jù)時(shí)，將當(dāng)前詞的模式串編號與下一個詞的模式串編號同時(shí)作為語料庫的索引，累加詞語同時(shí)出現(xiàn)的次數(shù)。封閉語料庫訓(xùn)練數(shù)據(jù)來源有如1998年1月《人民日報(bào)》語料庫(PKU)等；開放語料庫的數(shù)據(jù)可以為任意文段；開放語料庫規(guī)模越大則未登陸詞識別準(zhǔn)確度越高。本算法不涉及語料制作。語料訓(xùn)練在現(xiàn)實(shí)操作中可用STL中的MAP庫或再建一棵Trie樹，線性遍歷數(shù)據(jù)，可與本算法中建立Trie樹的操作同時(shí)進(jìn)行，記錄結(jié)點(diǎn)路徑兩兩聯(lián)合出現(xiàn)的次數(shù)。查詢時(shí)間復(fù)雜度可控制在(1)。

2.3 Trie樹構(gòu)建

將所有模式串依次逐字符插入Trie樹中，插入過程中若在路徑中已存在指向當(dāng)前字符的結(jié)點(diǎn)，則訪問到該結(jié)點(diǎn)，如無相對應(yīng)的結(jié)點(diǎn)，則新建一個指向當(dāng)前字符的結(jié)點(diǎn)，若一個模式串完成插入，標(biāo)記其路徑中最后一個結(jié)點(diǎn)。

Trie樹在初始狀態(tài)時(shí)，僅含有一個結(jié)點(diǎn)root(根節(jié)點(diǎn)，root的編號為0)，設(shè)模式串=12…C，當(dāng)前字符C在Trie 樹中的結(jié)點(diǎn)編號為now[]，C所在結(jié)點(diǎn)的子結(jié)點(diǎn)中通過C+1轉(zhuǎn)移到的狀態(tài)結(jié)點(diǎn)編號為next(now[],C+1)，初始狀態(tài)為now[C]=next(now[0],C)；通式為now[C+1]=next(now[C],C+1)，當(dāng)now[C+1]=Null時(shí)，即當(dāng)前無相對應(yīng)結(jié)點(diǎn)，則創(chuàng)建新的結(jié)點(diǎn)，并用新的結(jié)點(diǎn)編號賦值now[C+1]和next(now[C],C+1)；當(dāng)且僅當(dāng)當(dāng)前完成了一個模式串的插入，mp[now[C]]表示當(dāng)前模式串編號的映射。done[now[C]]=True，length[mp[now[C]]]的值為該模式串的長度，mp[now[C]]的值為當(dāng)前模式串的編號，link[now[C]]表示當(dāng)前以C為結(jié)尾的結(jié)點(diǎn)的最長后綴模式子串的結(jié)尾結(jié)點(diǎn)編號。將樹上所有結(jié)點(diǎn)的link[now[C]](后綴子串鏈表)賦值為-1。反復(fù)執(zhí)行以上所有過程，完成插入所有模式串后，Trie 樹構(gòu)建完畢。

實(shí)例：

創(chuàng)建模式串集合P={“獨(dú)立”“獨(dú)立自主”“自主”“自主權(quán)”“自主平等”“平等”“平等互利”“互利”“互利互惠”“互利合作”“和平”“原則”“五項(xiàng)原則”“立”“主”，“等”“權(quán)”“利”“惠”“合”“作”“則”“項(xiàng)”}。如圖1所示，灰色結(jié)點(diǎn)表示匹配點(diǎn)(該節(jié)點(diǎn)的done為真)。

2.4 自動機(jī)構(gòu)建

通過廣度優(yōu)先遍歷整棵樹，根據(jù)KMP算法，得到每一個結(jié)點(diǎn)的指針fail并構(gòu)建后綴子串鏈表。自動機(jī)在主串掃描失配時(shí)，fail指針指向失配情況發(fā)生后的可行情況(后綴結(jié)點(diǎn))。設(shè)now結(jié)點(diǎn)的后綴結(jié)點(diǎn)fail(now)的模式串結(jié)束標(biāo)志為true,即done[*fail(now)]=true，則link[now]=fail(now)，否則，link[now]=link[*fail(now)]。

圖1 Trie 樹圖

從任意一個結(jié)點(diǎn)now來看，首先遍歷now的子字符集合，設(shè)存在通過now轉(zhuǎn)移的子結(jié)點(diǎn)，則將該子結(jié)點(diǎn)的編號加入到搜索隊(duì)列然后計(jì)算link(now)，再對該結(jié)點(diǎn)的后綴子串鏈表信息進(jìn)行更新。否則，計(jì)算fail(next(now,))的值。構(gòu)建完成后，得到全部結(jié)點(diǎn)的最長后綴模式子串的結(jié)點(diǎn)編號以及失配指針fail。

實(shí)例 模式串集合中構(gòu)建自動機(jī)后，黑色虛線箭頭指向fail指針指向的對象，灰色虛線箭頭指向link指針指向的對象，工作原理如圖2所示。

圖2 自動機(jī)工作原理圖

2.5 字符串分割

字符串分割的算法是CPACA算法的關(guān)鍵部分，從自動機(jī)的0(起始狀態(tài))開始，以字符串中每個字符為依據(jù)進(jìn)行轉(zhuǎn)移，逐字符遍歷其最長后綴模式子串集合直至根節(jié)點(diǎn)，計(jì)算當(dāng)前匹配點(diǎn)與上文聯(lián)合出現(xiàn)的概率，直到完成字符串的匹配。

在字符串分割的過程中，設(shè)字符串=12…t。從0(初始狀態(tài))開始，使用函數(shù)move(q,t+1)進(jìn)行狀態(tài)轉(zhuǎn)移，再使用后綴子串鏈表信息，更新模式串的匹配信息。歸功于五元組自動機(jī)的預(yù)處理結(jié)果，在move(q,t+1)失敗的時(shí)候，當(dāng)前指針直接轉(zhuǎn)移到后繼結(jié)點(diǎn)上，繼續(xù)匹配(next(q,t+1)存儲了后繼結(jié)點(diǎn)編號)。在遍歷文本時(shí)，通過指針link找到所有的后綴模式子串、計(jì)算匹配概率。當(dāng)文本遍歷結(jié)束后，便得到了最優(yōu)的分詞方案(程序語句見算法3)。由于字符串規(guī)格與語料庫規(guī)格的擴(kuò)大，匹配概率也增大，故現(xiàn)實(shí)應(yīng)用中應(yīng)采用長整型存儲或者高精度存儲方式。

實(shí)例 使用模式串集合P對字符串“獨(dú)立自主和平等互利”進(jìn)行分詞，運(yùn)用CPACA算法，從0(初始狀態(tài))開始，進(jìn)行狀態(tài)轉(zhuǎn)移，直至字符串分詞完畢，字符串分詞過程如表1所示。

表1 字符串分詞過程

續(xù)表

步驟切分結(jié)果Cur切分過程 獨(dú)立/自/主主D[3][1]+D[4][2]<=D[4][1]P[4][2]=max(P[3][1]×CP(自，主))； 5獨(dú)立/自主/和和D[4][1]+D[5][1]>D[5][1],D[4][2]+D[5][1]>D[5][1]P[5][1]=max(P[4][1]×CP(自主,和), P[4][2]×CP(主,和),P[2][1]×OP(自主,和), P[2][2]×OP(自主,和), P[3][1]×OP(主,和))； 6獨(dú)立/自主/和平和平D[6][1]+D[4][1]>D[6][1],D[6][1]+D[4][2]>D[6][1]P[6][1]=max(P[4][1]×CP(自主,和平), P[4][2]×CP(主,和平),P[2][1]×OP(自主,和平),P[2][2]×OP(自主,和平),P[3][1]×OP(主,和平))； 獨(dú)立/自主/和/平平D[6][2]+D[5][1]<=D[6][1]P[6][2]=max(P[5][1]×CP(和,平))； 7獨(dú)立/自主/和/平等平等D[7][1]+D[5][1]>D[7][1],D[7][1]P[7][1]=max(p[5][1]×CP(和,平等),P[4][1]×OP(和,平等),P[4][2]×OP(和,平等)) 獨(dú)立/自主/和平/等等D[7][2]+D[6][1]>D[7][1],D[7][2]+D[6][2]<=D[7][1]P[7][2]=max(max(P[6][1]×(CP(和平,等)), P[6][2]×(CP(平,等)),max(P[4][1]×OP(和平,等),P[4][2]×OP(和平,等)))； 8獨(dú)立/自主/和/平等/互互D[8][1]+D[7][1]>D[8][1],D[8][1]+D[7][2]>D[8][1]P[8]=max(P[7][1]×CP(平等,互), P[7][2]×CP(等,互),P[5][1]×OP(平等,互),P[6][1]×OP(等,互),P[6][2]×OP(等,互))； 9獨(dú)立/自主/和/平等互利平等互利D[9][1]+D[5][1]>D[9][1]P[9][1]=max(P[5][1]×CP(和,平等互利),P[4][1]×OP(和,平等互利),P[4][2]×OP(和,平等互利))； 獨(dú)立/自主/和平/等/互利互利D[9][2]+D[7][1]<=D[9][1],D[9][2]+D[7][2]<=D[9][1]P[9][2]=max(P[7][1]×CP(平等，互利), P[7][2]×CP(等，互利))； 獨(dú)立/自主/和平等/互/利利D[9][3]+D[8][1]<=D[9][1]P[9][3]=max(P[8][1]×CP(互，利))； 10獨(dú)立/自主/和/平等互利—P[9][1]>P[9][2]>P[9][3]

3 歧義消除分析

3.1 歧義分詞問題

目前存在的交集型歧義、組合型歧義和真歧義中，除了真歧義是不可避免的外，交集型歧義(如“腦海里”，可被分為{“腦”“海里”}和{“腦?！薄袄铩眪)和組合型歧義(如“才能”，在句子“杰出的才能”和“有他才能勝出”中可被分為{“才”“能”}或{“才能”})是可以避免的。產(chǎn)生歧義的原因都是因?yàn)榇嬖诙喾N切分可能性，而計(jì)算機(jī)采取了錯誤的切分。切分具有后效性，因此，一處切分錯誤常導(dǎo)致全文分詞錯位，因此能否較好地解決歧義分詞問題是衡量分詞算法性能好壞的重要標(biāo)準(zhǔn)。

3.2 歧義消除

temp=0時(shí)進(jìn)行。例如，“腦海里”這個交集型歧義詞，現(xiàn)在采用CPACA算法對第個字符(里)進(jìn)行切分，則(腦海里)=max(′CP(“腦”“海里”)，′CP(“腦?！薄袄铩?)；對于“杰出的才能”和“有他才能勝出”這兩個子集型歧義詞，設(shè)當(dāng)前對第個字符(能)進(jìn)行切分，則{杰出的才能}= max(′CP(“的”“才能”)，(x-1,t)′CP(“才”“能”))和{有他才能勝出}=max((x-2,t)′CP(“才能”“勝出”)，(x-2,t)′CP(“能”“勝出”))。結(jié)合上下文，將所有存在的切分可能性進(jìn)行比較，取正確幾率最高的一種，因此，可保證輸出結(jié)果為全文分詞正確率最高的方案。這樣既解決了機(jī)械分詞方法中存在的歧義問題，同時(shí)又解決了基于概率模型“無詞庫”對常用詞的識別精度差的問題，提高了概率模型的識別準(zhǔn)確度。

3.3 未登錄詞識別

可將未登錄詞分為4類：1) 形態(tài)上發(fā)生變化的詞，如漂漂亮亮是漂亮的疊詞；2) 固定表達(dá)，如“三百次”“一百天”；3) 命名實(shí)體，如“毛澤東”“習(xí)近平”；4) 新詞，如“閱兵藍(lán)”“學(xué)霸”。大多數(shù)情況下這些詞語切分錯誤不會影響上下文識別，如“學(xué)霸的世界我不了解”在不進(jìn)行未登錄詞識別時(shí)，切分結(jié)果為“學(xué)/霸/的/世界/我/不/了解”，除了“學(xué)霸”切分錯誤外，下文并未出現(xiàn)切分錯位的情況。相較其他切分算法，CPACA較為容易檢測出未登錄詞，根據(jù)定義8中處理未登錄詞的轉(zhuǎn)移方程：

當(dāng)兩個字符串、疊加在一起的長度大于字符串的匹配點(diǎn)的最長后綴模式子串()，即、組成一個詞的記錄在封閉語料庫里不存在，則組成的詞有一定可能性是一個未登錄詞，則將、的耦合度CP(,)與、的存在度OP(,)對比，若存在度高于耦合度，則認(rèn)為的組合為未登錄詞。這種方法將機(jī)械切分、無監(jiān)督模型概率與有監(jiān)督模型概率實(shí)時(shí)對比，有效地提高了識別的準(zhǔn)確度。

4 CPACA算法在拼音分詞中的使用

英文單詞間用空格隔開，不具有歧義性，但拼音串沒有音節(jié)與音節(jié)間隔離的標(biāo)準(zhǔn)，如拼音串“xian”可以劃分為“xi an”(代表“西安”及其同音詞)，也可以劃分為“xian”(表示“先”及其同音詞)。對于拼音串中一段的切分錯誤可能會導(dǎo)致一整個句子出現(xiàn)問題，如“xianggangren”原意為“香港人”，如第一個音節(jié)被分解為“xi an”，無論后文如何切分都無法得出正確結(jié)果。諸如此類的問題使得計(jì)算機(jī)在分解、識別拼音串和拼音輸入法連拼時(shí)產(chǎn)生麻煩。就此，根據(jù)CPACA算法，從統(tǒng)計(jì)的角度出發(fā)，當(dāng)拼音串只為“xian”時(shí)，使用者想表達(dá)“西安”的概率遠(yuǎn)高于“先”，但對于“woxianqushangxue”，翻譯為“我先去上學(xué)”的幾率遠(yuǎn)高于“我西安去上學(xué)”，即在概率模型中，“xian”與“qu”組合的可能性高于“xi”“an”“qu”。采用CPACA算法的拼音輸入法可以長期學(xué)習(xí)輸入者輸入的語句，豐富統(tǒng)計(jì)模型，最大程度上減少了拼音分詞的錯誤，使得拼音分詞愈發(fā)精準(zhǔn)。

5 理論時(shí)間復(fù)雜度

設(shè)||表示字母表的規(guī)模，是字符串規(guī)模，表示模式串的數(shù)量，M表示第個模式串的長度，模式串的規(guī)?？偣矠椋硎咎柲Ｊ酱暮缶Y模式子串鏈表長度，最長后綴模式子串總指針規(guī)模為。

5.1 預(yù)處理

預(yù)處理這個階段主要包括Trie樹的建立和AC自動機(jī)的構(gòu)建。在建立Trie樹時(shí)，將每個結(jié)點(diǎn)都賦值為初態(tài)，這時(shí)空間規(guī)模為字母表規(guī)模，可見在Trie樹建立過程中，最壞的時(shí)間復(fù)雜度是；在使用廣度優(yōu)先規(guī)則，遍歷Trie 樹時(shí)(構(gòu)建AC自動機(jī))，同樣對每個結(jié)點(diǎn)進(jìn)行詢問，故遍歷Trie 樹的最壞時(shí)間復(fù)雜度同樣也為。

5.2 分 詞

分詞過程中，文本指針不會回溯，且保持移動為線性，枚舉后綴模式子串的時(shí)間復(fù)雜度為，CP函數(shù)與OP函數(shù)枚舉每個模式子串之前的匹配可能性的最壞時(shí)間總復(fù)雜度為，自動機(jī)狀態(tài)轉(zhuǎn)移是O(1)時(shí)間復(fù)雜度，所以，字符串分詞過程的最壞時(shí)間復(fù)雜度為。

6 實(shí)驗(yàn)仿真

本文實(shí)驗(yàn)使用一臺HP-Z800 服務(wù)器(英特爾四核處理器X5570，內(nèi)存為3 GB，操作系統(tǒng)為Noi Linux)。

6.1 分詞效果實(shí)驗(yàn)

有監(jiān)督訓(xùn)練數(shù)據(jù)采用Sighan 2005 bakeoff分詞語料中由北京大學(xué)標(biāo)注的數(shù)據(jù)，對CPACA所需的耦合度數(shù)據(jù)庫進(jìn)行訓(xùn)練，存在度數(shù)據(jù)庫的數(shù)據(jù)取自搜狗新聞?wù)Z料(120 MB)。采取十折交叉驗(yàn)證，在分詞實(shí)驗(yàn)中，首先將北京大學(xué)語料庫隨機(jī)平均分成10份，任意選取其中1份作為測試數(shù)據(jù)，9份作為耦合度訓(xùn)練數(shù)據(jù)，將分詞實(shí)驗(yàn)步驟重復(fù)10遍，得到10次實(shí)驗(yàn)結(jié)果，再與已有算法的分詞效果進(jìn)行對比，評測分詞效果的指標(biāo)有以下4個(表示召回率、表示準(zhǔn)確率、1為F-值、為未登錄詞召回率)：

(2)

(3)

礙于篇幅，本文將前5次結(jié)果與后5次結(jié)果分別取平均數(shù)據(jù)，結(jié)果如表2所示。參與比較的算法是：改進(jìn)的逆向最大匹配算法[2](算法A)、消除中文分詞中交集型歧義的方法[3](算法B)、改進(jìn)的正向最大匹配算法[5](算法C)、基于粗分和詞性標(biāo)注的中文分詞方法[7](算法D)、表示學(xué)習(xí)算法[8](算法E)、改進(jìn)概率統(tǒng)計(jì)算法[9](算法F)、樹形結(jié)構(gòu)算法[15](算法G)、帶詞長詞典與判斷消除算法[16](算法H)。此外，就合計(jì)準(zhǔn)確率而言，可進(jìn)行比較的分詞方法有：Sighan2005最佳成績(封閉)，Sighan2005最佳成績(開放)，它們的合計(jì)準(zhǔn)確率分別為94.6%和96.8%[8]。

從表2所示的數(shù)據(jù)可以看出，CPACA算法的準(zhǔn)確率達(dá)到95%以上，對歧義字段有很好的消除效果，通過與近年提出的方法相對比，說明該方法具有較高的準(zhǔn)確度。導(dǎo)致錯誤切分的原因主要有：1) 字符串中含有過分生僻人名或部分罕見地名；2) 字符串中含有古漢語；3) 字符串中存在錯別字。

表2 實(shí)驗(yàn)仿真結(jié)果

6.2 分詞時(shí)間效率實(shí)驗(yàn)

在不同的文本長度下，不同算法的分詞耗時(shí)比較如圖3所示，實(shí)驗(yàn)數(shù)據(jù)從“騰訊大閩網(wǎng)”抓取，為2014年全年福建本土新聞稿隨機(jī)組合形成；耦合度數(shù)據(jù)庫規(guī)模和存在度數(shù)據(jù)庫規(guī)模皆為固定的150萬詞(隨機(jī)生成)。

從圖3可見，CPACA算法分詞速度在所有參加測試的算法中排第4位，與準(zhǔn)確率相近的算法E、算法F、算法C相比具有較大優(yōu)勢。并且，這種優(yōu)勢伴隨數(shù)據(jù)規(guī)模的增大而愈發(fā)明顯。由此可見CPACA算法適用于屏蔽詞檢測或網(wǎng)頁搜索等需高準(zhǔn)確率且流量巨大的工程當(dāng)中。

圖3 分詞耗時(shí)比較

7 結(jié)束語

在AC自動機(jī)的基礎(chǔ)上，提出了CPACA中文分詞算法。經(jīng)過實(shí)驗(yàn)驗(yàn)證，CPACA算法不僅具有很好的實(shí)用性，而且在字符串規(guī)模大、模式串規(guī)模大、數(shù)量多的現(xiàn)實(shí)情況下，提高了分詞的準(zhǔn)確率。

CPACA算法分詞準(zhǔn)確率很大程度上取決于耦合度與存在度，兩者的語料庫豐富與否都是分詞準(zhǔn)確率的決定性因素，但目前存在封閉語料庫規(guī)模小的問題，華人打字習(xí)慣主要以拼寫詞組或短語的方式，鮮少一次性拼寫一整個句子，因此，今后可研究拼音、五筆等輸入法如何在用戶輸入的同時(shí)自動獲取文段的分詞方案。在拼音輸入法中加入切分記錄的功能，建立如云語料庫等方法，使封閉語料庫也可通過無監(jiān)督的方式來自我學(xué)習(xí)、自動更新，及時(shí)加入新近未登錄詞，從而進(jìn)一步提高中文分詞的準(zhǔn)確率。

CPACA算法在一定程度上使得中文分詞更加準(zhǔn)確，但隨著字符集、模式串的增大，導(dǎo)致算法所需的空間不斷加大，因此，后續(xù)研究將在保證準(zhǔn)確率的基礎(chǔ)上，研究怎樣減小該算法的空間復(fù)雜度。

[1] 魏莎莎, 熊海靈. 中文分詞中的歧義識別處理策略[J]. 微計(jì)算機(jī)信息, 2010, 30: 190-192.

WEI Sha-sha, XIONG Hai-ling. Ambiguity identification strategy of Chinese word segmentation[J]. Control & Automation, 2010, 30: 190-192.

[2] 羅桂瓊, 費(fèi)洪曉, 戴弋. 基于反序詞典的中文分詞技術(shù)研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2008, (1): 80-83.

LUO Gui-qiong, FEI Hong-xiao, DAI Yi. Research of Chinese segmentation based on converse segmentation dictionary[J]. Computer Technology and Development, 2008(1): 80-83.

[3] 魏博誠, 王愛平, 沙先軍, 等. 一種消除中文分詞中交集型歧義的方法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2011, 21(5): 60-63.

WEI Bo-cheng, WANG Ai-ping, SHA Xian-jun, et al. A method about removing overlapping ambiguity producing in Chinese matching[J] Computer Technology and Development, 2011, 21(5): 60-63.

[4] MA Guo-jie, LI Xing-shan, RAYNER K. Word segmentation of overlapping ambiguous strings during chinese reading[J]. Journal of Experimental Psychology-Human Perception and Performance, 2014, 3(40): 1046-1059.

[5] JIANG W, GUAN Y, WANG X. A pragmatic Chinese word segmentation approach based on mixing models[J]. Association for Computational Linguistics and Chinese Language Processing, 2007, 11(4): 393-416.

[6] 李玲. 基于雙詞典機(jī)制的中文分詞系統(tǒng)設(shè)計(jì)[J]. 機(jī)械工程與自動化, 2013(1): 17-19.

LI Ling. Design of chinese word segmentation system based on dual-dictionary mechanism[J]. Mechanical Engineering & Automation, 2013(1): 17-19.

[7] 姜芳, 李國和, 岳翔, 等. 基于粗分和詞性標(biāo)注的中文分詞方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(6): 204-207.

JIANG Fang, LI Guo-he, YUE Xiang, et al. Segmentation of Chinese word based on method of rough segment and part of speech tagging[J]. Computer Engineering and Applications, 2015, 51(6): 204-207.

[8] 來斯惟, 徐立恒, 陳玉博, 等. 基于表示學(xué)習(xí)的中文分詞算法探究[J]. 中文信息學(xué)報(bào), 2013, 5(27): 8-14.

LAI Si-wei, XU Li-heng, CHEN Yu-bo, et al. Chinese word segment based on character representation learning[J]. Journal of Chinese Information Processing, 2013, 5(27): 8-14.

[9] SUN X, ZHANG Y, MATSUZAKI T, et al. Probabilistic Chinese word segmentation with non-local information and stochastic training[J]. Information Processing & Management, 2013, 49(3): 626-636.

[10] ZHANG D Y, XU Y. Chinese word segmentation based on the first kind of spline weight function neural networks[J]. Applied Science Materials Science & Information Technologies in Industry, 2014, 513-517: 683-686.

[11] HEWLETT D, COHEN P. Fully unsupervised word segmentation with bve and mdl[C]//Proceedings of ACL. [S.l.]: ACL, 2011: 540-545.

[12] WANG Han-shi, ZHU Jian, TANG Shi-ping, et al. A new unsupervised approach to word segmentation[J]. Computational Linguistics, 2011, 37(3): 421-454.

[13] 馬寧, 李亞超, 何向真, 等. 一種實(shí)用的資源稀缺條件下的分詞方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(1): 68-70.

MA Ning, LI Ya-chao, HE Xiang-zhen, et al. Practical approach of word segmentation in poor resource situation[J]. Application Research of Computers, 2016, 33(1): 68-70.

[14] THOMAS H, CORMEN C E L, RONALD L R, et al. 算法導(dǎo)論[M]. 3版. 殷建平, 徐云, 王剛, 等, 譯. 北京: 機(jī)械工業(yè)出版社, 2013.

THOMAS H, CORMEN C E L, RONALDLR, et al. Introduction to algorithms[M]. 3rd. Translated by YIN Jian-ping, XU Yun, WANG Gang, et al. Beijing: China Machine Press, 2013.

[15] 溫唱. 基于樹形結(jié)構(gòu)的中文分詞方法的研究與實(shí)現(xiàn)[D]. 北京: 華北電力大學(xué), 2013.

WEN Chang. Research and implementation of Chinese word segmentation based on tree structure[D]. Beijing: North China Electric Power University, 2013

[16] 王崇. 基于帶詞長的詞典機(jī)制和規(guī)則判定的歧義消解算法的中文分詞技術(shù)的研究[D]. 青島: 青島科技大學(xué), 2013

WANG Chong. Research on Chinese word segmentation technology with word length and rule algtithm[D]. Qingdao: Qingdao University of Science & Technology, 2013.

編 輯 稅 紅

A Probability Model Chinese Word Segmentation Algorithm Based on Aho-Corasick Automata Algorithm

XU Yi-bin

(Faculty of Engineering and Applied Science, Queen's University Kingston Canada K7L 3N6)

Aho-Corasick automata algorithm is a famous multi-string matching algorithm, which backtracks to the effective subsequence state through the fail pointer when it fails in one pattern matching, where one or more effective subsequent states may exist. According to the above characteristics, this paper proposes an automata algorithm suitable for Chinese segmentation. The algorithm calculates the context matching probability of the current pattern by dynamic programming method, and backtracks to the optimal subsequent state of maximum probability, namely, it can realize the combination of the mechanical Chinese segmentation and statistics and probability model. The experimental result shows that a high accuracy rate in Chinese segmentation can be obtained through this algorithm.

Aho-Corasick automation; Chinese segmentation; dynamic programming; trie tree

TP301.6

A

10.3969/j.issn.1001-0548.2017.02.018

2015-05-04；

2016-08-08

徐懿彬(1997-)，男，主要從事中文信息處理方面的研究.