劉 暢，張 猛

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

0 引言

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

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

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

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

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

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

3 改進(jìn)中文分詞算法

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

圖1 樹(shù)狀詞庫(kù)示意圖Fig.1 Tree thesaurus diagram

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

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

1)將要進(jìn)行分詞處理的中文全文按照標(biāo)點(diǎn)符號(hào)分解為獨(dú)立的單句，使處理的中文句子更短，從而提高全文檢索的效率;

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

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

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

4 實(shí)驗(yàn)結(jié)果比較分析

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

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

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

5 結(jié)語(yǔ)

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

［1］劉件，魏程.中文分詞算法研究［J］.微計(jì)算機(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］張磊，張代遠(yuǎn).中文分詞算法解析［J］.電腦知識(shí)與技術(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］周程遠(yuǎn)，朱敏，楊云.基于詞典的中文分詞算法研究［J］.計(jì)算機(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ī)制［J］.中國(guó)科學(xué)院研究生院學(xué)報(bào)，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)狀及未來(lái)發(fā)展［J］.科技廣場(chǎng)，2009(11):222-225.XIONG Quan-hao.Overview of Chinese Word Segmentation ［J］.Science Mosaic，2009(11):222-225.

［7］祁文青.一種改進(jìn)的中文分詞算法［J］.黃石理工學(xué)院學(xué)報(bào)，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.