楊進(jìn)才,陳忠忠,謝芳,胡金柱(華中師范大學(xué) 計(jì)算機(jī)學(xué)院,武漢 430079)(湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,武漢 430068)

?

基于漢語拼音首字母索引的混合分詞算法①

楊進(jìn)才1,陳忠忠1,謝芳2,胡金柱1
1(華中師范大學(xué) 計(jì)算機(jī)學(xué)院,武漢 430079)
2(湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,武漢 430068)

摘 要:中文自動(dòng)分詞是web文本挖掘以及其它中文信息處理應(yīng)用領(lǐng)域的基礎(chǔ).蓬勃發(fā)展的中文信息處理應(yīng)用對(duì)分詞技術(shù)提出了更高的要求.提出了一種新的分詞算法FPLS,該算法用拼音首字母作為詞語表一級(jí)索引,詞語的字?jǐn)?shù)為二級(jí)索引構(gòu)造分詞詞典,采用雙向匹配方法,并引入規(guī)則解決歧義切分問題.與現(xiàn)有的快速分詞算法比較,該算法分詞效率高且正確率高.

關(guān)鍵詞:中文分詞; 拼音索引; 雙向匹配; 歧義切分

自然語言人機(jī)接口、情報(bào)檢索、web查詢系統(tǒng)、文本數(shù)據(jù)挖掘以及應(yīng)用最廣泛的搜索引擎的研究均依賴于中文信息處理的研究.在中文信息處理研究中自動(dòng)分詞算法是基礎(chǔ)課題,應(yīng)用環(huán)境不同對(duì)自動(dòng)分詞要求也有所不同.有一些對(duì)于速度要求非常高,如處理海量數(shù)據(jù)的搜索引擎,有一些對(duì)于精度的要求比較嚴(yán)格,如自然語言的理解、自動(dòng)翻譯等.

自動(dòng)分詞算法研究的主要容是設(shè)計(jì)高效的詞表數(shù)據(jù)結(jié)構(gòu)以及算法,以滿足不同的分詞要求.在中文信息處理領(lǐng)域的高速發(fā)展的20年來,許多專家、學(xué)者提出了不同的自動(dòng)分詞算法如: MM方法[1,2]、多次Hash快速分詞算法[3]、全二分查找算法[4]、雙哈希二叉樹分詞算法[5]、規(guī)則的分詞算法[6]、詞頻的分詞算法[7]等.

這些分詞算法歸為三大類: 機(jī)械分詞方法、基于統(tǒng)計(jì)的分詞方法和基于規(guī)則的分詞方法.MM方法、多次Hash快速分詞算法、全二分查找算法和雙哈希二叉樹分詞算法屬于機(jī)械分詞方法.規(guī)則的分詞算法屬于基于理解的分詞方法.詞頻的分詞算法屬于基于統(tǒng)計(jì)的方法.機(jī)械分詞方法無法解決分詞階段的歧義切分問題和未登錄詞識(shí)別問題,使用過程中需要借助其他的信息提高精確度.基于規(guī)則的分詞方法對(duì)信息的提取較難,因此對(duì)其研究還處在試驗(yàn)階段.基于統(tǒng)計(jì)的分詞方法需要使用詞頻度.它不僅考慮了句子中詞語出現(xiàn)的頻率信息,同時(shí)也考慮到詞語與上下文的關(guān)系,具備較好的學(xué)習(xí)能力,對(duì)歧義詞和未登錄詞的識(shí)別有良好的效果[8].但它也有一定的局限性,會(huì)抽出一些出現(xiàn)頻度高、但并不是詞的常用字組.

隨著大數(shù)據(jù)時(shí)代的到來,海量的文本信息需要中文分詞既準(zhǔn)確,同時(shí)快速.本文將探討一種新的分詞算法,在優(yōu)先保證高速的同時(shí)提高分詞的準(zhǔn)確率.

1　基本自動(dòng)分詞算法

基本的自動(dòng)分詞算法有兩種: 正向匹配算法與逆向匹配算法.

1.1正向最大匹配分詞算法

正向最大匹配分詞算法是一種應(yīng)用最為廣泛的機(jī)械分詞算法,這種算法又叫最長匹配法、回巡檢索法,本文稱正向匹配算法.算法描述如下:

假設(shè)自動(dòng)分詞詞典中的最長詞條含有n個(gè)漢字

(a)輸入要處理的字符串,取前n個(gè)字為匹配字段.

(b)對(duì)匹配字段查找分詞詞典,如果匹配成功,匹配字段作為一個(gè)詞就被切分出來;如果查不到,去掉匹配字段的最后一個(gè)字,剩余的n-1個(gè)字再作為匹配字段進(jìn)行匹配,直到字段匹配成功.

(c)將句子中剩下的部分作為匹配字段,重復(fù)進(jìn)行步驟(a)(b)(c)直至匹配完成為止.

1.2逆向最大匹配分詞算法

逆向分詞算法與正向分詞算法大體相似,只是匹配從后往前進(jìn)行,而且使用的詞典也不相同,它使用逆序詞典,其中每個(gè)詞語以逆序的方式存放.匹配不成功去掉前面一個(gè)字繼續(xù)匹配直至匹配成功.

1.3正向分詞算法與逆向分詞算法的分析對(duì)比

單純的使用逆向最大匹配分詞算法的錯(cuò)誤率為1/245,單純的使用正向最大匹配分詞算法的錯(cuò)誤率為1/169[9].逆向最大匹配分詞算法準(zhǔn)確率要比正向最大匹配分詞算法的高.

例1: “老師講不到的學(xué)生會(huì)學(xué).”

正向最大匹配分詞算法會(huì)切分成“老師講不到 的學(xué)生會(huì)學(xué)”,逆向最大匹配分詞算法會(huì)切成“老師講不到的學(xué)生會(huì)學(xué)”.分析正向匹配和逆向匹配的錯(cuò)誤,會(huì)發(fā)現(xiàn)錯(cuò)誤的部分大多數(shù)是正向匹配與逆向匹配不一致即出現(xiàn)歧義.

例2: “老師講的題學(xué)生會(huì)”

正向最大匹配分詞算法會(huì)切成“老師講的題學(xué)生會(huì)”,逆向最大匹配分詞算法會(huì)切成“老師講的題學(xué)生會(huì)”此時(shí),雖然正向最大匹配分詞算法與逆向最大分詞算法的結(jié)果一致,但是同樣出現(xiàn)了歧義.正確的結(jié)果應(yīng)為“老師講的題學(xué)生會(huì)”

通過分析例1和例2,我們發(fā)現(xiàn)正向最大匹配和逆向最大匹配結(jié)果不一致和一致都有可能出現(xiàn)歧義.解決好這些歧義可以提高分詞的正確率.

2　拼音首字母分詞詞典

2.1詞庫構(gòu)造

漢語中的詞是最小的、獨(dú)立的,有重要意義的語言成分,是組成語言的最小單位.漢語中詞是一個(gè)開放的集合,數(shù)量是無窮的,但可收集的詞卻是有限的.常用的詞有43570個(gè),這些詞的長短有所不一,從短到一個(gè)字到長到七個(gè)字的均有,其中二個(gè)字詞最多.具體分布如表1所示.

表1　詞庫詞條字?jǐn)?shù)分布表

組成詞的漢字雖很多,但拼音卻只有496個(gè)(在不考慮音調(diào)的情況下),而對(duì)應(yīng)的首字母更少僅有26 個(gè)(a-z).如果按漢語拼音的首字母劃分詞條,就會(huì)將詞條劃分成26個(gè)部分.

2.2分詞詞典

分詞詞典是組成漢語自動(dòng)分詞系統(tǒng)的重要成分,漢語自動(dòng)分詞系統(tǒng)需要從分詞詞典中提取信息.這里設(shè)計(jì)一種拼音首字母分詞詞典,詞典分為三部分: 首字母表、詞條字母表、詞典正文.詞典的結(jié)構(gòu)如圖1所示.

圖1　詞典結(jié)構(gòu)圖

(1)首字母表

每一個(gè)漢字在首字母表中都能找到唯一的縮寫字母與其相照應(yīng),首字母表中每一項(xiàng)的結(jié)構(gòu)如圖1a所示.

其中,C為首字母; Q1為指向在詞條字母表中第一次出現(xiàn)以C開頭的字符串的指針; Q2為指向在詞條字母表中最后一次出現(xiàn)以C開頭的字符串的指針.

例如,若C為‘a(chǎn)’,則Q1指向詞條字母表中的“a”,Q2指向詞條字母表中的“alpkydh”(其中“alpkydh”為在詞條字母表中最后一次出現(xiàn)且以‘a(chǎn)’為開頭的字符串).

(2)詞條字母表

詞條字母表對(duì)應(yīng)字典正文中唯一的一項(xiàng).其中,C2為拼音首字母所組成的字符串; P1為指向詞典正文中第一次出現(xiàn)拼音首字母縮寫為C2的詞語的指針; P2為指向詞典正文中最后一次出現(xiàn)拼音首字母縮寫為C2的詞語的指針; length為C2的長度; flag為是否有與待查詢的縮寫字母相匹配的C2的標(biāo)志,初始值設(shè)為0.

在圖2中,若C2為“a”,則P1指向“啊”的指針,P2為指向“奧”的指針,length=1.

(3)詞典正文

詞典正文是由詞構(gòu)成.其中,C3為詞語; flag2是否匹配成功的標(biāo)志詞,初始值設(shè)為0.

將上述三的結(jié)構(gòu)構(gòu)成分詞詞典整體結(jié)構(gòu)圖如圖2所示.

圖2　分詞詞典整體結(jié)構(gòu)圖

3　分詞歧義字段處理

不同的分詞方法對(duì)同一段文本進(jìn)行分詞,結(jié)果可能不相同,其中不同的部分稱為歧義字段.

例如: “我們出現(xiàn)奧運(yùn)會(huì)場(chǎng).”

正向最大匹配算法會(huì)切成“我們出現(xiàn)奧運(yùn)會(huì)場(chǎng)”,而逆向分詞算法會(huì)切成“我們出現(xiàn)奧運(yùn)會(huì)場(chǎng)”.其中“奧運(yùn)會(huì)”和“會(huì)場(chǎng)”出現(xiàn)歧義,“會(huì)”為交集字串.處理分詞中出現(xiàn)的歧義字段,是分詞中的一個(gè)難點(diǎn).歧義字段的類型有交叉型歧義字段與組合型歧義字段兩種.交叉型歧義字段指A、B、C三個(gè)子串,AB、BC分別構(gòu)成詞則有兩種切分方式:AB/C和A/BC,而組合型歧義字段指對(duì)于漢字串AB既可切分為AB又可切分為A/B[10].歧義字段中交叉型最多,交叉型歧義字段占全部歧義字段的94%[11].為了解決分詞中出現(xiàn)的歧義問題,本文在PFLS算法的基礎(chǔ)上采用規(guī)則進(jìn)行消歧.設(shè)計(jì)規(guī)則如下:

(1)交集字串與其后繼的字串構(gòu)成形容詞,將歧義字段的首字切掉.如: “太美好”,交集字串為“美”,“美”與后繼構(gòu)成形容詞將其前驅(qū)切掉,結(jié)果為“太美好”.

(2)交集字串的前驅(qū)為數(shù)詞,將歧義字段的首字切掉.如: “三個(gè)人”交集字串為“個(gè)”,“三”為數(shù)詞將其切掉,結(jié)果為“三個(gè)人”.

(3)交集字串與后繼構(gòu)成動(dòng)詞且與前驅(qū)也構(gòu)成動(dòng)詞,將尾字單切.如: “騷擾亂民” 交集字串為“擾”,“擾亂”為動(dòng)詞將“亂”切掉,結(jié)果為“騷擾亂民”.

(4)歧義字段類似ABCD,交集字串與后繼構(gòu)成動(dòng)詞且前驅(qū)為名詞,將前驅(qū)切掉.如: “老師不講,學(xué)生會(huì)學(xué)”交集字串為“會(huì)”,“學(xué)生”為名詞,“會(huì)學(xué)”為動(dòng)詞切掉前驅(qū),結(jié)果為“老師不講,學(xué)生會(huì)學(xué)”.

(5)交集字串與后繼構(gòu)成名詞且前驅(qū)為動(dòng)詞,將前驅(qū)切掉.如: “勞動(dòng)力氣”交集字串為“力”,“力氣”為名詞,“勞動(dòng)”這里為動(dòng)詞切掉前驅(qū),結(jié)果為“勞動(dòng)力氣”.

(6)交集字串的后繼為助詞,將尾字切掉.如: “她是一個(gè)嬌小的女孩”交集字串為“小”,有“嬌小”和“小的”兩種切分方式,“的”為助詞,結(jié)果為“她是一個(gè)嬌小的女孩”.

(7)交集字串的后繼為后接成分,將尾字切掉.如:“大人們”,“人”為交集字串,“們”為后接成分將其切掉,結(jié)果為“大人們”.

4　算法描述

將這種按拼音首字母分詞的分詞算法稱為FPLS (First Letter of the Pinyin Segmentation),算法描述如下:

(1)基于拼音首字母的正向匹配算法

算法名: FR ForeMatch(Text)

輸入: Text 為一段文本

輸出: FR,為一重復(fù)有序集合,集合中的元素為字與詞.

(a)將Text保存于數(shù)組s1中,將Text漢字轉(zhuǎn)化為拼音首字母存儲(chǔ)于數(shù)組s2中;

(b)字符個(gè)數(shù)n=7;

(c)取s2中前n個(gè)字符s,先根據(jù)首字符在首字母表中查找.在首字母表中找到與之對(duì)應(yīng)的C之后,從Q1指向的字符串開始,在詞條字母表中逐個(gè)匹配,直至Q2所指向的字符串為止.

(d)在詞條字母表中未找到與s相匹配的字符串,flag==0,n=n-1(去掉s的最后一個(gè)字符)重新進(jìn)行(c)步驟; 找到與s相匹配的字符串,flag==1,從P1指向的詞語開始,在詞典正文中逐個(gè)匹配s對(duì)應(yīng)的詞,直至P2所指向的詞語為止.

(e)在詞典正文中未找到匹配的詞語,flag2==0,去掉s的最后一個(gè)字符重新進(jìn)行(c)(d)(e)步驟.若在詞典正文中找到匹配詞語,flag2==1,將s對(duì)應(yīng)的s1中的詞作為一個(gè)詞切分,并將結(jié)果加入FR中.

(f)重復(fù)(b)(c)(d)(e)步驟,直至s1全部切分完畢.

(2)基于拼音首字母的逆向匹配算法

算法名: BR BackMatch(Text)

輸入: Text 為一段文本

輸出: BR,為一重復(fù)有序集合,集合中的元素為字與詞

(a)將Text保存于數(shù)組s1中,將Text漢字轉(zhuǎn)化為拼音首字母存儲(chǔ)于數(shù)組s2中;

(b)字符個(gè)數(shù)n=7;

(c)取s2中后n個(gè)字符s,先根據(jù)首字符在首字母表中查找.在首字母表中找到與之對(duì)應(yīng)的C之后,從Q1指向的字符串開始,在詞條字母表中逐個(gè)匹配,直至Q2所指向的字符串為止.

(d)在詞條字母表中未找到與s相匹配的字符串,flag==0,n=n-1,去掉s的最前一個(gè)字符)重新進(jìn)行(c)步驟; 找到與s相匹配的字符串,flag==1,從P1指向的詞語開始,在詞典正文中逐個(gè)匹配s對(duì)應(yīng)的詞,直至P2所指向的詞語為止.

(e)在詞典正文中未找到匹配的詞語,flag2==0,去掉s的最前一個(gè)字符重新進(jìn)行(c)(d)(e)步驟.若在詞典正文中找到匹配詞語,flag2==1,將s對(duì)應(yīng)的s1中的詞作為一個(gè)詞切分,并將結(jié)果加入BR中.

(f)重復(fù)(b)(c)(d)(e)步驟,直至s1全部切分完畢.

(3)基于拼音首字母的雙向匹配算法

執(zhí)行(1)(2)得到FR和BR;

(a)FR-BR∪BR-FR //獲取有歧義的分詞

(c)運(yùn)用規(guī)則處理(2)中的歧義部分

(d)輸出LR ,LR為最后的分詞結(jié)果.

例如: Text= “組織化解危機(jī).”

利用拼音首字母正向匹配算法,得到結(jié)果FR={組織化,解,危機(jī)}.

利用拼音首字母逆向匹配算法,得到的結(jié)果BR={組織,化解,危機(jī)}.

FR-BR∪BR-FR={組織,組織化,解,化解},其中交集字串為“化”.根據(jù)規(guī)則“化”與后繼構(gòu)成動(dòng)詞“化解”且前驅(qū)為名詞,切分為“組織”和“化解”兩個(gè)詞,即LR={組織,化解,危機(jī)}.

5　實(shí)驗(yàn)分析

對(duì)1998年人民日?qǐng)?bào)標(biāo)注語料庫中的語句進(jìn)行分詞,得到近13.6萬個(gè)不同詞性的詞,從中抽取12000個(gè)詞構(gòu)建普通的無詞典結(jié)構(gòu)的詞庫和按照PFLS算法的詞典結(jié)構(gòu)建詞庫.分別用最大正向匹配算法和最大逆向匹配算法調(diào)用普通的無詞典結(jié)構(gòu)的詞庫進(jìn)行分詞.然后與FPLS算法采用詞典結(jié)構(gòu)進(jìn)行分詞的結(jié)果進(jìn)行對(duì)比.

實(shí)驗(yàn)結(jié)果表明,拼音首字母自動(dòng)分詞算法時(shí)間復(fù)雜度比傳統(tǒng)的最大正向匹配算法和最大逆向匹配算法相比,效率高、正確率高.實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如表2所示.

表2　實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

為了更好的說明問題,本文通過兩個(gè)例子來論證FPLS的可行性,并對(duì)實(shí)驗(yàn)過程中出現(xiàn)的錯(cuò)誤進(jìn)行分析.

例3.“通過組織化解了他們的矛盾”

正向最大匹配的結(jié)果為“通過組織化解了他們 的矛盾”,逆向最大匹配算法的結(jié)果為“通過組織化解了他們的矛盾”.兩者匹配的結(jié)果不一致出現(xiàn)歧義字段“組織化解”,本文采用規(guī)則解決了歧義問題提高了準(zhǔn)確率.

例4.“這道題學(xué)生會(huì)”

正向最大匹配的結(jié)果為“這道題學(xué)生會(huì)”,逆向最大匹配算法的結(jié)果為“這道題學(xué)生會(huì)”.兩者雖匹配結(jié)果一致,但是不符合語義.正確結(jié)果是“這道題學(xué)生會(huì)”.出現(xiàn)這種情況的原因是類似這樣的語句需要借助語義、語境信息解決.然而,并未有一種很好的方法解決語義上歧義的問題,包括目前較為成熟的分詞系統(tǒng)LTP也沒有很好的解決方法,這也是分詞結(jié)果出現(xiàn)錯(cuò)誤的原因.解決語義歧義問題也是我們下一步要做的工作.

基于FPLS分詞算法的時(shí)間之所比最大正向匹配和最大逆向匹配算法短,是因?yàn)镕PLS算法采用的詞典結(jié)構(gòu)采用了多維索引,而最大正向匹配分詞算法和最大逆向分詞算法未采用索引.

6　結(jié)語

FPLS算法將多維索引與歧義處理規(guī)則相結(jié)合,分詞效率高且正確率較高,適用于搜索引擎和快速分詞.由于歧義處理規(guī)則針對(duì)正向匹配與逆向匹配中的歧義制定,規(guī)則不夠全面,與專門的語義、語法分詞歧義處理相比還有一定的差距.在保證分詞的高效的同時(shí),最大限度提高分詞的準(zhǔn)確率是進(jìn)一步研究的課題.

參考文獻(xiàn)

1王瑞雷,欒靜,潘曉花,等.一種改進(jìn)的中文分詞正向最大匹配算法.計(jì)算機(jī)應(yīng)用與軟件,2011,28(3):195–197.

2周俊,鄭中華,張煒.基于改進(jìn)最大匹配算法的中文分詞粗分方法.計(jì)算機(jī)工程與應(yīng)用,2014,(2):124–128.

3張科.多次Hash快速分詞算法.計(jì)算機(jī)工程與設(shè)計(jì),2007,28(7):1716–1718.

4李振星,徐澤平,唐衛(wèi)清,等.全二分最大匹配快速分詞算法.計(jì)算機(jī)工程與應(yīng)用,2002,38(11):106–109.

5羅洋.一種基于雙哈希二叉樹的中文分詞詞典機(jī)制.計(jì)算機(jī)應(yīng)用與軟件,2013,30(5):251–253.

6張江.基于規(guī)則的分詞方法.計(jì)算機(jī)與現(xiàn)代化,2005,(4):18– 20.

7翟鳳文,赫楓齡,左萬利.字典與統(tǒng)計(jì)相結(jié)合的中文分詞方法.小型微型計(jì)算機(jī)系統(tǒng),2006,27(9):1766–1771.

8韓冬煦,常寶寶.中文分詞模型的領(lǐng)域適應(yīng)性方法.計(jì)算機(jī)學(xué)報(bào),2015,38(2):272–281.

9王艷,元昌安,覃曉,等.基于VC++/MFC的中文自動(dòng)分詞算法及其軟件的實(shí)現(xiàn).廣西師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,25(3):104–108.

10熊回香.全文檢索中的漢語自動(dòng)分詞及其歧義處理.中國圖書館學(xué)報(bào),2005,31(5):54–57.

11趙偉,戴新宇,尹存燕,等.一種規(guī)則與統(tǒng)計(jì)相結(jié)合的漢語分詞方法.計(jì)算機(jī)應(yīng)用研究,2004,21(3):23–25.

Hybrid Segmentation Algorithm for Chinese Text Using First Pinyin Letter Index

YANG Jin-Cai1,CHEN Zhong-Zhong1,XIE Fang2,HU Jin-Zhu1
1(School of Computer Science of Central China Normal University,Wuhan 430079,China)2(School of Computer Science of Hubei University of Technology,Wuhan 430068,China)

Abstract:Chinese automatic segmentation is the basis of web text mining and other Chinese information processing applications.Booming Chinese information processing applications put forward a higher requirement for Chinese automatic segmentation.This paper presents a new segmentation algorithm FPLS,which uses a dictionary with a first letter of the Pinyin as a first level index and words count as the secondary index structure.A bidirectional matching method and rules are employed to resolve ambiguity segmentation problem in the algorithm.Comparing with the existing algorithm,algorithm FPLS gets higher accuracy and efficiency.

Key words:Chinese automatic segmentation; Pinyin index; bidirectional match; ambiguity resolve

基金項(xiàng)目:①教育部社科基金(13YJAZH117);國家社科基金(14BYY093)

收稿時(shí)間:2015-07-28;收到修改稿時(shí)間:2015-09-21