劉 暢，張 猛

(1.吉林工商學(xué)院信息工程學(xué)院，長春130062;2.吉林大學(xué)網(wǎng)絡(luò)中心，長春130012)

0 引言

全文檢索系統(tǒng)的研究主要是為降低全文檢索的空間占用率，提高檢索的速度，使用戶在海量的網(wǎng)絡(luò)信息中快速找到相關(guān)數(shù)據(jù)。國外學(xué)者對全文檢索系統(tǒng)的研究和應(yīng)用已經(jīng)有幾十年的歷史，相對比較成熟。中文全文檢索系統(tǒng)的使用原理和方法與英文全文檢索系統(tǒng)相似，但由于中文的語義是由單個漢字和詞組構(gòu)成，而且彼此之間沒有分隔符，所以使用相對復(fù)雜。

筆者主要研究分析中文全文檢索系統(tǒng)的應(yīng)用、索引數(shù)據(jù)結(jié)構(gòu)中順序表［1］和倒排表［2］的原理，對基于字索引［3］和基于分詞的中文檢索技術(shù)進行比較，在此基礎(chǔ)上提出了一種改進的中文分詞算法。通過實驗比較證明，改進的中文分詞算法是一種更為高效的中文全文檢索分詞算法。

1 全文檢索技術(shù)的概述

全文檢索是指以全文本為檢索對象，通過掃描全文本中的每個字或詞，找到相關(guān)信息提交給用戶的方法。全文檢索主要包括建立索引和搜索索引兩個過程，而在中文全文檢索過程中找到適合的關(guān)鍵字建立索引項是成功檢索的關(guān)鍵。目前建立索引的方法主要包括建立順序表和倒排表兩種方法。建立順序表主要是通過對全文本進行從頭到尾的查看，直到找出要尋找的字符串，相當(dāng)于建立文本到字符串的映射，這種方法比較原始和簡單，適合文件量較小的對象，雖然比較直接和快捷，但是，如果文檔量大，則使用相當(dāng)繁瑣。建立倒排表是將全文非結(jié)構(gòu)化的數(shù)據(jù)提取出一部分，按照某種結(jié)構(gòu)重新進行排列，這個過程叫做索引，然后再對索引進行搜索，從而快速找到要尋找的字符串，相當(dāng)建立字符串到文本的映射。因此，全文索引是指計算機索引程序通過掃描文章中的每個詞，對每個詞建立一個索引，指明該詞在文章中出現(xiàn)的次數(shù)和位置。當(dāng)用戶查詢時，檢索程序根據(jù)事先建立的索引進行查找，并將查找結(jié)果反饋給用戶的檢索方式。這個過程類似于通過字典中的檢索字表查字的過程。在全文檢索建立索引的過程中有基于字索引和分詞索引兩種方式，字索引就是以單個漢字作為索引項，優(yōu)點是容易建立索引，但匹配的準確性不高;目前大多數(shù)學(xué)者認為中文全文檢索技術(shù)應(yīng)該以詞為基本索引項，這符合中國人的語言習(xí)慣，便于提高匹配的準確性，但要想實現(xiàn)以詞為建立索引的基本項，分詞技術(shù)是關(guān)鍵。

2 中文全文檢索系統(tǒng)中的分詞技術(shù)

目前，針對中文分詞技術(shù)的研究和應(yīng)用已取得了一些成果，提出了一些有效的中文分詞算法，主要包括3大類:基于詞典的分詞算法［4］(正向最大匹配算法、逆向最大匹配算法);基于統(tǒng)計的分詞算法［5］(互信息概率統(tǒng)計算法、組合度的決策算法)和基于規(guī)則的分詞算法［6］。以上算法奠定了中文全文檢索技術(shù)的使用基礎(chǔ)，但通過應(yīng)用證明每種算法在歧義處理、字長限制和使用耗時上都存在一些不足，筆者提出的改進中文分詞算法，可在不影響歧義包容和字長限制的基礎(chǔ)上提高中文全文檢索的效率。

3 改進中文分詞算法

在目前已有的中文分詞算法基礎(chǔ)上，筆者提出了一種改進中文分詞的算法 樹狀詞庫分詞算法［7］，它基本具備了中文分詞的高效性、無長度限制和歧義包容的特性。在這種算法中建立索引的過程是要建立文本中相關(guān)詞與詞庫的映射，在改進的中文分詞算法中對詞庫進行改造，使之更好地與相關(guān)詞進行映射，以便于實現(xiàn)中文分詞。詞庫是關(guān)系數(shù)據(jù)結(jié)構(gòu)中的層次數(shù)據(jù)庫［8］，需要把所有相關(guān)詞在層次數(shù)據(jù)庫中按字分解，圖1是一個示例。

圖1 樹狀詞庫示意圖Fig.1 Tree thesaurus diagram

在示例中方形內(nèi)的文字表示在樹形結(jié)構(gòu)上是可組成詞組的，如“長春”、“吉林”等，而矩形內(nèi)的文字在樹形結(jié)構(gòu)上是不能單獨組成詞組使用的，如“長春大”、“長春公”，所以方形內(nèi)的文字是終止符。任何一個句子都會打散成單字與樹狀結(jié)構(gòu)的單字匹配，詞的長度變成了樹的高度，每次的匹配變成了樹的遍歷，并且這種遍歷的效率都是線性的。這里要做的只是取出每個字去樹上找到相應(yīng)的匹配，每次的匹配代價都是O(1)(如果詞庫用Hash表的話)，這樣匹配的時間復(fù)雜度就是字符串本身的長度。對于長度為n的字符串來說，其分詞復(fù)雜度是O(n)，而最大匹配的平均復(fù)雜度是O(n2)［9］。

改進的中文分詞算法的設(shè)計步驟如下:

1)將要進行分詞處理的中文全文按照標點符號分解為獨立的單句，使處理的中文句子更短，從而提高全文檢索的效率;

2)將要處理的單句在樹狀結(jié)構(gòu)中遍歷，在遍歷的過程中如果找到匹配的字，則繼續(xù)執(zhí)行，如果遇到方形內(nèi)的文字(終止符)，則為一個完整的詞，所以可把這個詞作為一個分詞。

從分詞后的下一字開始繼續(xù)做步驟2)的遍歷，如此循環(huán)往復(fù)就將詞分完。

核心算法構(gòu)造如下:

4 實驗結(jié)果比較分析

在實驗中選取的中文來自我國的古典名著，按照字節(jié)計數(shù)選定相同數(shù)據(jù)的長度，在實驗室的一臺PC機上進行幾種中文全文索引結(jié)構(gòu)中分詞算法的比較實驗，實驗結(jié)果如表1所示。

由表1得知，對相同字節(jié)計數(shù)長度的中文文本，在保證無長度限制和歧義包容的特性基礎(chǔ)上，改進中文分詞算法的耗時為已有中分分詞算法的1/2和1/5。

表1 中文分詞算法耗時比較Tab.1 Time-consuming comparison of Chinese segmentation algorithm

5 結(jié)語

筆者提出的改進的中分分詞算法 樹狀詞典中文分詞算法，能在保證中文文本歧義包容和無長度限制的基礎(chǔ)上縮短了中文全文檢索的耗時，提高中文全文檢索的速率，是一種更為有效的中文全文檢索分詞算法。

［1］劉件，魏程.中文分詞算法研究［J］.微計算機應(yīng)用，2008，29(8):11-16.LIU Jian，WEI Cheng.Arithmetic Research on Chinese Segmentation ［J］.Microcomputer Applications，2008，29(8):11-16.

［2］張磊，張代遠.中文分詞算法解析［J］.電腦知識與技術(shù)，2009(1):192-193.ZHANG Lei，ZHANG Dai-yuan.Chinese Lexical Analysis Algorithm ［J］.Computer Knowledge and Technology，2009(1):192-193.

［3］孫鐵利，劉延吉.中文分詞技術(shù)的研究現(xiàn)狀與困難［J］.信息技術(shù)，2009(7):187-189，192.SUN Tie-li，LIU Yan-ji.State of the Art and Difficulties in Chinese Word Segmentation Technology ［J］.Information Technology，2009(7):187-189，192.

［4］周程遠，朱敏，楊云.基于詞典的中文分詞算法研究［J］.計算機與數(shù)字工程，2009(3):68-71，87.ZHOU Cheng-yuan，ZHU Min，YANG Yun.Research on Chinese Word Segmentation Algorithm Based on the Dictionary［J］.Computer＆ Digital Engineering，2009(3):68-71，87.

［5］吳晶晶，荊繼武，聶曉峰，等.一種快速中文分詞詞典機制［J］.中國科學(xué)院研究生院學(xué)報，2009，26(5):703-711.WU Jing-jing，JING Ji-wu，NIE Xiao-feng，et al.Fast Dictionary Mechanism for Chinese Word Segmentation［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2009，26(5):703-711.

［6］熊泉浩.中文分詞現(xiàn)狀及未來發(fā)展［J］.科技廣場，2009(11):222-225.XIONG Quan-hao.Overview of Chinese Word Segmentation ［J］.Science Mosaic，2009(11):222-225.

［7］祁文青.一種改進的中文分詞算法［J］.黃石理工學(xué)院學(xué)報，2007(4):23-25，37.QI Wen-qing.An Improved Maximum Matching Method for Chinese Word Segmentation ［J］.Journal of Huangshi Institute of Technology，2007(4):23-25，37.

［8］ZHANG Meng，HU Liang，LI Qiang.Weighted Directed Word Graph［C］∥Proceedings 16th Annual Symposium，CPM 2005.Jeju Island，Korea:Springer，2005:156-167.

［9］PAOLO FERRAGINA，GIOVANNI MANZINI，VELI MAKINEN.An Alphabet-Friendly FM-Index［C］∥Proceedings:11th International Conference，SPIRE 2004.Padova，Italy:［s.n.］，2004:150-160.