具有三級索引詞庫結構的中文分詞方法研究

（大慶石油學院 計算機科學系， 黑龍江 大慶 163318）

摘 要：提出了一種分組并具有三級索引結構的詞庫組織體系，給出了合適的索引密度間隔；針對系統基本詞庫的擴充問題，考慮了一種基于詞頻統計并具有過濾功能的關鍵詞自動抽取和小詞條添加方法。大量仿真實驗結果表明，采用該方法可較大提高中文文本的切詞速度及信息的查全查準率。

關鍵詞：中文切詞； 正向最大匹配； 詞庫； 索引密度； 全文檢索

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

文章編號：1001 3695(2006)08 0049 03

Study on Chinese Word Segmentation Based on Key word Library Having Three Level Index

XIAO Hong， XU Shao hua， LI Xin

(Dept. of Computer Science， Daqing Petroleum Institute， Daqing Heilongjiang 163318， China)

Abstract:In this article，we’ll give a method of organizing words library using three level index，and also give the appropriate index density interval; Aim at the expansion of words library， we consider the method of key words auto extraction and small words addition basing on word frequency statistics and having filtration function. A large number of simulation experiments show that this method can improve the speed of Chinese word segmentation and the recall ratio and precision ratio of information.

Key words:Chinese Word Segmentation; Forward Maximum Method; Words Library; Index Density; Full text Retrieval

隨著信息技術和計算機網絡技術的迅速發展，人們獲取信息的手段和方法也在不斷改進和提高。各種信息檢索系統的出現，特別是搜索引擎工具的出現，改變了人們對信息獲取的方式和途徑?；赪WW的全文檢索系統及搜索引擎是一個復雜的信息處理系統，涉及多個環節和多種關鍵技術，分詞技術（也稱切詞）是其中最基本和最重要的技術之一。分詞是建立搜索引擎索引器和查詢器的基礎，高效準確的切詞方法和分詞詞庫組織結構是提高搜索效率和文獻全文檢索查全查準率的關鍵環節。

目前針對基于WWW的中文全文檢索和搜索引擎的設計已有多種分詞方法，其中基于詞庫中詞條模式匹配的文本分詞方法是一種最基本也是最為成熟的分詞方式，但這種方法對大文本的切詞效率較低[1]。同時，這種方法對文本的切詞效果完全依賴于系統的基本詞庫，當基本詞庫的結構組織不合理或詞庫中存儲的詞條滿足不了對某一領域信息查詢的需要時，將影響到對信息的查全查準率。雖然人們作了各種改進，但一些問題還沒有得到很好的解決，例如歧義詞識別、新詞識別及在文本切詞過程中向詞庫自動添加新詞等。針對這些問題，筆者提出了一種基于分組并具有三級索引的詞庫組織體系結構，并輔以單字附加庫來縮小進行匹配的詞條范圍，從而可較大提高對文本的分詞速度；同時采用詞條匹配與詞頻統計相結合的方法提高對歧義詞和新詞的識別率。應用中，采用基于統計的詞條自動抽取和過濾方法，可實現對基本詞庫新詞的自動添加。仿真實驗結果表明，采用該方法可較大提高中文文本的切詞速度及信息的查全查準率。

1詞庫結構和組織

在基于詞庫的詞條模式匹配分詞方法中，詞條的組織和詞庫結構的設計是否合理是影響文本分詞效率和信息查全查準率的一個重要因素[2]。理論上詞庫中的詞條越多，切詞的效果就越好。但是隨著詞條數的增加，切詞過程需要過多的模式匹配，切詞效率呈下降趨勢；而詞條過少，使得一些詞語無法切分，影響對文本信息的查全。針對這一問題，筆者設計了一種分組并具有三級索引的詞庫組織體系結構。

整個詞庫采用線性表來組織，并通過分組和加索引的方法來提高詞庫的檢索速度，以減少進行匹配的詞條數。詞庫中每一個詞條保存一個記錄，一個記錄項包括WordID（詞的ID，唯一標志）和詞。為了加快切詞速度，整個詞庫都駐留內存，存放在一個統一的線性鏈表結構中，在組織鏈表時首先將詞庫按字數進行分組，相同字數的詞條放在同一組中，同一組中的各詞條按漢字內碼進行排序，這樣組織詞表可方便地在詞表上添加索引。

詞庫上添加的索引分三級，一級索引表示各組的位置，即各長度（詞條字數）的詞條開始位置；二級索引表示同一組內不同漢字開頭的詞條位置，如詞庫中以“人”開頭的詞條很多，則二級索引中必有一個是表示以“人”開頭的詞開始的位置。在漢字中兩字詞條占了約70%以上，五六字以上的詞條顯得很少，因而二級索引在這些分組中的效果不是很明顯，而且在占絕大多數的二字詞條中各字開頭的詞條個數不均，多則上百，少則只有一兩個詞，這種情況下不能發揮二級索引的作用，因而再定義一級三級索引，這種索引在二級索引和三級索引之間定義的，在同一組內的各詞條上每隔一定的間隔取一個詞添加到三級索引中。各級索引都記錄了各詞條在線性表中的下標和詞條漢字內碼。索引關系如圖1所示。

2新詞的自動抽取與添加

在應用中，由于建立的檢索系統初始基本詞庫不一定滿足實際信息檢索的需要，可能有一些重要的詞條（關鍵詞）沒有被添加進詞庫。本文設計了一種基于詞頻統計并可進行濾波的詞條自動抽取方法。具體實現步驟如下：

（1）首先將文本中的系詞、前置詞、冠詞、代詞等詞類去掉，將形容詞或副詞與其修飾的詞結合在一起當作一個復合詞。

（2）對文本從頭開始逐詞順序往下掃描，并按下列方法進行統計：

①每個詞在其第一次出現時設一個相應的計數器，并置為1。此后該詞每出現一次就在其相應的計數器中加1；

②在標題或摘要（如果有的話）中出現的詞，除同①中的處理外，再在相應的計數器中外加一個整數T；

③在段首或段尾出現的詞，除同①中的處理外，再在相應的計數器中外加一個整數P；

④在引言和結論段中出現的詞，除同①和③中的處理外，再在相應的計數器中外加一個整數I；

⑤根據受限自然語言理解技術，找出文本中的一些關鍵句，例如那些包含諸如“關鍵在于…”，“旨在…”，“主要目的（標）是…”等句子。對在關鍵句中出現的詞，除同上①、②、③、④中的處理外，再在相應的計數器中外加一個整數K；

⑥對于一些特殊的領域，根據受限自然語言理解技術和有關知識，設立其他方案；

（3）處理同義詞或轉義詞。在出現的多個同義詞或轉義詞中選擇計數器的積分最高者，保留該詞和相應計數器，然后把其他同義詞或轉義詞的計數器中的計分全部加入保留計數器中。

（4）處理近義詞。在出現的多個近義詞中選擇計數器的積分最高者，保留該詞和相應計數器，然后對其他近義詞根據其與保留的近義詞的語義近似程度（用一個接近1的小數θ表示，這要根據實際問題來決定），將其計數器中的計分乘以θ之后加入保留的計數器中。

（5）歸一化。將所有詞的計數器的計分相加得到和數S，然后每個計數器的計分除以S再放入計數器。

（6）截取關鍵詞：設定閾限λ（一個選定在[0，1]區間中的小數），進行“λ 濾波操作”，即把關鍵字集中出現頻率小于λ（0＜λ≤1）的關鍵詞濾掉，僅選取那些計數器的計分大于等于λ的詞作為關鍵詞。

將新抽取出的關鍵詞經與基本詞庫中詞條比較后，把未在基本詞庫中出現過的詞條添加進詞庫，再以此詞庫作為新的基本詞庫。這樣在實際應用中，可不斷擴充檢索系統的詞庫，提高信息的查全率。

3分詞算法的設計與實現

3．1分詞算法設計

基于字串的匹配方法實際上是一個在詞表上查找的過程，詞表相當于一個查找表。因此，匹配速度主要取決于查找表的組織方法和查找策略。在字串的匹配中，最理想的是通過哈希函數一次即定位到查找表中匹配元素，但在實際切詞過程中目前還沒有一種算法可以做到這一點。因此，盡可能地縮小查找范圍是提高匹配效率的一種有效方法。在詞庫（查找表）上建立三級索引，由于詞表是按字數分組的，所以一級索引是各分組開始的位置，根據詞的字數可用哈希函數直接定位到分組的起始位置。二級索引是建立在各詞首漢字上的，可根據首漢字內碼值，同樣采用哈希函數，在確定了一級索引后再根據待匹配串的首漢字就能找到二級索引，進一步縮小了匹配范圍。在現代漢語中有些開頭的詞過多，在這種情況下二級索引不是很有效，可再對第二個漢字同樣按漢字內碼建立一個三級索引，這樣根據待匹配串的第二個漢字找到三級索引，因為三級索引的密度最大不超過50，這樣在最復雜的情況下最多匹配50次。而實際中一般匹配不會超過20次，這樣可有效減少匹配次數，提高文本的分詞速度。具體實現過程如下：

設D為詞典，max表示D中的最大詞長，Buffer為待切分的字串。每次從Buffer中取長度為max的子串與D中的詞進行匹配。若成功，則該子串為詞，將Buffer的指針后移max個漢字后繼續匹配；否則子串逐次減1進行匹配直到只有一個漢字為止[3，4]。為提高切分效率，不采用逐次減一個字的方法，而是使用正向逐一增長的方法。其整個切詞過程如下：

（1）將詞庫讀入內存。讀入詞庫是切詞的第一步，為了提高整個切詞的速度，可將整個詞庫一次性讀入內存，并常駐內存。雖然增加了空間開銷，但可提高時間效率。在詞表上建立相應的三級索引并取得所有詞條中最大詞的長度。

（2）讀入要切分的中文文本數據。對于待切分的文本數據按行進行處理，每處理一行時先將字符數據讀入緩沖區，并進行相應的字符集轉換。由于漢字是用雙字節表示的，因此要將單節表示的字符串轉換成多字節字符集。

（3）句子切分。首先從文本緩沖Buffer中取出max長度的子串，根據子串的長度采用哈希函數計算出一級索引的位置，再根據第一個漢字的內碼同樣采用哈希函數計算出二級索引的位置，進而計算出三級索引，最終確定在詞庫表中進行匹配的詞條的上下界（也就是查找區間的線性表下標）。確定上下界后采用二分查找法進行匹配，若在此區間內匹配成功則切分出了一詞，否則將匹配子串從右邊去掉一個漢字后繼續進行匹配，直到將整個句子切分完畢。每切分出一個詞，就將詞的WordID和詞在文本中出現的位置存放到外部文件或數據庫中，以便索引器根據切分出的結果建立索引，進而讓查詢器根據索引進行查詢。

3．2分詞算法的改進

從測試結果可以看出，在詞庫中加三級索引可明顯改變切分速度。但三級索引的密度間隔對速度的影響不是一個正比關系，當達到一定的峰值后，減小間隔切分速度反而會降低。因此，選擇合適的索引密度間隔是提高切分速度很重要的一步。實驗結果表明，當三級索引的密度間隔設為20時其切分效率是最高的。

由于本文采用的切詞方法是基于詞庫的模式匹配方法，對于一些新詞或詞庫中不存在的詞無法識別，因而可采用一種智能方法來識別新詞和詞庫中不存在的詞。這種改進方法是增加一個附加庫，這個庫存放漢語中的所有標點符號和單字的連詞、介詞、助詞、語氣詞、擬聲詞和嘆詞。借助這個附加庫對于找不到切分匹配的字符串，再查找這樣的子串，它的前后均不是詞庫中的詞條，而是附加庫中的單字，且中間沒有任何附加庫中的字元，則這個子串就很可能是一個新詞或不在詞庫中存在的詞。統計這個子串在整篇文章中出現的頻率，若頻率較高則一定是一個新詞，這種將詞庫與詞頻統計相結合的方法增加了新詞的識別率。通過實驗證明這種改進方法能夠識別80%以上的新詞，這對于切詞方法是一種很好的改進。

4測試結果與分析

根據上述分析和實現過程，筆者采用VC6．0編制了相應的分詞系統算法程序。系統基本詞庫以文本文件方式組織，初始詞庫包含53000個詞條。選擇一篇具有919個中文文字的文檔，在P4 2．0GHz/256MB內存的機器上進行測試，結果如表1所示。

從表1所列結果中可以看出，索引對整個切詞效率的影響明顯。如果不加任何索引，則每次匹配時都要與數據庫中的所有詞條進行匹配，切詞速度很慢；當詞庫進行分組加上三級索引后，切分速度便明顯提高。

5結束語

中文分詞是中文信息處理的基礎，有著重要的應用價值。目前廣泛使用的智能中文輸入法、文本校對、拼音標注、文本分類等，都需要有分詞系統的支持[1]。本文提出的分組并具有三級索引結構的詞庫組織體系，以及基于詞頻統計并具有過濾功能的關鍵詞自動抽取和詞條添加方法，與目前廣泛使用的基于詞庫的模式匹配單一方法相比，可較大提高對中文文本的切詞速度和信息查全率。

參考文獻：

[1]李東，張湘輝.漢語分詞在中文軟件中的廣泛應用[EB/OL].微軟中國研究開發中心網站.

[2]李慶虎，陳玉健，孫家廣.一種中文分詞詞典新機制——雙字哈希機制[J].中文信息學報，2003，17(4):13-18.

[3]吳棟，滕育平.中文信息檢索引擎中的分詞與檢索技術[J].計算機應用，2004，24(7).

[4]湛燕，陳昊，袁方，等.基于中文文本分類的分詞方法研究[J].計算機工程與應用，2003，(23):87-89.

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

作者簡介：肖紅（1979-），女，講師，碩士，主要從事中文信息處理、數據挖掘理論及應用方面的研究；許少華（1962-），男，教授，博導，博士，主要從事數據庫、人工智能與神經網絡理論及應用方面的研究；李欣（1979-），男，講師，碩士，主要從事中文信息處理、數據挖掘理論及應用方面的研究。

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