基于改進線圖分析算法的淺層漢語句法分析器的設計與實現

摘要：針對傳統的漢語句法分析算法進行改進，采用了自底向上與自頂向下相結合的線圖分析方法，分析、設計和實現了一個漢語句法分析原型系統。該系統實現了基于最大詞長匹配算法的分詞模塊、基于統計方法的詞性標注模塊和基于改進的線圖分析算法的句法分析模塊。最后對系統進行小規模中文文本試驗測試，測試結果表明利用改進的分析算法，使得句法分析效率和分析結果的準確率均有一定程度的提高。

關鍵詞：文本信息處理；漢語句法分析；線圖分析法；句法解析器；句法結構

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

文章編號：1001-3695(2007)09-0164-04

隨著計算機和Internet的推廣應用，由數據處理、信息處理發展到知識處理，對語言文字處理要求的深度和廣度越來越高。漢語句法分析在中文文本信息處理領域中占有十分重要的地位，同時它也是公認的一個研究難題。不同于其他西方語言，漢語有許多特殊之處，吸收其他語言研究成果時需要結合漢語的特點加以研究[1]。當前對漢語的研究主要按照詞、句子和篇章三個層次開展。其中句子的處理在三個層次中起著承上啟下的作用，所以句子處理是一個核心課題。就目前來說，句子處理以自動分詞為基礎，以句法分析和語義分析為核心。本文工作圍繞著句法分析方法和系統展開，句法分析就是應用句法規則和其他知識，將輸入句子中的詞之間的線性次序變換成語法樹形式的數據結構。

目前國內很多有代表性的句法分析系統中的漢語句法分析模塊都是通過改進已有的經典句法分析算法設計的，不少已在實踐中取得了良好的效果[2]。其中，傳統的基于規則的方法占了主導地位，這是因為基于規則的方法從漢語句子最本質的特征出發，如構詞法、詞組構造法、造句法等，從宏觀上總結出句法規則。無論漢語的句式結構多么自由，其中蘊涵的最基本的規則是相對穩定的，而且規則易于表達漢語句子成分的構成規律。另外的原因是，經過長時間的發展和不斷改進，這類方法已較為成熟，應用在一些實用化的系統中有較高的效率。基于此，本文采用基于規則的線圖分析方法進行句法分析，對其改進后，實現了一個句法分析原型系統的開發。

1線圖句法分析算法

線圖(chart)分析算法是最通用、簡單、直觀的句法分析算法。線圖就是一組節點和邊的集合。簡單地說，線圖分析算法是一個由日程表驅動的不斷循環的過程。按照初始化策略對日程表（agenda）進行初始化處理，如果agenda為空，那么分析失敗；否則每次按照日程表組織策略，從日程表中取出一條邊。如果取出的邊是一條非活躍邊而且覆蓋整個句子，那么返回成功，將取出的邊加入到hart中，執行基本策略和規則調用策略將產生的新邊又加入到agenda中[3]。這個算法流程中，各項基本策略均可調整的，通過調整這些策略可以得到改進的chart分析算法。

1．1自頂向下與自底向上的句法分析算法

使用線圖分析算法進行句法分析時，通常采用兩種方式[4]，即自頂向下分析和自底向上分析。

1)自頂向下分析算法在句法分析中，最普通的就是采用自頂向下回溯的分析方法。它逐個地枚舉推導直至找到一個能生成輸入句子結構的推導。自頂向下的分析是從假設出發的，它假定一個節點可以替換下面的節點，從根到葉逐步分枝，從抽象到具體、從整體到部分。目的很明確，就是要找到與葉相適應的句法結構。

2)自底向上分析算法自底向上的并行算法是另一種常用的句法分析方法。這種方法從作為分析對象的句子中的單詞序列出發，以自底向上的方式建立一些局部分析，然后從具體到抽象，一步步地歸并，最后到達根節點S。因此它首先應該使用N、V等最具體的改寫規則，而且要按照規則中箭頭所指的反方向使用規則。

1．2傳統線圖分析算法的優點與不足

傳統線圖分析算法的優點表現在可以表示不相連的子樹。在自然語言分析中，有時局部的結構分析成功了，但總體的結構分析卻不好，使得最后難以形成一棵完整的樹。線圖可以表示不相連的子樹，不一定要求最后必須形成一棵完整的樹，可以把局部分析正確的結構以子樹的形式保存下來，而不至于將前面的分析拋棄。

線圖算法可以直觀地表示具有多個解釋的詞。在線圖中，如果某個詞具有多個解釋，則可以把這些解釋表示為多重的邊，從而將歧義現象清楚地顯示出來。線圖算法靈活，可以通過修改分析中的一些控制策略較容易地進行算法改進。其不足之處在于分析效率低。由于回溯產生的冗余較多，使得分析準確率降低。此外，線圖分析不能避免對一個句子產生多個分析句法樹的問題。

2改進的句法分析算法

自頂向下和自底向上分析算法兩者均不可避免地會產生較多的冗余，從而導致分析效率降低。為了減少冗余、節省時間和空間、提高分析準確率，本文提出一種改進策略，在自底向上線圖分析算法中，引入了自頂向下的預測功能[5]，稱之為自底向上與自頂向下相結合的改進線圖分析算法。

預測是指提出從本間隔點出發向右可能接續的所有活躍邊的列表。尚未驗證的預測保留在表中，已經被驗證或被反駁的預測則從表中劃掉。預測是根據規則進行的，首先從字符間隔1開始向右預測可能要出現一個句子，即預測將有點規則S→·α出現。

a) 如果在字符間隔預測出點規則y→ α·B β，B→ γ∈P，那么從字符間隔i后可能接續點規則B→·γ（α，β可為空，B為非終結符）。

b) 如果在字符間隔i預測出現點規則y→ α·b β，那么在字符間隔i后有可能出現字符b。

重復a)b)直到預測完所有滿足情況的點規則。

改進算法的偽代碼描述如下：

input: Chinese character strings with word segments and parts of speech annotation

output: Chart of syntactic analysis

begin

for(i=0;i<=n;i++)

for every active edge of the form X→X1…·Xk…Xm(px-py) in ActiveArcs do

if Xk is a terminating symbol and p1>py， delete this active edge from ActiveArcs endif

if agenda=，put the part of speech and the left and right interval into agenda endif

choose a element from agenda which is C(p1- p2)

if C matches the form X→·C X1…Xm， add an active edge X→C·X1…Xm(p1-p2) to ActiveArcs and add C(p1-p2) to the chart

elseif C matches any active edge of the form X→X1…·C…Xm(p0-p1) in ActiveArcs， add an active edge X→X1…·C…Xm(p0-p2) to ActiveArcs and add C(p1-p2) to the chart

elseif C matches any active edge of the form X→X1…Xm ·C (p0-p1) in ActiveArcs， add an edge X(p0-p2) to agenda and add C(p1-p2) to the chart endif

if C = S，add C(p1-p2) to the chart endif

endfor

end

下面用一個實例來說明改進的分析算法的工作流程。

考慮一個句子：這個復雜系統可以解決大量問題。

詞典這個：R， 復雜：Adj， 系統：N， 可以：Aux， 解決：V， 大量：Adj， 問題：N

規則庫S→NP VPNP→R Adj N

NP→Adj NVP→Aux VPVP→V NP

在完成分詞和詞性標注之后，這個句子的表現形式變為：1這個/R2復雜/Adj 3系統/N4可以/Aux5解決/V6大量/Adj7問題/N 8。根據改進的分析算法，句法解析器將首先從字符間隔1開始向右預測可能要出現一個句子，即預測將有點規則S→·NP VP出現。由于agenda =，則把下一個詞“這個/R”和下一個字符間隔2入棧。從agenda中選擇成分R記為C(2-3)，由于C與預測的形如NP→·R Adj N的點規則相匹配，增加一個活躍邊NP→R·Adj N(2-3)到活躍邊集合中；然后在字符間隔1和2之間增加一個非活躍邊加入到線圖中。解析器將根據這一流程工作，直到完成最右邊的一個字符間隔后，算法結束。圖1為用改進的分析算法對例句進行分析產生的線圖。

3原型系統的分析、設計與實現

3．1系統目標

漢語句法分析的最終目標是能夠高效準確地分析大規模真實文本。基于規則的漢語句法分析方法雖然能抽象出漢語的句法規則，但卻難以處理分析真實文本中出現的種種復雜現象。目前，由于僅僅基于規則的句法分析系統和分析算法自身的一些缺陷，對于諸如結構歧義、分析效率的問題很難較好地解決。本文設計原型系統時，句法分析模塊采用前面描述的自底向上與自頂向下相結合的改進句法分析方法，從而達到提高正確率和分析效率的目的。

該原型系統的設計目標是分析句子的合理句法結構，有效地處理開放的語料，現階段系統處理的文本單位是單句。

3．2系統功能

通過本系統的工作，主要實現以下幾個功能：

a)給每個輸入的句子S進行分詞。

b)給切分好的詞進行詞性標注。

c)對標注好詞性的句子，用改進的線圖分析算法進行句法分析生成句法樹。

文中構建的句法分析原型系統由詞法分析和句法分析兩大模塊組成。詞法分析模塊中的分詞采用的是最大詞長匹配算法，當輸入一個句子時，該算法在詞庫數據庫中進行相應的搜索，從而將句子分解為一個個獨立的詞。詞法分析模塊中的詞性標注采用的是相對頻率訓練的統計方法，利用已經標注好的語料庫作為訓練語料，從中統計出相關的概率參數，對給定的句子進行詞性標注。句法分析模塊采用的是改進的線圖分析算法，實現對一個單句建立一個句法樹的過程。將已經分詞標注詞性的句子，通過改進的線圖分析算法，運用一套漢語語法規則，實現基于規則的漢語句法分析。圖2描述的是句法分析原型系統總體功能模塊圖。

3．3系統的實現

漢語句法分析原型系統經過調試運行后，得到如圖3所示的系統界面。系統的界面以下拉菜單方式顯示，分別進行分詞、詞性標注和句法分析等操作。圖4為運行系統后，對例句進行句法分析最終得到的樹型結構。

4試驗測試

4．1試驗環境

原型系統是在Windows XP Professional操作系統平臺上，使用VC++ 6.0工具開發的。VC++ 6.0是一個非常強大的開發工具，提供了很多可被直接應用的控件，減輕了編寫程序的工作量，并且其代碼的可重用性好，程序更健壯。本系統的試驗測試也是在Windows XP Professional操作系統下進行的。

4．2試驗數據

4．2．1詞性和短語標記集

為了進行語法研究與信息處理，需要把語法功能（或者說語法性質）相同或者相近的詞歸成一類。這里包含兩項工作：

a)針對漢語詞語的全集，按照某種標準建立一個分類體系。在朱德熙先生的語法理論的指導下，北大計算語言學研究所與中文系合作，經過幾年的研究，提出了一個適用于語言信息處理的現代漢語詞語分類體系。多項語言工程的實踐檢驗了這個詞語分類體系的科學性與可操作性，該詞語分類體系在中文信息處理學界已產生較大的影響。

b)決定該全集中的每一個詞語究竟屬于哪一個詞類[6]。根據這些思想并結合測試語料實際情況，確定了一套小規模詞性標記集和短語標記集，分別如表1和2所示。

4．2．2語料庫

語料庫(corpus)是一個由大量在真實情況下使用的語言信息經過科學的收集和組織而集成的專供研究使用的資料庫[7]。自從20世紀70年代美國制作了著名的brown corpus以來，世界上已制作了各種語料庫。富士通研究開發中心與北京大學計算語言學研究所合作，以人民日報語料為對象，制作大規模漢語標注語料庫，這個語料庫是世界上規模最大的標注語料庫之一。PFR人民日報標注語料庫（v1.0）是在得到人民日報社新聞信息中心許可的條件下，以1998年人民日報語料為對象，由北京大學計算語言學研究所和富士通研究開發中心有限公司共同制作的標注語料庫。本文使用PFR人民日報標注語料庫在其主頁上公開的1998年1月份的語料作為訓練樣本。

4．2．3句型庫和語法規則庫

句型庫也是一個輔助數據庫，根據常用句型總結出了典型句型作為分析對象，句法產生式規則就是在這些典型句型的基礎上總結出來的。本文在常用的29個典型句型的基礎上總結出了33條句法規則用于對系統進行測試。

4．3測試結果與分析

在試驗中，筆者采用的是由16個詞性標記和10個短語標記組成的小規模標記集，對10萬字的語料進行訓練，語料是從PFR人民日報標注語料庫在其主頁上公開的1998年1月份的語料庫中隨機抽取的。將小規模測試集分為6組，每組包括20個句子約160個詞。其中：1、2、3組為封閉測試集；4、5、6組為開放測試集。分別采用傳統的線圖分析算法和改進的分析算法對測試集中的句子進行分析，并將系統自動分析標注和人工標注結果進行比較，利用準確率（precision）和召回率（recall）兩個評價指標對改進的分析算法進行驗證。

當采用同樣的詞性和短語標記集，同樣的標注語料庫作為訓練樣本進行訓練，而采用傳統的線圖分析算法對上述六個測試語料進行試驗時，其測試結果如表4所示。圖5和6為算法改進前后準確率和召回率的比較。

通過對改進算法前后測試結果的比較可以看出，改進之后的句法分析算法在分析的準確率和召回率方面都比改進之前的傳統的線圖分析算法有一些提高，這在一定程度上證明了改進算法的有效性。

5結束語

在進行漢語句法分析的過程中，在傳統的自底向上的線圖分析算法中引入了自頂向下的預測功能。通過這一策略，減少了傳統線圖分析算法中不可避免地出現較多冗余的現象，從而導致分析效率較低的情況。由于冗余線圖的減少，使得不正確的分析結果出現的概率也相應地減小，在使用改進的分析算法進行測試時，句法分析原型系統的準確率有一定的提高。

通過以上試驗測試也注意到，采用改進的句法分析算法進行句法分析的測試結果在某些方面不夠理想，主要體現在某些語料上獲得了較低的準確率和召回率，其主要原因分析如下：

a)在進行測試的過程中，訓練樣本數量較少，標注語料庫基本上是采取手工標注，其精度還不夠理想，因此還需要大量的人工輔助的前期工作。

b)試驗所選取的詞性和短語標記集規模較小，覆蓋面較小，而且，目前國內還沒有一個統一的適合于漢語自動分析和人工標注的加工規范。

c)測試中使用的規則主要來自人工總結，工作量非常的大，并且正確率相對來說不能夠保證。句型庫和規則庫也都依靠人工建立，就個人掌握的非常有限的漢語以及語法句法知識而言，想要達到覆蓋大部分的漢語應用句型以及語法是非常困難的。

總而言之，實現的這個句法分析原型系統還只能處理一些簡單的或與筆者總結的典型句型結構相近或相類似的句子，離處理實際的真實文本還有一定的距離。下一步的工作則是不斷豐富漢語語法知識，并利用更大規模的標注語料庫充實系統的知識庫[8]；此外，基于語料庫的語法規則的自動生成也是筆者今后的研究方向。

參考文獻：

［1］姚天順， 朱靖波. 自然語言理解——一種讓機器懂得人類語言的研究[M]. 2版.北京：清華大學出版社， 2002.

［2］王小捷， 常寶寶.自然語言處理技術基礎[M]. 北京：北京郵電大學出版社， 2002.

［3］侯敏.計算語言學與漢語自動分析[M]. 北京：北京廣播學院出版社， 2000.

［4］BRIAN R. Probabilistic topdown parsing and language modeling[J].Computational Linguistics，2001，17(2):1-28.

［5］劉穎. 計算語言學[M]. 北京：清華大學出版社， 2002.

［6］俞士汶， 朱學鋒， 段慧明. 大規模現代漢語標注語料庫的加工規范[J]. 中文信息學報， 2000，14(6):58-64.

［7］楊惠中. 語料庫語言學導論[M]. 上海:上海外語教育出版社， 2002.

［8］北京大學計算語言學研究所[EB/OL]. http://icl.pku.edu.cn/.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”