潘 欣,呂靜波,張素莉

(1.長(zhǎng)春工程學(xué)院電氣與信息工程學(xué)院,長(zhǎng)春130012;2.長(zhǎng)春高新區(qū)長(zhǎng)東北核心區(qū)管理委員會(huì),長(zhǎng)春130016)

0 引言

文本分析技術(shù)廣泛應(yīng)用于搜索引擎、文本數(shù)據(jù)挖掘、輿情監(jiān)控等領(lǐng)域。要進(jìn)行文本分析首先要將句子拆分成獨(dú)立的詞。對(duì)于英文等西方語言文本,由于詞和詞之間本身就存在間隔,所以可以直接拆分;對(duì)于中文文本,由于句子是由無間隔的字組成的,所以需要進(jìn)行中文分詞操作[1]。中文分詞操作的基礎(chǔ)就是通過詞典(lexicon)識(shí)別句子中的詞,然后再根據(jù)概率、模糊集、前向和后向匹配等技術(shù)進(jìn)行句子到詞的分解,詞典的質(zhì)量直接決定了分詞的質(zhì)量[2]。

目前,詞典的管理主要面臨的問題是:一方面中文詞匯量十分龐大,不同領(lǐng)域的詞匯難以人工窮舉[3];另一方面,我國(guó)社會(huì)發(fā)展迅速,不同領(lǐng)域新的詞匯層出不窮,僅靠人工搜集與輸入難以完成。要快速、高效地建立詞庫(kù),我們就必須采用一種自動(dòng)化方法自動(dòng)搜集資料、自動(dòng)發(fā)現(xiàn)新詞。

網(wǎng)絡(luò)蜘蛛(Web spider)也叫網(wǎng)絡(luò)機(jī)器人,是一種“自動(dòng)化瀏覽網(wǎng)絡(luò)”的程序,通過網(wǎng)絡(luò)蜘蛛可以自動(dòng)地、遞歸地抓起一組特定的網(wǎng)絡(luò)信息。作為搜索引擎的基礎(chǔ)技術(shù)之一,網(wǎng)絡(luò)蜘蛛在獲取網(wǎng)絡(luò)信息方面發(fā)揮了巨大作用[4]。本研究建立了一種基于網(wǎng)絡(luò)蜘蛛的新詞發(fā)現(xiàn)算法,通過引入網(wǎng)絡(luò)蜘蛛技術(shù)抓取關(guān)鍵網(wǎng)頁(yè)內(nèi)容,再經(jīng)過抽取新詞實(shí)現(xiàn)新詞發(fā)現(xiàn)。實(shí)驗(yàn)表明,本文提出的方法可以從網(wǎng)上快速搜集新詞,獲得的詞典在分詞能力上較傳統(tǒng)方法有很大提高。

1 基于網(wǎng)絡(luò)蜘蛛的新詞發(fā)現(xiàn)算法

1.1 總體算法

基于網(wǎng)絡(luò)蜘蛛的新詞發(fā)現(xiàn)算法共包含3個(gè)模塊(如圖1所示)。

圖1 網(wǎng)絡(luò)蜘蛛的新詞發(fā)現(xiàn)與動(dòng)態(tài)詞庫(kù)管理系統(tǒng)

網(wǎng)絡(luò)蜘蛛模塊,負(fù)責(zé)抓取用戶指定的網(wǎng)頁(yè)信息并去除掉網(wǎng)頁(yè)中的HTML腳本,將網(wǎng)頁(yè)文件轉(zhuǎn)換為純文本文件;新詞發(fā)現(xiàn)模塊讀取所有的文本文件,統(tǒng)計(jì)發(fā)現(xiàn)文本中的新詞;詞庫(kù)管理模塊將新詞有選擇地加入詞庫(kù),并刪除過期的不常用的詞。總體算法如下:

新詞發(fā)現(xiàn)總體算法AutoNewWordExtract

輸入:搜集新詞網(wǎng)站URL,基礎(chǔ)參數(shù);

輸出:發(fā)現(xiàn)新詞并寫入詞典;

(1)WebSpider通過網(wǎng)絡(luò)蜘蛛算法搜集數(shù)據(jù) ;

(2)WordDetect通過統(tǒng)計(jì)分析發(fā)現(xiàn)新詞;

(3)AddNewWord將發(fā)現(xiàn)的新詞加入詞庫(kù)。

1.2 網(wǎng)絡(luò)蜘蛛

本系統(tǒng)網(wǎng)絡(luò)蜘蛛在輸入關(guān)注網(wǎng)頁(yè)之后,進(jìn)行一定深度的廣度優(yōu)先搜索,算法如下:

(5)記錄該URL已經(jīng)抓取完畢,并將T存儲(chǔ)在文件中。

通過該算法,可以輸入一個(gè)起始頁(yè)面、最大搜索深度、不搜索列表。算法根據(jù)該頁(yè)面內(nèi)部的超級(jí)鏈接進(jìn)行廣度優(yōu)先搜索,將搜有獲取的網(wǎng)頁(yè)轉(zhuǎn)換為文本并存儲(chǔ)。

1.3 詞的發(fā)現(xiàn)

詞的發(fā)現(xiàn)算法統(tǒng)計(jì)分析網(wǎng)絡(luò)蜘蛛獲取的文本信息,具體步驟如下:

算法WordDetect

輸入:T(文本列表),N(詞的最大字?jǐn)?shù)),F1(頻度閾值),F2(候選度閾值),F3(關(guān)系閾值)

輸出:L(新詞列表)

(1)讀取 T中的所有文本信息,對(duì)所有2至(N+1)個(gè)漢字的組合進(jìn)行頻度統(tǒng)計(jì),記錄所有頻度大于F的組合。

(2)計(jì)算每個(gè)漢字組合 X的候選程度[5],公式如下:

式中:m——漢字組合X在T中的出現(xiàn)次數(shù);

i——X 的字?jǐn)?shù)。

(3)計(jì)算一個(gè)漢字組合候選程度與包含該組合的父組合的關(guān)系(如“計(jì)算”、“算機(jī)”和“計(jì)算機(jī)”之間的關(guān)系),確定該候選組合是否可以認(rèn)為是一個(gè)獨(dú)立的詞[5]。計(jì)算公式如下:

其中X是Yj的子集,X的字?jǐn)?shù)為i,Y的字?jǐn)?shù)為i+1。當(dāng)DDCFxi較低時(shí)說明該組合是某一個(gè)更長(zhǎng)詞的子組合,不是一個(gè)獨(dú)立的詞。

(4)根據(jù)步驟(2)獲得的每個(gè)組合的候選度,過濾掉候選度低的組合。

(5)根據(jù)步驟(3)獲得的組合關(guān)系值,過濾掉子組合和不是詞的組合(如“算機(jī)”是“計(jì)算機(jī)”子組合,但其DDCF值很低,不是一個(gè)詞)。

(6)輸出獲取到的詞列表。

通過算法WordDetect,在輸入一組文本、各個(gè)候選參數(shù)的閾值之后,可以在發(fā)現(xiàn)文本中出現(xiàn)的詞輸出。

1.4 新詞添加管理

新詞添加的算法如下:

(4)將NL中的所有內(nèi)容追加到詞典D當(dāng)中。

通過新詞的添加算法,可以對(duì)WordDetect算法獲得的新詞列表進(jìn)行判斷,如果某個(gè)詞沒有出現(xiàn)在詞庫(kù)中那么就將其加入到詞庫(kù)之中。

2 新詞發(fā)現(xiàn)實(shí)驗(yàn)

本研究采用Visual Studio 2008集成開發(fā)環(huán)境,通過C#3.5開發(fā)實(shí)現(xiàn)整個(gè)系統(tǒng)。為了測(cè)試本系統(tǒng)的新詞發(fā)現(xiàn)能力,首先通過本系統(tǒng)對(duì)新華網(wǎng)(http://www.xinhuanet.com/)進(jìn)行新詞發(fā)現(xiàn)操作,通過實(shí)驗(yàn)采用的參數(shù)如表1所示。

表1 系統(tǒng)采用的參數(shù)列表

通過該參數(shù),網(wǎng)絡(luò)蜘蛛共獲得27 241個(gè)文本文件;在2 000詞量的測(cè)試詞典基礎(chǔ)上,共獲得82 065個(gè)新詞。通過開源分詞器IKAnalyzer測(cè)試,其采用2 000詞量的詞典與自動(dòng)新詞發(fā)現(xiàn)后的詞典其分詞效果對(duì)比如下:

原句子:阿里巴巴集團(tuán)及公司主要股東雅虎和軟銀一直就支付寶一事進(jìn)行著持續(xù)建設(shè)性的溝通和討論,取得了實(shí)質(zhì)性的進(jìn)展。

2 000 詞量詞庫(kù) :阿/里 /巴 /巴 /集團(tuán)/及/公司 /主要 /股 /東 /雅 /虎 /和 /軟 /銀 /一 /直 /就 /支 /付 /寶 /一/事 /進(jìn)行/著 /持續(xù) /建設(shè)/性 /的/溝通 /和/討論 /,取得/了/實(shí)質(zhì)/性/的 /進(jìn)展。

正確分詞數(shù):11個(gè)

本文提出算法的詞庫(kù):阿里巴巴/集團(tuán)/及/公司/主要/股東/雅虎 /和/軟銀/一直 /就/支付寶/一 /事 /進(jìn)行 /著 /持續(xù) /建設(shè) /性 /的 /溝通 /和 /討論 /,/取得 /了 /實(shí)質(zhì) /性 /的 /進(jìn)展/。

正確分詞數(shù):17個(gè)

從實(shí)驗(yàn)結(jié)果可以看出,本文提出的算法所建設(shè)的詞典可以極大地提供分詞質(zhì)量,尤其是在分析句子中起關(guān)鍵作用的名詞“阿里巴巴”、“支付寶”,以及一些專業(yè)詞匯“股東”都能正確地識(shí)別出來。

3 結(jié)語

本文提出了一種基于網(wǎng)絡(luò)蜘蛛的新詞發(fā)現(xiàn)算法,通過搜集和抓取綜合性的網(wǎng)站的網(wǎng)頁(yè)信息,在經(jīng)過新詞發(fā)現(xiàn)可以獲得大量的詞匯。通過該算法可以自動(dòng)建立高質(zhì)量詞典,為自然語言理解、中文文本挖掘、中文文本分析提供有力支持。

[1]Foo S,Li H.Chinese word segmentation and its effect on information retrieval[J].Information Processing &Management,2004,40(1):161-190.

[2]Lin Y J,Yu M S.Extracting Chinese frequent strings without a dictionary from a Chinese corpus and its applications[J].Journal of Information Science and Engineering,2001,17(5):805-824.

[3]Chen K J,Bai M H.Unknown word detection for Chinese by a corpus-based learning method[J].International Journal of Computational Linguistics and Chinese Language Processing,1998,3(1):27-44.

[4]Rungsawang A,Angkawattanawit N.Learnable topicspecific web crawler[J].Journal of Network and Computer Applications,2005,28:97-114.

[5]Hong C M,Chen C M,Chiu C Y.Automatic extraction of new words based on Google News corpora for supporting lexicon-based Chinese word segmentation systems[J].Expert Systems with Applications,2009,36:3641-3651.