基于樹剪枝的典籍文本快速切分方法研究
——以《茶經(jīng)》的翻譯為例

姜 欣，姜 怡 ，方 淼,汪榕培

(1. 大連理工大學(xué) 外語學(xué)院、電信學(xué)院，遼寧 大連 116024；

2. 東北大學(xué) 秦皇島分校 電子信息系，河北 秦皇島 066004)

1 引言

中國浩瀚典籍是中華文化的瑰寶，亟待向世界傳播。可典籍中大量的術(shù)語、典故、專有名詞等造成了典籍在閱讀、理解和翻譯上的困難。以茶文化典籍為例，從唐代陸羽《茶經(jīng)》至清朝的《續(xù)茶經(jīng)》已有幾十部作品，可由于茶文化中一些專業(yè)術(shù)語的存在使得讀者難以準(zhǔn)確迅速地閱讀、理解甚至翻譯，而這構(gòu)成了目前茶文化對外傳播與交流的瓶頸。因此，如何對典籍文本的自動(dòng)切分就成了關(guān)鍵問題。

目前，典籍文本的漢語詞語自動(dòng)切分方法大致可以分成三類：基于詞典的方法[1-4]，基于統(tǒng)計(jì)的方法[5-9]和混合的方法[10-13]?；谠~典的方法主要借助于詞典，遵循一定的匹配原則對文本進(jìn)行掃描，進(jìn)而進(jìn)行文本詞句的劃分，可遺憾的是由于受到詞典的限制，基于詞典的方法難以處理詞典未登錄詞，因此就會(huì)存在語句理解上的歧義。為了解決這種局限性，有學(xué)者借助于統(tǒng)計(jì)模型，利用詞語的概率分布進(jìn)行文本的切分，不受領(lǐng)域和詞典的限制，但是卻需要大量的訓(xùn)練文本，其訓(xùn)練文本的質(zhì)量決定著切分的性能。ICTCLAS作為國內(nèi)外權(quán)威的現(xiàn)代漢語分詞工具，使用詞典和統(tǒng)計(jì)結(jié)合的方法，不需要受到詞典的限制，也不需要訓(xùn)練文本，通過計(jì)算兩個(gè)詞語的出現(xiàn)是否獨(dú)立推斷兩個(gè)字是否能夠形成一個(gè)詞語，能夠有效地從原始語料中獲取術(shù)語、典故和專有名詞。但是由于多詞單元的存在，統(tǒng)計(jì)相關(guān)度量很難自動(dòng)確定詞語的邊界。因此，在課題組使用ICTCLAS對《茶經(jīng)》和清朝文人陸廷燦的《續(xù)茶經(jīng)》進(jìn)行切分的過程中，雖然能得到一些合理的結(jié)果，但是因?yàn)槭艿阶陨碓~典詞語覆蓋面的限制，因而在處理茶典籍中的術(shù)語、典故和專有名詞等問題的時(shí)候效果仍不理想。

為了解決上述問題，本文作者基于樹剪枝的相關(guān)理論,以《茶經(jīng)》的翻譯為例提出了一種新的典籍文本快速切分方法。其基本思想就是利用統(tǒng)計(jì)量似然比λ來計(jì)算相鄰兩個(gè)詞之間的相關(guān)度，然后逐步向多詞單元擴(kuò)展，形成二字乃至多字的候選，然后使用快速的樹剪枝算法尋找典籍文本全局最優(yōu)的劃分，即在全局范圍內(nèi)確定詞語的邊界，進(jìn)而對典籍文本進(jìn)行合理的翻譯。理論分析及實(shí)例表明，該方法可以有效地進(jìn)行典籍文本的快速切分以改善典籍文本翻譯的質(zhì)量。

2 相關(guān)度量和擴(kuò)展計(jì)算

2.1 統(tǒng)計(jì)相關(guān)度量

統(tǒng)計(jì)相關(guān)度量有很多種，如t分布，χ2，似然比λ等。然而，由于似然比λ不需要嚴(yán)格遵循正態(tài)分布并且適合處理稀疏矩陣的特點(diǎn)，能克服數(shù)據(jù)龐大、信息量不易提取的瓶頸，因此在典籍文本的快速切分中具有良好的應(yīng)用前景。為了更好的開展研究，首先給出似然比λ的相關(guān)概念定義[14]。

規(guī)則1設(shè)二元組w1w2為相鄰出現(xiàn)的兩個(gè)詞，規(guī)定

假設(shè)1：如果w2的出現(xiàn)和其前面w1的出現(xiàn)是獨(dú)立的，則p(w2|w1)=p=p(w2|w1)

假設(shè)2：如果w2的出現(xiàn)和其前面w1的出現(xiàn)不是獨(dú)立的，則p(w2|w1)=p1≠p2=p(w2|w1)。

根據(jù)規(guī)則1，用c1,c2和c12分別表示語料庫中w1,w2和w1w2出現(xiàn)的次數(shù)，就可以使用最大似然估計(jì)的方法計(jì)算p,p1和p2，計(jì)算公式如下：

(1)

則在假設(shè)1的條件下，實(shí)際觀測到的w1,w2和w1w2的似然值滿足

L(H1)=b(c12;c1,p)b(c2-c12;N-c1,p)

(2)

在假設(shè)2的條件下，實(shí)際觀測到的w1,w2和w1w2的似然值滿足

L(H2)=b(c12;c1,p1)b(c2-c12;N-c1,p2)

(3)

那么，似然比λ的定義如下：

(4)

表示參數(shù)空間最大似然估計(jì)與全參數(shù)空間最大似然估計(jì)的比值。

對式(4)兩邊同時(shí)取對數(shù)，得到：

試驗(yàn)日糧根據(jù)試驗(yàn)設(shè)計(jì)要求的飼養(yǎng)標(biāo)準(zhǔn)參考NRC(1998)進(jìn)行飼糧的配制（見表1）。4個(gè)組的基礎(chǔ)日糧配方完全相同，對照組不添加蘇氨酸，試驗(yàn)1～3組的蘇氨酸水平分別為0.6%、0.8%、1.0%，4個(gè)組賴氨酸水平均為1.20%。

(5)

其中，L(k,n,x)=xk(1-x)n-k。

由于全空間(p1,p2)是關(guān)于w1先出現(xiàn)時(shí)w2出現(xiàn)的概率p1和其他詞先出現(xiàn)時(shí)w2出現(xiàn)的概率p2的兩維空間，p1=p2是一個(gè)特殊的子空間，則可以根據(jù)觀測數(shù)據(jù)分別計(jì)算子空間和全空間的最大似然值，然后計(jì)算似然比λ。另外，由于-2logλ是漸進(jìn)逼近χ2分布的，因此通過查詢統(tǒng)計(jì)分布表，就可以在給定置信水平α下驗(yàn)證拒絕H1還是拒絕H2。以《茶經(jīng)》的“雋”“永”兩個(gè)單字的翻譯為例，給定置信水平α=0.005，則通過計(jì)算和查表得知可以拒絕H1，接受H2，即認(rèn)為兩者非獨(dú)立出現(xiàn)，臨界值是7.88(自由度為1)。這說明兩個(gè)字很可能構(gòu)成一個(gè)詞，在文章的翻譯的過程中譯成“雋永”的可能性比較大。

2.2 擴(kuò)展計(jì)算

從前述分析可以看出，統(tǒng)計(jì)相關(guān)度量能度量兩個(gè)字之間的相關(guān)度，并由此確定兩詞的詞義。然而在處理三個(gè)字或者更多字組成的詞語翻譯的時(shí)候，這個(gè)度量值的精確度卻會(huì)大大降低，而在典籍文獻(xiàn)中經(jīng)常會(huì)出現(xiàn)三個(gè)字或者更多字組成的詞語，為了計(jì)算三字以上字串的統(tǒng)計(jì)相關(guān)度量的大小，更合理的對典籍進(jìn)行翻譯，就需要對似然比的概念定義進(jìn)行擴(kuò)展。

設(shè)三個(gè)字(w1w2w3)的情況，計(jì)算其λ值可以考慮如下兩種情形：w1w2先結(jié)合，然后再與w3計(jì)算λ值；或者w2w3先結(jié)合，然后再與w1計(jì)算λ值。由此可見，二者可能相同，也可能不同，定義最大的一個(gè)λ值作為w1w2w3的似然比。

同理，對于四個(gè)字(w1w2w3w4)的情況有三種結(jié)合方式，即：w1w2w3作為整體與w4結(jié)合，計(jì)算其λ值；w1w2與w3w4結(jié)合，計(jì)算其λ值；w1與w2w3w4結(jié)合，計(jì)算其λ值。最終，取大的一個(gè)λ值作為w1w2w3w4的似然比。以此類推，五個(gè)字(w1w2w3w4w5)的情況也采用類似的計(jì)算方法。

在實(shí)際應(yīng)用中發(fā)現(xiàn)，典籍文本中五個(gè)字以上的詞語中已經(jīng)很少有單獨(dú)的詞語，大多數(shù)都是組合的詞語，即使是三個(gè)字、四個(gè)字的后選中都有不少是組合的詞語。因此，如果僅僅使用統(tǒng)計(jì)值來推斷是否是詞語或者構(gòu)成術(shù)語、專有名詞等，在典籍文本的劃分過程中就會(huì)出現(xiàn)偏差。因此，為了解決這些候選出現(xiàn)的時(shí)候典籍文本的正確翻譯的問題，需要結(jié)合以上的計(jì)算模型，從全局上考慮最佳的切分。以下就是針對這個(gè)問題進(jìn)行論述。

3 基于樹剪枝的快速切分方法及流程圖

在中國古典文獻(xiàn)中，常常出現(xiàn)一些文言虛詞，這些文言虛詞基本不能明確地表示意義，而只能組織實(shí)詞使句子結(jié)構(gòu)完整，是構(gòu)成文言句子不可或缺的部分。如果它們與其他實(shí)意字之間有很強(qiáng)的相關(guān)性，只會(huì)對結(jié)果造成干擾，因此排除這些詞以及由它們構(gòu)成的多詞單元。

這兩部茶典籍中常見的文言虛詞共有32個(gè)，即“安, 而, 爾, 夫, 蓋, 故, 何, 乎, 或, 即, 既, 莫, 乃, 其,且, 然, 若, 雖, 所, 為, 惟, 焉, 也, 以, 矣, 已, 因, 于, 哉, 則, 者, 之”。因此，在對古文句子進(jìn)行切分的過程中首先排除這些文言虛詞，然后再計(jì)算全局頻繁模式的最佳統(tǒng)計(jì)值λ。其基本算法如下[15]：

設(shè)一個(gè)字串w1w2w3…wn-2wn-1wn是一個(gè)短句，可能的切分如w1/w2/w3/ … /wn-2/wn-1/wn，所有可能的切分是共有2n-1種。設(shè)任意一種切分w1/w2/w3/ … /wn-2/wn-1/wn的關(guān)聯(lián)度量為λ(w1/w2/w3/ … /wn-2/wn-1/wn)，計(jì)算采取如下規(guī)則：如果兩個(gè)字的串形成一個(gè)切分為w1w2，則λ(w1w2)=-2logλ，即前面所求的w1w2關(guān)聯(lián)度量；如果兩個(gè)字的串所形成的切分為w1/w2，由于-2logλ是漸進(jìn)逼近χ2分布的，則假設(shè)λ(w1/w2)=7.8，以最大化兩詞獨(dú)立的情況。

故而，典籍文本的切分問題就形式化為求解一個(gè)最大切分關(guān)聯(lián)度量值的切分，即：

(6)

求解過程可以用一個(gè)樹修剪的方式進(jìn)行，其算法如下：

擴(kuò)展步：字串w1w2…wn的切分可以看作是以w1開始，不斷擴(kuò)展的過程。w1與w2連接的切分有兩種方式w1w2和w1/w2，可以看作w1擴(kuò)展w2之后生成兩個(gè)節(jié)點(diǎn)。w1w2w3的切分方式有四種：w1w2w3，w1w2/w3,w1/w2w3,w1/w2/w3，分別由上面的兩個(gè)節(jié)點(diǎn)生成。以此類推。把w1作為根節(jié)點(diǎn)，w2擴(kuò)展了一個(gè)字之后形成了字串w1w2，而形成兩種切分w1w2和w1/w2，相當(dāng)于生成了兩個(gè)子節(jié)點(diǎn)。同時(shí)，節(jié)點(diǎn)w1w2也可以再擴(kuò)展一個(gè)字w3，生成兩個(gè)切分節(jié)點(diǎn)w1w2w3和w1w2/w3。另外，w1/w2也生成兩個(gè)節(jié)點(diǎn)w1/w2w3和w1/w2/w3，即每個(gè)節(jié)點(diǎn)又生成兩個(gè)子節(jié)點(diǎn)。以此類推，待擴(kuò)展到wn的時(shí)候可以形成一棵滿二叉樹，共有n層，如圖1所示，葉節(jié)點(diǎn)共有2n-1個(gè)，即2n-1種切分。其中，定義生成左子樹的擴(kuò)展為左向擴(kuò)展，生成右子樹的擴(kuò)展為右向擴(kuò)展。

修剪步：由于在一次擴(kuò)展后會(huì)產(chǎn)生2n-1個(gè)節(jié)點(diǎn)，例如在第二層上共有兩個(gè)節(jié)點(diǎn)，w1w2和w1/w2，如果λ(w1w2)>λ(w1/w2)，則w1w2的右向擴(kuò)展總是比w1/w2的右向擴(kuò)展的似然比λ大，那么w1/w2的右向擴(kuò)展將沒有意義，則將w1/w2的右向擴(kuò)展預(yù)先修剪掉，只保留w1w2的右向擴(kuò)展。

搜索：為了實(shí)現(xiàn)高效搜索，采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)中間切分串，即廣度優(yōu)先遍歷全局的二叉樹，在第k層進(jìn)行擴(kuò)展的時(shí)候，把擴(kuò)展結(jié)果存入待擴(kuò)展隊(duì)列中。擴(kuò)展完成之后計(jì)算擴(kuò)展后的k+1層上節(jié)點(diǎn)的λ值，取最大λ值的節(jié)點(diǎn)下一步進(jìn)行雙向擴(kuò)展，其余節(jié)點(diǎn)只進(jìn)行左向擴(kuò)展。如果一個(gè)節(jié)點(diǎn)的切分后最后一個(gè)串等于最長的詞長，將只進(jìn)行右向擴(kuò)展。如w1…/wi-L+1wi-L+2…wi(其中，L為最大詞長)將不再進(jìn)行左向擴(kuò)展。

圖1顯示了整個(gè)算法的基本流程。由整個(gè)擴(kuò)展過程可以看到，由于在每一層上都進(jìn)行預(yù)修剪和根據(jù)詞長修剪，將不再搜索整個(gè)二叉樹上的所有節(jié)點(diǎn)，而只需要計(jì)算1+2+3+L+L+…+L=nL-L(L-1)/2，計(jì)算的時(shí)間復(fù)雜度為o(LN)，L為詞長常數(shù)。相對于計(jì)算所有節(jié)點(diǎn)算法的時(shí)間復(fù)雜度為o(n2) 來說，算法的空間復(fù)雜度變得更為簡單。

圖1 字串切分?jǐn)U展圖

4 實(shí)例分析

為了驗(yàn)證本文所構(gòu)建典籍文本切分方法的合理性和有效性，課題組選取了《茶經(jīng)》《續(xù)茶經(jīng)》和其余28篇茶文，共158 687個(gè)漢字來進(jìn)行分析說明。

首先，使用這些語料計(jì)算二元組、三元組、四元組和五元組候選，共產(chǎn)生候選數(shù)目如表1所示。

表1 候選組數(shù)及閾值

分別采用樹剪枝方法和ICTCLAS對《茶經(jīng)》文本進(jìn)行了切分，切分結(jié)果的準(zhǔn)確性采用準(zhǔn)確率(precision)、召回率(recall)、調(diào)和值(F-score)以及切分效率(Effectiveness)進(jìn)行衡量，如表2所示。

表2 典籍文本切分對比結(jié)果

表2表明，典籍文本的樹剪枝切分方法能有效解決典籍領(lǐng)域的詞語切分問題，和ICTCLAS方法相比，在準(zhǔn)確率、召回率和F值上其效能分別提升了17%、8%、13%，而在切分效率上提升了7%。這說明，本文所提出的典籍文本的切分方法不僅可以提升典籍文本翻譯的效率，而且具有良好的應(yīng)用價(jià)值及應(yīng)用前景。

5 結(jié)論

為了解決典籍文本中大量的術(shù)語、典故、專有名詞等造成的典籍閱讀、理解和翻譯上的困難，本文作者基于樹剪枝的相關(guān)理論和思想，以《茶經(jīng)》的翻譯為例提出了一種新的典籍文本快速切分方法：在采用統(tǒng)計(jì)似然比計(jì)算兩字、多字單元的候選集合的基礎(chǔ)上，使用樹剪枝算法快速求解全局最優(yōu)切分，并以《茶經(jīng)》為例進(jìn)行了算例分析。理論分析及實(shí)例表明，該方法不僅可以有效地進(jìn)行典籍文本的快速切分以改善典籍文本翻譯的質(zhì)量，降低了算法的復(fù)雜度，能較好的解決典籍文本在閱讀、理解和翻譯上的文本切分問題。

然而，在典籍文本中存在一些韻腳用字的相似度問題，而這對于典籍文本的自動(dòng)切分會(huì)造成一些信息量的耦合問題，如何對這樣的問題進(jìn)行深入分析，是需要進(jìn)一步研究的問題。筆者正在做這方面的研究，由于篇幅問題，將另文給出。

[1] 張春霞, 郝天永. 漢語自動(dòng)分詞的研究現(xiàn)狀與困難[J].系統(tǒng)仿真學(xué)報(bào).2005，(1)：138-143.

[2] Robert Dale, Herman Moisl, Harold Somers. Handbook Of Natural Language Processing[M]. New York：Marcel Dekker, Inc. 2000.

[3] David D. Palmer. A trainable rule-based algorithm for word segmentation[C]//Proceedings of the 35th annual meeting of the association for computational linguistics, 321- 328.

[4] 孫茂松, 左正平, 黃昌寧. 漢語自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J]. 中文信息學(xué)報(bào).2000，14(1)：1-6.

[5] 吳勝遠(yuǎn). 獲取最新 一種漢語分詞方法[J].計(jì)算機(jī)研究與發(fā)展.1996，(4)：306-311.

[6] Richard Sproat, Chilin Shih, Willian Gale, et al. A stochastic Finite State word segmentation algorithm for Chinese[J]. Computing Linguist, 1996，(3)：377-404.

[7] 李家福, 張亞非. 一種基于概率模型的分詞系統(tǒng)[J].系統(tǒng)仿真學(xué)報(bào). 2002, (5)：544-550.

[8] Dai Yubin, Loh Teeck Ee, Khoo Christopher. A new statistical formula for Chinese text segmentation incorporating contextual information[C]//Proceedings of the 22ndannual international ACM SIGIR conference on research and development in information retrieval, pp.88-89,1999.

[9] Utiyama Masao, Isahara Hitoshi. A statistical Model for domain independent text segmentation[C]//The annual meeting of the association for computational linguistics and 10thconference of the European chapter of the association for computational linguistics, pp.491-498, 2001.

[10] 趙鐵軍, 呂雅娟,等. 提高漢語自動(dòng)分詞精度的多步處理策略[J].中文信息學(xué)報(bào). 2001，15(1)：13-18.

[11] Zhang Huaping,Yu Hongkui, Xiong Deyi, Liu Qun. HHMM-based Chinese lexical analyzer ICTCLAS[C]//The 2ndSIGHAN workshop in the 41stmeeting of the association for computational linguistics, 2003：184-187.

[12] Christopher D. Manning, Hinrich S., Foundations of statistical natural language processing, MIT press[M]. 1999.

[13] Dunning Ted. Accurate methods for statistics of surprise and coincidence[J]. Computational Linguistics, 1993，1：61-74。

[14] J. Omura and T. Kailath, Some Useful Probability Distributions’ Stanford Electronics Laboratories Stanford[C]//CA, Tech. Rep. No. 7050-6, 1965.

[15] Mingyu Zhong，Michael Georgiopoulos，Georgios C. Anagnostopoulos.A k-norm pruning algorithm for decision tree classifiers based on error rate estimation [J]. Machine Learning, 2008, 71(1)：55-88.