垂直搜索引擎中的分詞算法研究

潘磊寧 方建安 金林駿

（上海市東華大學(xué)信息科學(xué)與技術(shù)學(xué)院 上海 201620）

0 引言

近年來(lái)，爆炸式增長(zhǎng)的信息和不斷發(fā)展的互聯(lián)網(wǎng)技術(shù)，使得 WEB的信息量急劇增長(zhǎng)，格式以及內(nèi)容不斷翻新，而通用搜索引擎由于存儲(chǔ)、計(jì)算資源和帶寬等方面的問(wèn)題想要檢索互聯(lián)網(wǎng)上全部的網(wǎng)頁(yè)是不可能的[1]。從海量的信息中準(zhǔn)確快速地搜索出特定的內(nèi)容十分困難，如何從網(wǎng)絡(luò)中的海量信息里快速而有效地查詢到所需有價(jià)值的信息己成為人們關(guān)注的重點(diǎn)[2]。

垂直搜索引擎具有專、精、深的特點(diǎn)，可通過(guò)面向某一特定的領(lǐng)域、人群或需求僅搜索網(wǎng)絡(luò)中的特定主題信息。它采用主題爬蟲(chóng)對(duì)特定主題的網(wǎng)頁(yè)進(jìn)行抓取，對(duì)特定的領(lǐng)域進(jìn)行了專業(yè)的過(guò)濾和篩選，使得某一特定領(lǐng)域內(nèi)信息更加全面和深入，并且它可以聚合信息、處理索引，提供有價(jià)值的相關(guān)服務(wù)和信息，從而提高用戶檢索時(shí)的準(zhǔn)確率[3]。因此，為了滿足特定領(lǐng)域的用戶需求，保證檢索結(jié)果的專業(yè)性，人們開(kāi)始對(duì)垂直搜索引擎進(jìn)行研究。

面向主題的垂直搜索引擎與通用搜索引擎存在如下差別：首先，通用搜索引擎面向任何用戶提供對(duì)任何信息的查詢，而垂直搜索引擎則面向?qū)I(yè)用戶向他們提供對(duì)其所在專業(yè)的信息檢索；其次，通用搜索引擎對(duì)網(wǎng)絡(luò)進(jìn)行逐頁(yè)的爬行，試圖遍歷整個(gè)Web。而垂直搜索引擎則采用一定的策略預(yù)測(cè)相關(guān)網(wǎng)頁(yè)的位置，動(dòng)態(tài)地調(diào)整網(wǎng)頁(yè)爬行方向，使系統(tǒng)盡可能的在與主題相關(guān)的網(wǎng)頁(yè)集中的地方爬行，這將節(jié)約大量的網(wǎng)絡(luò)資源。最后，通用搜索引擎對(duì)硬件的需求過(guò)大，而垂直搜索引擎由于沒(méi)有遍歷整個(gè)Web節(jié)約了大量的網(wǎng)絡(luò)資源，而且沒(méi)有自己的大型索引數(shù)據(jù)庫(kù)所以硬件需求也比較低。因而，研究垂直搜索引擎具有很好的現(xiàn)實(shí)意義。

分詞技術(shù)是任何一個(gè)垂直搜索引擎的“靈魂”，能否將檢索請(qǐng)求中的關(guān)鍵字通過(guò)正確的理解從句子中正確切分出來(lái)并進(jìn)行匹配查找，是一個(gè)搜索引擎能否得到正確結(jié)果的關(guān)鍵過(guò)程。分詞的準(zhǔn)確與否會(huì)直接影響到檢索結(jié)果的正確率，因此文中將主要研究垂直搜索引擎中分詞技術(shù)的算法的改進(jìn)，并通過(guò)實(shí)驗(yàn)驗(yàn)證其有效性。

1 現(xiàn)有的分詞算法

現(xiàn)有的中文分詞算法主要可分為三大類：基于字符串匹配的分詞算法、基于理解的分詞算法和基于統(tǒng)計(jì)的分詞算法。

基于字符串匹配的分詞算法：基于字符串匹配的分詞算法是指與已有詞典里的詞進(jìn)行一一匹配，匹配上的詞輸出到結(jié)果，匹配不上的詞常以單字的形式輸出，它通過(guò)對(duì)已有詞典的機(jī)械匹配來(lái)得到分詞結(jié)果。按照掃描方向的不同，可以分為正向匹配和逆向匹配；按照優(yōu)先匹配算法不同，可以分為最大匹配和最小匹配。

基于理解的分詞算法：基于理解的分詞算法讓計(jì)算機(jī)模擬人對(duì)句子的理解，達(dá)到識(shí)別詞的效果，基本思想是在識(shí)別詞的同時(shí)進(jìn)行句法、語(yǔ)義分析，利用句法和語(yǔ)義信息來(lái)處理歧義。這種分詞算法需要大量的語(yǔ)言知識(shí)和信息，由于中文的復(fù)雜性，計(jì)算機(jī)很難成功地模擬理解語(yǔ)義，目前還處在實(shí)驗(yàn)階段。

基于統(tǒng)計(jì)的分詞算法：詞是穩(wěn)定的字的組合，在上下文中相鄰的字同時(shí)出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個(gè)詞，因此字與字相鄰共現(xiàn)的概率能較好地反映成詞的可信度?；诮y(tǒng)計(jì)的分詞算法對(duì)文本中相鄰共現(xiàn)的字的組合進(jìn)行統(tǒng)計(jì)，記錄計(jì)算兩個(gè)或多個(gè)漢字相鄰共現(xiàn)的概率，當(dāng)這一概率超過(guò)某一閾值時(shí)，認(rèn)為這一字組構(gòu)成了詞。這一分詞算法不需切分詞典，但可能會(huì)誤認(rèn)一些共現(xiàn)概率高的字組為詞，比如“我的”等，并且算法的時(shí)間和空間開(kāi)銷都較大。在實(shí)際使用中，經(jīng)常將這一算法與基于字符串匹配的分詞算法相結(jié)合，既發(fā)揮基于字符串匹配的分詞算法分詞速度快、效率高的優(yōu)點(diǎn)，又利用了基于統(tǒng)計(jì)的分詞算法結(jié)合上下文識(shí)別生詞、消除歧義的優(yōu)點(diǎn)。

中文分詞的一個(gè)巨大非技術(shù)障礙乃是分詞規(guī)范和標(biāo)準(zhǔn)問(wèn)題，雖然中文分詞已經(jīng)有很多年的研究歷史，但是迄今為止國(guó)內(nèi)仍沒(méi)有一個(gè)公開(kāi)的、受到廣泛認(rèn)可的、可操作的分詞規(guī)范，也不存在一個(gè)通用的大規(guī)模評(píng)測(cè)資料。這使得眾多研究者的研究結(jié)果之間缺乏真正的可比性，從而制約了中文分詞技術(shù)的提高，能夠真正公開(kāi)為大眾所用的較好的分詞工具很少。

2 改進(jìn)的分詞算法

2.1 理論基礎(chǔ)

字是組成文本的最小元素，詞語(yǔ)是字為表示特定概念按照一定順序組合在一起所形成的文字序列，設(shè)所有字的集合為Z={z1, z2, z3,...,zn}，則一個(gè)詞 wi可以表示為 zi1zi2zi3...zik，其中 zij∈ Z，并記詞的集合為 W={w1, w2, w3,...,wm}。對(duì)于比較復(fù)雜的詞語(yǔ)也可以通過(guò)詞或字的相互組合來(lái)表示，比如w1= z1z2， w2= z3z4z5， w3=z1z2z3z4z5，則 w3= w1w2， w3= z1z2w2， w3= w1z3z4z5。

設(shè) wi=zi1zi2zi3...zik是可以提取的一個(gè)文字序列，定義該文字序列在所有文本集中出現(xiàn)的頻率為該文字序列的支持度，即支持度Support( wi)=，其中是文本集 T的文本總數(shù)量，freq( wi)是文本集 T中出現(xiàn)文字序列 wi的文本數(shù)量，即該序列在一個(gè)文本中出現(xiàn)的概率 S upport( wi)= P( wi)。根據(jù)貝葉斯概率公式，文字序列的支持度又可表示為Support( wi)= P ( zi1zi2zi3...zik)= P ( zi1zi2...zij)*P( zij+1zij+2...zik| zi1zi2...zij)，記子序列 w=z z...z，i1i2ij w=zij+1zij+2...zik，則有 P( wi)= P ( w)*P ( w|w)，或者

對(duì)于任意一個(gè)文字序列 wi=zi1zi2zi3...zik，可以將其拆分成多個(gè)子序列，如果存在一個(gè)拆分wi= zi1zi2zi3...zik= zi1zi2...zijzij+1zij+2...zik= ww，并且 w、 w都是一個(gè)詞語(yǔ)，則稱為一個(gè)文字序列 wi的一個(gè)有效拆分。

根據(jù)關(guān)聯(lián)規(guī)則理論，強(qiáng)關(guān)聯(lián)規(guī)則應(yīng)同時(shí)滿足最小支持度閾值和最小置信度兩個(gè)條件，本文將強(qiáng)關(guān)聯(lián)規(guī)則作為衡量文字序列是否可以稱為詞語(yǔ)的依據(jù)，根據(jù)關(guān)聯(lián)規(guī)則理論如果一個(gè)文字序列能同時(shí)滿足最小支持度和最小置信度兩個(gè)條件，那么該文字序列可作為一個(gè)獨(dú)立的詞語(yǔ)存在；最小支持度與最小置信度是文字序列成為詞語(yǔ)的充分必要條件。在現(xiàn)實(shí)文本中，存在大量高頻短語(yǔ)，但如果某高頻短語(yǔ)能拆分成更加高頻的詞語(yǔ)，那么使用該高頻短語(yǔ)作為獨(dú)立詞語(yǔ)的意義將被消弱，相反對(duì)于一些不可拆分的短語(yǔ)，如果在文本中經(jīng)常出現(xiàn)，那么它將很有必要作為一個(gè)詞語(yǔ)來(lái)使用。

2.2 改進(jìn)算法的描述

挖掘關(guān)聯(lián)規(guī)則的通用算法是一種計(jì)算量比較復(fù)雜的算法，比如Trie字典樹(shù)算法等，由于詞語(yǔ)本質(zhì)上就是連續(xù)的多個(gè)字組成的序列，在詞語(yǔ)中字與字之間存在嚴(yán)格的順序關(guān)系，本文在Trie字典樹(shù)算法基礎(chǔ)上，提出一種專門(mén)處理中文本文詞語(yǔ)的改進(jìn)分詞算法。與Trie字典樹(shù)算法類似，該算法挖掘關(guān)聯(lián)規(guī)則的過(guò)程為先找到滿足最小支持度的頻繁集，并構(gòu)造Trie樹(shù)，然后由頻繁集產(chǎn)生同時(shí)滿足最小支持度和最小置信度的強(qiáng)關(guān)聯(lián)規(guī)則來(lái)發(fā)現(xiàn)詞語(yǔ)。

但不同的是Trie字典樹(shù)算法是按照項(xiàng)目出現(xiàn)的頻率大小順序創(chuàng)建字典樹(shù)，而該算法首先找出可能的所有階的頻繁集，并將頻繁集按照字序列中字的順序存儲(chǔ)到字典樹(shù)中；Trie字典樹(shù)算法是按照深度優(yōu)先的規(guī)則遍歷字典樹(shù)，而該算法按照寬度優(yōu)先的規(guī)則逐層遍歷字典樹(shù)，判斷文字序列是否能構(gòu)成強(qiáng)關(guān)聯(lián)規(guī)則，將構(gòu)成強(qiáng)關(guān)聯(lián)規(guī)則的文字序列確認(rèn)為詞語(yǔ)并保存在字典樹(shù)中，否則刪除該序列。

2.3 改進(jìn)算法的具體構(gòu)建

2.3.1 獲取文字序列

2.3.2 建立字典樹(shù)

字典樹(shù)在文本挖掘中經(jīng)常使用，它將文字序列放在一個(gè)樹(shù)結(jié)構(gòu)中，每個(gè)字對(duì)應(yīng)樹(shù)中的一個(gè)節(jié)點(diǎn)，前后兩個(gè)字在樹(shù)結(jié)構(gòu)中構(gòu)成父子節(jié)點(diǎn)關(guān)系，并通過(guò)hash表存儲(chǔ)每個(gè)節(jié)點(diǎn)所擁有的孩子節(jié)點(diǎn)。一個(gè)獨(dú)立的子序列在字典樹(shù)中對(duì)應(yīng)一個(gè)從根節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)的鏈路，并在序列末尾對(duì)應(yīng)節(jié)點(diǎn)上標(biāo)記該序列出現(xiàn)的頻率，通過(guò)字典樹(shù)可以快速查找某個(gè)文字序列是否出現(xiàn)在集合中。

2.3.3 分詞

該算法在挖掘強(qiáng)關(guān)聯(lián)規(guī)則的過(guò)程是逐層處理的，首先遍歷字典樹(shù)中由兩個(gè)字組成的序列，根據(jù)置信度計(jì)算公式，計(jì)算每個(gè)序列的置信度，判斷是否構(gòu)成強(qiáng)關(guān)聯(lián)規(guī)則，若構(gòu)成強(qiáng)關(guān)聯(lián)規(guī)則則選定為詞語(yǔ)，否則刪除該子序列，然后依次遍歷三個(gè)和更多個(gè)字組成的序列的置信度。在分階挖掘詞語(yǔ)時(shí)，遍歷字典樹(shù)的過(guò)程使用寬度優(yōu)先遍歷算法，經(jīng)過(guò)寬度優(yōu)先遍歷算法遍歷字典樹(shù)之后，字典樹(shù)中剩余的文字序列均構(gòu)成詞語(yǔ)，再次遍歷字典樹(shù)可獲取所有挖掘出來(lái)的詞語(yǔ)。

3 改進(jìn)分詞算法的效果

語(yǔ)言模型的有效性一般通過(guò)考察準(zhǔn)確率和召回率來(lái)衡量，準(zhǔn)確率就是抽取正確的詞語(yǔ)數(shù)量與所有抽取的詞語(yǔ)數(shù)量的比值，召回率是自動(dòng)抽取并出現(xiàn)在人工詞表中的詞語(yǔ)數(shù)量與人工詞表數(shù)量的比值，即召回率=抽取正確的詞語(yǔ)數(shù)量/所有抽取的詞語(yǔ)數(shù)量，召回率=自動(dòng)抽取并出現(xiàn)在人工詞表中的詞語(yǔ)數(shù)量/人工詞表數(shù)量。

這里做了個(gè)實(shí)驗(yàn)，是在相同閾值情況下與N-gram模型的對(duì)比，為驗(yàn)證本文提出的算法的有效性，實(shí)驗(yàn)樣本取自新浪新聞網(wǎng)（sina.com.cn）的2萬(wàn)篇中文網(wǎng)頁(yè)，根據(jù)經(jīng)驗(yàn)，該算法最小支持度取值0.005，最小置信度取值0.1，同時(shí)使用分別基于二元模型和三元模型的N-gram算法，詞頻閾取值20。在同樣的硬件環(huán)境中分別運(yùn)行三種算法模型，并記錄各自抽取的詞語(yǔ)數(shù)量和運(yùn)行時(shí)間，同時(shí)采用隨機(jī)抽樣方式統(tǒng)計(jì)構(gòu)詞詞語(yǔ)的有效性，結(jié)果對(duì)比如下表所示：

算法 詞數(shù) 準(zhǔn)確率 召回率 有效性二元N-gram算法 26789 0.678 0.689 0.671三元N-gram算法 19002 0.742 0.637 0.683改進(jìn)的算法 26227 0.765 0.672 0.768

由上表可以看出，與常用的 N-gram算法相比，本文提出的改進(jìn)分詞算法更有效，獲取的詞語(yǔ)也更全面，同時(shí)能保持較高的運(yùn)行效率。

4 結(jié)束語(yǔ)

為了提高垂直搜索引擎的檢索效率，本文先是充分分析了現(xiàn)有的分詞算法，并且介紹了有關(guān)的關(guān)聯(lián)規(guī)則理論，然后在此基礎(chǔ)上提出了一種改進(jìn)的詞算法。與最常用的是N-gram語(yǔ)言模型相比，該算法不受N值限制，可以從大量文本中自動(dòng)快速獲取文本中常用的詞語(yǔ)，并構(gòu)成詞庫(kù)。本文在最后通過(guò)實(shí)驗(yàn)證明該算法比N-gram語(yǔ)言模型更有效，獲取的詞語(yǔ)更全面，同時(shí)能保持較高的運(yùn)行效率。

[1]繆丹，李天瑞.面向商品比價(jià)應(yīng)用的垂直搜索引擎系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn).西南交通大學(xué)研究生學(xué)位論文.2012，5.

[2]趙立磊，潘東華.基于網(wǎng)頁(yè)去重的垂直搜索引擎設(shè)計(jì)與實(shí)現(xiàn).大連理工大學(xué)研究生學(xué)位論文.2012，6.

[3]Paolo Boldi，Bruno Codenotti，Massimo Santini and Sebastiano Vigna.Ubicraw ler：A scalable fully distributed web craw ler.Software：Practice &Experience.2004，8.