李楠，張凡娜

（商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000）

搜索引擎[1]是在互聯(lián)網(wǎng)上搜集、提取、處理信息的有效方式，隨著互聯(lián)網(wǎng)上信息量的迅速增加、信息組織方式的散列多樣，都對(duì)高效準(zhǔn)確的搜索引擎算法提出了更高的要求，從而更好地服務(wù)用戶(hù)主動(dòng)、快捷地查詢(xún)到所需信息。常見(jiàn)的傳統(tǒng)搜索引擎有網(wǎng)絡(luò)目錄和全文搜索引擎。為了保證查全率，往往盡可能地索引更多的頁(yè)面并根據(jù)一定的規(guī)則計(jì)算反饋結(jié)果與所查信息的相關(guān)度，進(jìn)而排序向用戶(hù)推送結(jié)果，由于相關(guān)度計(jì)算規(guī)則的差異性和簡(jiǎn)單匹配性，導(dǎo)致查詢(xún)結(jié)果的反饋不一定精準(zhǔn)。數(shù)據(jù)量的急劇增加也使得搜索過(guò)程不能迅速完成?；谡Z(yǔ)義的搜索引擎[2-4]相對(duì)傳統(tǒng)搜索引擎大大提高了召回率和精確度，文本相似度的計(jì)算[5]不滿(mǎn)足于簡(jiǎn)單匹配，而更側(cè)重于語(yǔ)義相似性，通過(guò)同義詞詞林[6-7]以及相關(guān)平臺(tái)的詞匯相似度[8]統(tǒng)計(jì)等計(jì)算語(yǔ)義的相似性。使得文本相似度計(jì)算方法更加合理精準(zhǔn)，更適合于知識(shí)密集型領(lǐng)域的應(yīng)用。

1 基于語(yǔ)義的搜索引擎

基于語(yǔ)義的搜索引擎[3]以自然理解技術(shù)為基礎(chǔ)，將信息索引關(guān)鍵詞的層面提升到概念，增強(qiáng)了對(duì)知識(shí)的理解能力。對(duì)自身索引數(shù)據(jù)庫(kù)里的數(shù)據(jù)進(jìn)行語(yǔ)義上的標(biāo)注[4]，對(duì)用戶(hù)查詢(xún)的關(guān)鍵詞進(jìn)行語(yǔ)義分析，在數(shù)據(jù)庫(kù)中搜索相關(guān)聯(lián)的項(xiàng)目，反饋給用戶(hù)。模型結(jié)構(gòu)如圖1所示。

索引數(shù)據(jù)庫(kù)模塊中信息搜索器收集來(lái)自互聯(lián)網(wǎng)的信息，并對(duì)其進(jìn)行整理、去重，生成關(guān)鍵詞。將信息輸送給語(yǔ)義索引器。語(yǔ)義索引器對(duì)信息中的關(guān)鍵詞進(jìn)行提取并作語(yǔ)義標(biāo)記，再將標(biāo)記好的關(guān)鍵詞進(jìn)行分類(lèi)，按照一定類(lèi)別順序存入索引數(shù)據(jù)庫(kù)中。

圖1 基于語(yǔ)義的搜索引擎的模型結(jié)構(gòu)

搜索模塊中,當(dāng)用戶(hù)輸入查詢(xún)內(nèi)容時(shí)，檢索器負(fù)責(zé)對(duì)用戶(hù)搜索內(nèi)容進(jìn)行關(guān)鍵詞的提取，并傳送給轉(zhuǎn)換器。轉(zhuǎn)換器將關(guān)鍵詞轉(zhuǎn)換成語(yǔ)義推理機(jī)能夠識(shí)別的代碼，由語(yǔ)義推理機(jī)進(jìn)行推理、分析，得出用戶(hù)查詢(xún)內(nèi)容的準(zhǔn)確含義，形成關(guān)鍵詞集，語(yǔ)義索引器在索引數(shù)據(jù)庫(kù)中進(jìn)行查找，結(jié)果編輯器對(duì)結(jié)果進(jìn)行編輯整理，最終將查詢(xún)結(jié)果輸送給用戶(hù)。同時(shí)，結(jié)果記憶器記錄用戶(hù)的訪(fǎng)問(wèn)記錄，并將訪(fǎng)問(wèn)結(jié)果返回給索引數(shù)據(jù)庫(kù)，通過(guò)對(duì)比語(yǔ)義索引器所給關(guān)鍵詞，判斷查詢(xún)結(jié)果是否準(zhǔn)確，以此作為依據(jù)，對(duì)語(yǔ)義推理機(jī)進(jìn)行優(yōu)化。

2 基于語(yǔ)義搜索引擎的主要算法

2.1 鏈接分析算法

2.1.1 PageRank 算法

根據(jù)網(wǎng)頁(yè)被鏈接的次數(shù)來(lái)判斷其重要性，以重要性為依據(jù)對(duì)網(wǎng)頁(yè)進(jìn)行排序。PageRank算法[9]在排序之前，會(huì)預(yù)先給每個(gè)網(wǎng)頁(yè)一個(gè)PageRank值一般為PR=1/N，N為網(wǎng)頁(yè)總數(shù)。通過(guò)查看某網(wǎng)頁(yè)被直接或者間接鏈接的次數(shù)，來(lái)計(jì)算PR值，計(jì)算方法如式(1)所示，根據(jù)PR值對(duì)網(wǎng)頁(yè)進(jìn)行排序。

其中，Mpi是鏈接網(wǎng)頁(yè)P(yáng)i的所有網(wǎng)頁(yè)的集合，L(pj)是鏈接網(wǎng)頁(yè)P(yáng)j的網(wǎng)頁(yè)數(shù)目，N是網(wǎng)頁(yè)總數(shù)，α一般取值 0.85。

2.1.2 HITS 算法

HITS算法[10]通過(guò)中心權(quán)威網(wǎng)頁(yè)對(duì)外進(jìn)行鏈接，并將鏈接到的符合題意的頁(yè)面結(jié)果進(jìn)行返回，集中在一個(gè)集合中，返回給用戶(hù)。HITS算法根據(jù)一個(gè)網(wǎng)頁(yè)被鏈接的次數(shù)（入度）以及從此網(wǎng)頁(yè)鏈接向其他網(wǎng)頁(yè)的次數(shù)（出度）來(lái)評(píng)價(jià)這個(gè)網(wǎng)頁(yè)的重要性。同時(shí)，重要網(wǎng)頁(yè)指向的網(wǎng)頁(yè)重要性較高。計(jì)算重要性，需要先計(jì)算各個(gè)頁(yè)面的權(quán)威值和目錄值。設(shè)初始子集的集合P={P1,P2,P3,…,Pn}，根據(jù)頁(yè)面之間的鏈接關(guān)系建立一個(gè)矩陣，如式(2)所示。如果頁(yè)面i有鏈接到頁(yè)面j，則aij的值即為1，反之為 0。

2.2 去重算法

去重算法對(duì)需要測(cè)重的網(wǎng)頁(yè)進(jìn)行HTML項(xiàng)分析，并將網(wǎng)頁(yè)鏈接抽取出來(lái)，上傳給互聯(lián)網(wǎng)?；ヂ?lián)網(wǎng)根據(jù)這個(gè)鏈接調(diào)取索引列表中的其他全部頁(yè)面進(jìn)行重復(fù)性檢測(cè)，將重復(fù)頁(yè)面舍棄。檢測(cè)流程如圖2所示。

根據(jù)文檔中提取出來(lái)的關(guān)鍵信息，將特征點(diǎn)一一羅列出來(lái)，匯集成文檔指紋。并將進(jìn)行過(guò)相似性計(jì)算的其它文檔與這個(gè)指紋進(jìn)行比較，找出相似的文檔。其中，文本相似度算法是去重算法中一個(gè)重要的中間算法，相似度算法越有效，查準(zhǔn)率、查全率就越高。

圖2 重復(fù)網(wǎng)頁(yè)檢測(cè)流程

3 基于語(yǔ)義搜索引擎的文本相似度計(jì)算方法

文本相似度是指兩個(gè)或者多個(gè)文本之間相似程度，介于（0,1）。數(shù)值越小，則文本的相似度越低。文本相似度算法[11]是為了計(jì)算文本相似度以及文章中主要的關(guān)鍵詞。目前，主要有基于向量空間模型的余弦相似度算法和基于語(yǔ)義詞典的語(yǔ)義相似度算法。

3.1 向量空間模型（VSM）的余弦相似度算法

向量空間模型[12]VSM對(duì)文本進(jìn)行分詞處理，在處理好的分詞中找到關(guān)鍵詞并進(jìn)行詞頻統(tǒng)計(jì)。將統(tǒng)計(jì)好的關(guān)鍵詞放置到VSM的各個(gè)維度上，再以余弦相似度為依據(jù)，計(jì)算出文本相似度。主要分為預(yù)處理、關(guān)鍵詞選擇、加權(quán)計(jì)算、對(duì)生成的空間模型進(jìn)行余弦計(jì)算幾個(gè)階段。

預(yù)處理階段對(duì)文本進(jìn)行分詞并去除停用詞。去掉停用詞以及頻率較高的副詞等一些無(wú)實(shí)意的詞后，根據(jù)詞語(yǔ)頻度找出關(guān)鍵詞。關(guān)鍵詞頻為T(mén)F＝S/T，其中S為詞語(yǔ)數(shù)，T為關(guān)鍵詞數(shù)，使用TF-IDF權(quán)值計(jì)算方法進(jìn)行加權(quán)計(jì)算，計(jì)算方法如式(3)所示。

其中，ct是對(duì)關(guān)鍵詞的詞頻信息進(jìn)行歸一化處理，M是文章總數(shù)，St是有關(guān)鍵詞出現(xiàn)的文章數(shù)量。

最后，使用空間模型的余弦算法，將文本之間的運(yùn)算轉(zhuǎn)化成向量之間的運(yùn)算，將抽象問(wèn)題具體化。兩個(gè)文檔W1和W2在空間模型中的向量可以表示為W1=W1[a11,a12,…,a1n]和W2=W2[a21,a22,…,a2n]，計(jì)算兩個(gè)文檔之間的相似度Sim(W1,W2)主要方法：

1）余弦法計(jì)算方法

2）點(diǎn)積法計(jì)算方法

3）Dice相似度計(jì)算方法

3.2 基于語(yǔ)義詞典的語(yǔ)義相似度計(jì)算方法

基于語(yǔ)義詞典的語(yǔ)義相似度算法[8]也是從中文分詞和去除停用詞開(kāi)始，進(jìn)而進(jìn)行權(quán)值運(yùn)算。同時(shí)要去除小權(quán)值的關(guān)鍵詞，然后再根據(jù)詞條建立空間向量，通過(guò)語(yǔ)義相似度的計(jì)算，得出相似度矩陣，進(jìn)而得到LCS（松散耦合系統(tǒng)），最后通過(guò)系統(tǒng)來(lái)計(jì)算兩個(gè)文本的相似度。基本流程如圖3所示。

計(jì)算結(jié)果受到語(yǔ)義關(guān)系、語(yǔ)義距離、節(jié)點(diǎn)深度、節(jié)點(diǎn)密度四個(gè)因素的影響，語(yǔ)義關(guān)系包括繼承關(guān)系、整體與部分關(guān)系和同義詞關(guān)系。語(yǔ)義距離是影響文本相似度之間最重要的因素，是兩個(gè)義項(xiàng)節(jié)點(diǎn)之間路徑的長(zhǎng)度。路徑越大，相似度越低；節(jié)點(diǎn)深度是義項(xiàng)與樹(shù)根路徑之間所經(jīng)過(guò)的邊數(shù)。深度越深，兩個(gè)義項(xiàng)的相似度越大。節(jié)點(diǎn)密度是兩個(gè)義項(xiàng)擁有的共同祖先的子節(jié)點(diǎn)的個(gè)數(shù)，節(jié)點(diǎn)的子節(jié)點(diǎn)密度越小，相似度越大。

圖3 基于語(yǔ)義詞典的語(yǔ)義相似度算法流程圖

文本相似度可以從詞語(yǔ)相似度、句子相似度以及段落相似度等方面進(jìn)行判斷。通過(guò)文本中關(guān)鍵詞的編碼方式對(duì)詞語(yǔ)進(jìn)行相似度處理，提取語(yǔ)義上的關(guān)聯(lián)性進(jìn)而擴(kuò)充到文本相似度的計(jì)算上。并將其具體應(yīng)用到語(yǔ)義搜索引擎的檢索上，使其能夠通過(guò)用戶(hù)訪(fǎng)問(wèn)信息的關(guān)鍵詞的關(guān)聯(lián)性在索引庫(kù)中搜索相關(guān)的結(jié)果，并推送給用戶(hù)。

4 基于語(yǔ)義搜索引擎的詞語(yǔ)相似度計(jì)算方法

詞語(yǔ)相似度[8]是文本相似度的基礎(chǔ)。詞語(yǔ)相關(guān)度和詞語(yǔ)相關(guān)性是影響詞語(yǔ)相關(guān)度的兩個(gè)重要指標(biāo)。一般通過(guò)詞語(yǔ)之間的距離來(lái)判斷詞語(yǔ)相關(guān)性。

每個(gè)詞語(yǔ)都有一個(gè)或者多個(gè)義項(xiàng)。而在計(jì)算詞語(yǔ)之間相似度時(shí)，需要用到所有的義項(xiàng)?；谡Z(yǔ)義搜索引擎根據(jù)同義詞詞林中詞語(yǔ)義項(xiàng)的編碼以及兩個(gè)義項(xiàng)的語(yǔ)義距離，計(jì)算義項(xiàng)相似度。同義詞詞林遵循樹(shù)狀層次結(jié)構(gòu)將所有的詞條組織收錄在一起，層層結(jié)構(gòu)逐級(jí)遞增，對(duì)詞義的刻畫(huà)也越來(lái)越細(xì)致，要對(duì)義項(xiàng)進(jìn)行相似度計(jì)算，首先需要根據(jù)兩個(gè)義項(xiàng)編碼在哪層開(kāi)始不同來(lái)判斷兩個(gè)義項(xiàng)在哪層分支上。例如：Ea02A03與Ea02B03，因?yàn)樵诘?層編碼開(kāi)始不同，則從第4層開(kāi)始分支。從第1層開(kāi)始，相同則系數(shù)乘以1，不同則乘以所在分支層對(duì)應(yīng)的系數(shù)，再乘以調(diào)節(jié)參數(shù)，如果義項(xiàng)A和B不在詞林中的同一棵樹(shù)上，則相似度,如果在詞林中的同一棵樹(shù)上并且在第2層分支上，系數(shù)為2，則相似度如式(7)所示：

詞語(yǔ)相似度的計(jì)算主要是通過(guò)語(yǔ)義詞典對(duì)義項(xiàng)[8]的計(jì)算來(lái)實(shí)現(xiàn)的，在對(duì)文本進(jìn)行相似度比較之前，可以對(duì)文本進(jìn)行分詞、去除停用詞等處理，這樣就可以將文本劃分成單個(gè)的詞語(yǔ)。通過(guò)語(yǔ)義詞典比較詞語(yǔ)之間的相似度，判斷兩個(gè)文本中最相似的關(guān)鍵詞進(jìn)行相似度計(jì)算[12]。

5 實(shí)驗(yàn)結(jié)果與分析

通過(guò)實(shí)驗(yàn)，使用C++語(yǔ)言實(shí)現(xiàn)了空間向量模型的文本相似度算法，結(jié)構(gòu)如圖4所示。

圖4 基于向量空間模型相似度算法結(jié)構(gòu)

在本模型中，先對(duì)輸入的文本進(jìn)行分詞、去除停用詞等一系列處理，根據(jù)詞頻計(jì)算公式統(tǒng)計(jì)詞語(yǔ)頻度，找出關(guān)鍵詞，并以數(shù)組的形式返回。建立關(guān)鍵詞的空間模型，根據(jù)公式計(jì)算出文本之間的內(nèi)積和余弦值，最后根據(jù)計(jì)算出來(lái)的閾值來(lái)判斷文本之間的相似度。在實(shí)驗(yàn)中，主要針對(duì)空間向量模型建立空間模型，運(yùn)用向量?jī)?nèi)積來(lái)計(jì)算余弦值，求出文本的相似度。

實(shí)現(xiàn)算法過(guò)程中，先通過(guò)判斷兩個(gè)文本的長(zhǎng)度，如果文本的長(zhǎng)度<1,則直接返回，不進(jìn)行結(jié)果集的運(yùn)算，如果文本的長(zhǎng)度>1，則繼續(xù)進(jìn)行相似度運(yùn)算。

在進(jìn)行相似度運(yùn)算之前，先對(duì)文本1進(jìn)行判斷，將文本1的關(guān)鍵詞取出，以數(shù)組的形式返回，然后對(duì)數(shù)組進(jìn)行遍歷，根據(jù)關(guān)鍵詞對(duì)文本1,2的值進(jìn)行匹配，如果值存在則進(jìn)行計(jì)算累計(jì)求和，如果值為空則移除。

使用相同的方法對(duì)文本2進(jìn)行判斷，最后將文本1,2求出的數(shù)據(jù)進(jìn)行開(kāi)平方根計(jì)算，得到相似度的結(jié)果。

程序中閾值是用來(lái)衡量相似度大小的度量值。當(dāng)設(shè)置閾值為0.5時(shí)，收錄的結(jié)果為相似度大于0.5的所有結(jié)果。實(shí)驗(yàn)中選擇了25個(gè)文檔進(jìn)行測(cè)試，當(dāng)閾值為0.5時(shí)運(yùn)行結(jié)果，如表1所示。

表1 閾值為0.5時(shí)的實(shí)驗(yàn)結(jié)果

通過(guò)程序?qū)崿F(xiàn)了文本相似度算法的計(jì)算，結(jié)果顯示，文本相似度介于（0,1），值越接近1，說(shuō)明相似度越高；值越接近0，則相似度越低。在本次驗(yàn)證中，設(shè)置閾值為0.5，對(duì)于計(jì)算出的相似度低于0.5的，則結(jié)果會(huì)自動(dòng)去除，不顯示在文檔中。所以，顯示出來(lái)的相似度值均為0.5以上。如0017＆0025，表示的是文檔17與文檔25之間的相似度為 0.56。

設(shè)置不同的閾值，搜索出的相似文本數(shù)量也會(huì)有所變化，根據(jù)統(tǒng)計(jì)，不同閾值所檢索出的相似文檔數(shù)量，如表2所示，通過(guò)對(duì)比，可以看得出來(lái)，閾值越高，查出的相似文檔的對(duì)數(shù)越少，對(duì)文檔相似的要求越嚴(yán)格，閾值越低，越容易被認(rèn)定為相似文檔。從實(shí)驗(yàn)結(jié)果可以看出，傳統(tǒng)的搜索引擎在搜索過(guò)程中，只能找出完全匹配的相似文檔，不能找出同義詞或者知識(shí)性相同表達(dá)不同的相似文檔，影響文本搜索的準(zhǔn)確性和完整性。在基于語(yǔ)義的搜索引擎算法中，根據(jù)反饋結(jié)果可以選擇合適的閾值，獲取到準(zhǔn)確完整的數(shù)據(jù)信息。

表2 不同閾值所對(duì)應(yīng)的相似文檔對(duì)數(shù)

6 結(jié)論

本文深入分析了基于語(yǔ)義的搜索引擎算法和基于空間向量模型的文本相似度算法，總結(jié)了基于語(yǔ)義詞典的語(yǔ)義相似度算法在計(jì)算文本相似度的算法流程，使用C++語(yǔ)言，實(shí)現(xiàn)了文本相似度的計(jì)算，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。實(shí)驗(yàn)結(jié)果表明基于語(yǔ)義詞典的語(yǔ)義相似度能夠?qū)崿F(xiàn)文本相似度的有效計(jì)算，從而實(shí)現(xiàn)更快速、準(zhǔn)確地檢索。為了保證語(yǔ)義相似度計(jì)算的全面性，需要經(jīng)常更新詞典信息庫(kù)，并通過(guò)詞語(yǔ)之間的差異，找出新的計(jì)算方法。