二次回溯中文分詞方法

摘 要:在最大匹配法(MM)的基礎上，提出了二次回溯中文分詞方法。該方法首先對待切文本進行預處理，將文本分割成長度較短的細粒度文本;利用正向匹配、回溯匹配、尾詞匹配、碎片檢查來有效發現歧義字段;利用長詞優先兼顧二詞簇的方式對交集型歧義字段進行切分，并對難點的多鏈長交集型歧義字段進行有效發現和切分。從隨機抽取的大量語料實驗結果上證明了該方法的有效性。

關鍵詞:中文分詞; 回溯匹配; 交集型歧義; 多鏈長; 碎片檢查

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3321-03

doi:10.3969/j.issn.1001-3695.2009.09.034

Two times backtracking chinese word segmentation method

YUAN Jiana， ZHANG Jin-songa， MA Liangb

(a.School of Optical-Electrical Computer Engineering， b.Business School， University of Shanghai for Science Technology， Shanghai 200093， China)

Abstract:This paper proposed two times backtracking Chinese word segmentation method based on the MM. The text was pretreatment by the method in the first， then cut the text into shorter lengths granular text. Found ambiguity field effective by forward matching method， backtracking matching， last words matching and debris inspection. Cut crossing ambiguity field by long term priorities and 2-words rules， and found the difficult and multi-linked crossing ambiguity field and cut effectively. The large number of randomly selected language materials being tested and results show that method is effective.

Key words:Chinese word segmentation; backtracking matching; crossing ambiguity; multi-linked; debris inspection

0 引言

中文信息處理的特有問題就是如何將漢語的字串分割為合理的詞語序列。中文分詞是句法分析等深層中文信息處理的基礎，也是機器翻譯、信息檢索和信息抽取等智能化信息處理的關鍵所在[1，2]。而中文分詞的主要困難在于切分歧義消解和未登錄詞語的識別，這也是世界上最令計算機感到棘手的語言現象之一[3~5]。中文分詞方法中機械分詞法主要包括正向最大匹配法(maximum matching method ，MM)、逆向最大匹配法(reverse direction maximum matching method ，RMM)和最少切分法。目前機械式分詞占主流地位的是正向最大匹配法和逆向最大匹配法，這兩種方法是利用一個分詞詞表進行模式匹配來切分，不依賴詞法、句法和語義知識，切分速度快、簡潔、易于實現，在各種中文信息處理上得到了廣泛的應用;缺點是對于歧義字段無法有效地識別和切分。統計結果表明，單純使用正向最大匹配的錯誤率為1/169;單純使用逆向最大匹配的錯誤率為1/245[6]，但這種精度還不能滿足智能信息處理以及人機交互的要求，對詞義消歧(word sense disambiguation，WSD)是計算語言學和自然語言處理領域一個重要的研究課題，也是近些年來該領域的熱點研究問題之一[7]。本文在正向最大匹配法的基礎上，提出二次回溯中文分詞方法(簡稱二次回溯法)，該方法對歧義字段能有效地識別和切分，大大提高分詞的召回率和查準率。

1 相關概念

歧義字段分為交集型歧義字段和多義型歧義字段兩類，為行文方便，結合文獻[3，5，8]給出如下定義:

定義1 令T1為詞庫，T2為字庫，

W=a1NA1ADaib1NA1ADbkc1NA1ADcj

W1=a1NA1ADaib1NA1ADbk

W2=b1NA1ADbkc1NA1ADcj

Wa=a1NA1ADai，Wc=c1NA1ADcj

其中:W，W1，W2，Wa，Wc∈T1以及ai′，bk′，cj′∈T2(i′∈[1，i]，j′∈[1，j]，k′∈[1，k])，則稱字串W為由詞W1和詞W2形成的交集型歧義字段，n=i+j+k為歧義字段的長度， 字串b1NA1ADbk為交段，k為交段的長度，歧義字段中交段的個數稱為鏈長。

例如，為人民工作。其中“為人”“人民”“民工”“工作”均是詞，交段長度均為1，鏈長為3。

定義2 令T1為詞庫，

W=a1NA1ADaib1NA1ADbk

W1=a1NA1ADai，W2=b1NA1ADbk

其中:W，W1，W2∈T1以及ai′，bk′∈T2(i′∈[1，i]，k′∈[1，k])，而且存在語境〈α，β〉和〈λ，μ〉，使得αa1NA1ADaib1NA1ADbkβ中a1NA1ADaib1NA1ADbk為詞W，λa1NA1ADaib1NA1ADbkμ中a1NA1ADaib1NA1ADbk為詞序列W1W2，則稱W為多義型歧義字段。

例如:a)這個門把手壞了;b)請把手拿開。

例1，“把手”為多義型歧義字段，a)中“把手”不應該切分，b)中“把手”應該切分為“把”和“手”兩個獨立的詞。

交集型歧義字段占全部歧義切分字段的85%以上[9]，所以要提高中文分詞質量最關鍵的是提高對交集型歧義字段的識別率和切分準確性。

定義3 文本中相鄰兩個標點符號(含段首不可見符號)之間字串序列稱為元句子。

2 二次回溯法設計

2.1 二次回溯法總體過程

二次回溯中文分詞算法，主要由如下幾步組成:

a)將文本轉換成細粒度文本，即元句子;

b)正向最大匹配;

c)正向次大匹配(第一次回溯匹配);

d)尾單字與后繼單字結合成二字檢測;

e)循環步驟b)~d)至元句子切分結束;

f)對元句子切分后的字串進行碎片檢查(第二次回溯匹配);

g)繼續下一個元句子進行切分，循環步驟b)~f)直至文本切分結束。

2.2 第一次回溯切分算法描述

首先將待切文本中所有諸如:“，”“;”“!”等標點符號用標簽隔開，如用“/，/”“/;/”“/!/”分別替換“，”“;”“!”。這樣文本就被“/”分隔成一個個標點符號或者無標點符號的字串，這個字串稱為元句子(定義3)。“/”符號之間的標點符號無須切分;針對長度小于等于2的元句子獨立成詞，無須切分。對文本的切分只要依次完成對文本中長度大于2的元句子的切分即可，以下過程就針對單一的元句子來進行切分。

若分詞詞表中最長的詞由n個字組成，在待切元句子str中按自左向右截取長度為n的字串str1，使之與詞表中的詞條依次匹配(如果元句子Str長度小于等于n，則取整個元句子來匹配):

1)如果詞表中存在str1，再取str1的前n-1個字串str2=str1.Substring(0，n-1)與詞表中的詞條依次匹配:

a)如果詞表中不存在str2，則將str1從待切文本中切分出去，str=str.substring(n)，繼續在剩下待切元句子中自左向右截取長度為n的字串與詞表中的詞條依次匹配。

b)如果詞表中存在str2，則取Str1最右端的字與待切元句子中的第n+1個字組合str3= str.substring(n-1，2)， Str3與詞表中的詞條依次匹配:

(a)如果不存在str3這樣的詞，則將str1從待切元句子中切分出去，str=str.Substring(n)，繼續在剩下待切元句子中自左向右截取長度為n的字串與詞表中的詞條依次匹配。

(b)如果存在str3這樣的詞，則將str2從待切元句子中切分出去，str=str.Substring(n-1)，繼續在剩下待切元句子中自左向右截取長度為n的字串與詞表中的詞條依次匹配。

2)如果詞表中不存在str1，就從該字串最右端部刪去一個字，用n- 2 的字串去詞表中匹配，直至匹配成功。

上述一次回溯分詞算法的流程如圖1所示。

在《人民網》選擇若干篇文章用MM法和一次回溯法切分，選擇其中不同部分切分，如表1所示。

表1 兩種切分效果對比

MM法一次回溯法

有關/責任人/員有關/責任/人員

一萬下/游群眾一萬/下游/群眾

將他/們/救出去將/他們/救出去

最緊/迫/的/任務最/緊迫/的/任務

要得/到/批準要/得到/批準

情況/會/更糟/糕情況/會/更/糟糕

2.3 第二次回溯切分算法描述

對于鏈長大于1的字串，一次回溯切分后可能會產生以單字組成的切分碎片，如“研究生產生活”被切分成“/研究/生/產/生活/”，“生產”是一個詞，被切分成兩個單字。

再進行一次回溯碎片檢查，算法描述如下:

在對每個元句子切分過程中設置一個整型變量，不妨設為tag，初始值為0，在對該句子切分過程中一旦對str2切分，則tag增1，在二次回溯法步驟e)切分元句子結束后檢測tag。如果tag值小于2，則對該句子切分結束;否則用如下二次回溯算法來檢查元句子切分后的含有切分符號“/”的字串:

a)在元句子中進行逆向截取，截取長度為5，如果該字符串不滿足“/單字1/單字2/”結構，則按照步長為1向左平移進行截取，截取字符串長度仍然是5，再進行檢測，直到檢測符合上述結構或元句子被截取完為止。

b)如果該字符串滿足“/單字1/單字2/”結構，則檢測單字1和單字2組合是否是詞。如果是詞則合并該切分，即在元句子中用“/單字1單字2/”替換“/單字1/單字2/”;如果不是詞，則繼續向左平移截取，直至元句子被截取完。

例:“/研究/生/產/生活/” 中“/生/產/”滿足“/單字1/單字2/”結構，且“生產”是詞，則將這兩字合并，即用“/生產/”替換“/生/產/”。

3 二次回溯中文分詞算法分析

3.1 與正向最大匹配法(MM法)異同

1)相同點 都是屬于機械分詞，都是基于對詞典中詞條的匹配結果來切分。

2)不同點 如表2所示。

表2 兩種算法對比

比較項二次回溯法MM法

標點預分割分割不分割

切分方向整體正向+局部回溯正向

詞條優先規則長詞+次長詞協調切分長詞優先切分

其他句尾匹配+碎片檢查無

3.2 算法設計分析

MM法的長詞優先規則大部分情況下能很好地切分，但對于包含有歧義字段的文本往往作出了錯誤的切分，如“原北京市長王岐山”， 其中有詞“原”“北京”“北京市”“市長”“王岐山”(屬于未登錄詞的名字提取，本文不作討論)和“北京市長”構成交集型歧義字段，交集詞為“市”，交段長為1。用MM法切分結果是:“原/北京市/長/王岐山/”，這是錯誤的切分，因此僅僅依靠長詞優先規則無法對歧義字段很好也切分。

二次回溯中文分詞方法則利用長詞、次長詞，二字詞句尾匹配諧調切分，主要從如下方面考慮:

a)文獻[10]中對大量真實語料進行統計，共統計了132 411詞條，詞條的長度分布以及出現頻率如表3所示。

由表3可知:二字詞詞條總數的65891/132411=49.76%，占所有詞條數接近一半之多; 單字詞和二字詞出現頻率之和為96.4%。

MM法采用的長詞優先規則并沒有考慮到詞長分布規律和詞頻統計情況，從而導致MM法的分詞精度不夠。而二次回溯中文分詞方法則綜合考慮最大詞長、次大詞長、二字詞句尾匹配協調切分，更符合真實文本中詞條的分布情況。

b)文獻[11]中以含有約77000詞條的詞庫作為切分詞序對510萬從網上隨機下載的新聞語料進行加工，對交集型歧義字段在大量真實語料中的切分結果進行統計，如表4所示。

由表4可知:鏈長為1的詞也只占歧義字段總數的53.05%，MM法對鏈長為1的歧義字段切分較好，超過1的一般都切分失敗，而二次回溯中文分詞方法對于多鏈長的歧義字段都能較好地識別和切分。

3.3 訓練評測

在中新網、人民網等隨機抽取27篇28541字的真實語料，用二次回溯法和MM法對其中所有交集型歧義字段進行封閉式測試，結果如表5所示。

表5 訓練結果

兩種方法對比詞數

MM法失敗，二次回溯法成功204

MM法成功，二次回溯法失敗25

均切分錯誤33

由表5數據可知:二次回溯法相對于MM法的召回率為86.08%，查準率為89.08%;交集型歧義字段切分上，二次回溯法將MM法切分錯誤率降低了75.53%，即錯誤率降低了3/4以上;由于單純使用正向最大匹配的錯誤率為1/169[6]，以及交集型歧義字段占全部歧義切分字段的85%以上[9]，二次回溯法的切分錯誤率為1/466以下，切分錯誤率遠低于MM法和RMM法。

4 結束語

算法復雜度方面，二次回溯法整個過程沒有對上下文語義、詞性進行分析，僅僅利用詞表進行詞條匹配，因此屬于機械分詞，算法比MM法復雜，但仍然比較簡單且易于實現;切分精度方面，能對交集型歧義字段有效地識別和切分，大大提高了對歧義字段的召回率和查準率。二次回溯法對多義型歧義字段不能有效發現，這同時也是機械分詞的一個難點。今后的工作嘗試將二次回溯法結合文獻[12]所提出基于詞頻統計并具有過濾功能的關鍵詞自動抽取和詞條添加的方法，來進一步提高分詞的召回率和查準率。

參考文獻:

[1]劉群，張華平，俞鴻魁，等. 基于層疊隱馬模型的漢語詞法分析[J]. 計算機研究與發展，2004，41(8):1421-1429.

[2]趙偉，戴新宇，尹存燕，等.一種規則與統計相結合的漢語分詞方法[J].計算機應用研究，2004，21(3):23-25.

[3]羅智勇，宋柔. 現代漢語通用分詞系統中歧義切分的實用技術[J].計算機研究與發展，2006，43(6):1122-1128.

[4]孫茂松，肖明，鄒嘉彥.基于無指導學習策略的無詞表條件下的漢語自動分詞[J].計算機學報，2004，27(6):736-742.

[5]譚瓊，史忠植. 分詞中的歧義處理[J].計算機工程與應用，2002，38(11):125-127.

[6]翟鳳文，赫楓齡，左萬利. 字典與統計相結合的中文分詞方法[J]. 小型微型計算機系統，2006， 27(9):1766-1771.

[7]盧志茂，劉挺，李生. 統計詞義消歧的研究進展[J].電子學報，2006，34(2):333-343.

[8]談文蓉，楊憲澤，談進，等.MIS智能接口中漢語分詞系統的設計與應用[J].計算機科學，2006，33(7):204-206.

[9]孫茂松，黃昌寧，鄒嘉彥.利用漢字二元語法關系解決漢語自動分詞中的交集型歧義[J]. 計算機研究與發展，1997，34(5):332-339.

[10]揭春雨，劉源，梁南元.論漢語自動分詞方法[J].中文信息學報，1989，3(1):1-8.

[11]閆引堂，周曉強.交集型歧義字段切分方法研究[J].情報學報，2000，19(6):637-642.

[12]肖紅，許少華，李欣.具有三級索引詞庫結構的中文分詞方法研究[J].計算機應用研究，2006，23(8):49-51.