基于TF-IDF算法的分層搜索引擎設(shè)計(jì)?

（江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212003）

1 引言

目前，在互聯(lián)網(wǎng)上搜集、提取、處理信息的最常用的方式是使用搜索引擎［1］。隨著互聯(lián)網(wǎng)上信息量的迅速增加，以及信息組織方式變得愈加散列和多樣性，要求搜索引擎算法必須更加的高效準(zhǔn)確［2］。

為此，各國(guó)學(xué)者對(duì)其進(jìn)行了大量研究，提出了許多搜索引擎算法與框架。如基于分類目錄、文本檢索的方法［3］；使用基于網(wǎng)頁(yè)被訪問(wèn)概率的PageR?ank算法［4］；通過(guò)網(wǎng)頁(yè)被鏈接的數(shù)量和質(zhì)量來(lái)確定搜索結(jié)果的排序權(quán)重的Hilltop算法［5］等。

本文提出了一種基于詞語(yǔ)頻率-逆文檔頻率（Term Frequency-Inverse Document Frequency，TF-IDF）算法的分層搜索引擎設(shè)計(jì)方案。該方案分為兩個(gè)階段。在第一階段，利用網(wǎng)絡(luò)爬蟲技術(shù)爬取網(wǎng)絡(luò)詞條，并構(gòu)造一個(gè)語(yǔ)料庫(kù)粗燥集；在第二階段，則基于TF-IDF算法在本地對(duì)語(yǔ)料庫(kù)進(jìn)行精確高效搜索，得到與待搜索語(yǔ)句最相近的結(jié)果。實(shí)驗(yàn)中，將該搜索引擎應(yīng)用于百度百科［6］的有關(guān)詞條。整個(gè)搜索過(guò)程顯示在基于Flask框架構(gòu)建的本地Web上，能夠提供給用戶良好的搜索輸入環(huán)境與搜索結(jié)果顯示區(qū)域，點(diǎn)擊搜索結(jié)果可以進(jìn)入詳細(xì)顯示頁(yè)面。

2 TF-IDF算法

在信息檢索中，TF-IDF算法是一種采用詞語(yǔ)加權(quán)方案的數(shù)字統(tǒng)計(jì)方法，旨在反映單詞對(duì)集合或語(yǔ)料庫(kù)中文檔的重要性［7］。它通常用作搜索信息檢索、文本挖掘和用戶建模的加權(quán)因子。TF-IDF值與單詞在文檔中出現(xiàn)的次數(shù)成比例地增加，并且被包含該單詞的語(yǔ)料庫(kù)中的文檔數(shù)量抵消，這有助于調(diào)整某些單詞通常更頻繁出現(xiàn)的實(shí)際情況［8］。

搜索引擎可使用TF-IDF加權(quán)方案或其變體作為在給定用戶查詢的情況下對(duì)文檔的相關(guān)性進(jìn)行評(píng)分以及排序。TF-IDF可以成功地用于各種主題領(lǐng)域的停用詞過(guò)濾，包括文本摘要和分類。通過(guò)對(duì)每個(gè)查詢項(xiàng)的TF-IDF求和來(lái)計(jì)算最簡(jiǎn)單的排名函數(shù)，許多更復(fù)雜的排名函數(shù)是這個(gè)簡(jiǎn)單模型的變體［9］。

2.1 TF-IDF的定義

通常，TF-IDF可表示為統(tǒng)計(jì)量詞語(yǔ)頻率和逆文檔頻率的乘積形式。這兩個(gè)統(tǒng)計(jì)量有多種計(jì)算方式來(lái)確定其數(shù)值。

2.1.1 詞語(yǔ)頻率TF

對(duì)于詞語(yǔ)頻率，最簡(jiǎn)單的選擇是使用文檔中出現(xiàn)詞語(yǔ)的原始計(jì)數(shù)［10］。例如，若詞語(yǔ)t在文檔d中出現(xiàn)tft,d次，那么即可定義詞頻tf(t,d)=tft,d。其他的定義方案如下：

1）布爾頻率。

2）根據(jù)文件長(zhǎng)度調(diào)整的詞語(yǔ)頻率。

3）對(duì)數(shù)縮放頻率。

4）為防止因文檔d過(guò)長(zhǎng)導(dǎo)致的偏差使用的帶偏置的詞語(yǔ)頻率。

2.1.2 逆文檔頻率IDF

逆文檔頻率衡量單詞提供的信息量，可以用來(lái)度量一個(gè)詞語(yǔ)的普遍重要性［11］。某一特定詞語(yǔ)在語(yǔ)料庫(kù)中的IDF，可以使用文件的總數(shù)除以語(yǔ)料庫(kù)中詞語(yǔ)出現(xiàn)的文檔的個(gè)數(shù)的對(duì)數(shù)來(lái)表示，即：

其中，t為某一特定詞語(yǔ)，D為語(yǔ)料庫(kù)整體，d為某一文件，N為語(yǔ)料庫(kù)中的文檔總數(shù)，N=|D|，nt=|d∈D:t∈d|為語(yǔ)料庫(kù)D中詞語(yǔ)t出現(xiàn)的文檔的個(gè)數(shù)。

同樣IDF也有多種的定義方案，如：

1）一元定義。idf(t,D)=1即詞語(yǔ)t再語(yǔ)料庫(kù)D中必定出現(xiàn)了

2）平滑的逆文檔頻率。

3）逆文檔頻率的最大值。

4）概率逆文檔頻率。

2.1.3 詞語(yǔ)頻率-逆文檔頻率TF-IDF

TF-IDF定義為tf(t,d)詞語(yǔ)頻率和idf(t,D)

逆文檔頻率兩個(gè)統(tǒng)計(jì)量的乘積，即：

當(dāng)詞語(yǔ)t在給定的文檔d中出現(xiàn)的頻率愈高，則tf(t,d)值愈大；當(dāng)詞語(yǔ)t在語(yǔ)料庫(kù)集中出現(xiàn)頻率越小，則idf(t,D)值愈大；此時(shí)TF-IDF的權(quán)重越大，詞語(yǔ)t更能代表文檔d。反之，則相反。TF-IDF這個(gè)權(quán)重因此可以區(qū)別出其余普通的詞語(yǔ)［12］。

并且idf(t,D)的log中的值往往大于等于1，因此tfidf(t,d,D)的值大于等于0。詞語(yǔ)出現(xiàn)的文檔數(shù)越多，idf(t,D)的log中的值越接近1，則tfidf(t,d,D)的越接近0，表示該詞語(yǔ)t對(duì)于區(qū)分文檔的作用越小。

在得到GMC的估計(jì)量后，我們還需要確定帶寬。帶寬的選擇可以采用Sain等(1994)提出的方法，該方法可以通過(guò)R軟件的“ks”包實(shí)現(xiàn)，也可以采用交叉驗(yàn)證法來(lái)選擇。由于E(Y|X)=minl(x)(Y-l(X))2,E(X|Y)=minl(Y)(X-l(Y))2我們可以選擇h使得h滿足

本文在計(jì)算tf(t,d)和idf(t,D)時(shí)，分別選取式（2）和式（5），則：

2.2 TF-IDF的計(jì)算

假設(shè)一個(gè)語(yǔ)料庫(kù)，它包含兩個(gè)文檔。兩個(gè)文檔的各個(gè)單詞以及其在各文檔中出現(xiàn)的次數(shù)，如表1所示。

計(jì)算詞語(yǔ)“apple”的TF-IDF的步驟如下：

詞語(yǔ)“apple”的tf為“apple”在各個(gè)文檔中出現(xiàn)的頻率。詞語(yǔ)“apple”都僅出現(xiàn)一次，但文檔1有5個(gè)單詞，而文檔2有7個(gè)單詞，所以“apple”在文檔2中的tf值較小。

一個(gè)語(yǔ)料庫(kù)中的某個(gè)單詞的idf值一樣的，它由有該單詞的文檔頻率決定。在本例中，兩個(gè)文檔均含有“apple”，所以：0。

因此“apple”在兩文檔的TF-IDF值均為0，即這個(gè)詞在所有文件中都沒(méi)有提供很多信息。

而相反“melon”詞語(yǔ)有著更多的信息。因?yàn)樗鼉H在文檔2中出現(xiàn)了3次。它的tfidf值計(jì)算如下：

因此詞語(yǔ)“melon”與文檔2的匹配程度更高。

3 程序設(shè)計(jì)框架

該程序框架可分為三個(gè)部分：爬蟲框架、flask框架以及TF-IDF計(jì)算。爬蟲框架負(fù)責(zé)對(duì)全網(wǎng)詞條獲取進(jìn)行初步搜索，如百度百科的所有詞條，形成粗糙集（語(yǔ)料庫(kù)），并保存以實(shí)現(xiàn)下一步精確的搜索；flask框架用于設(shè)置本地Web，作為顯示與人機(jī)交互界面；TF-IDF計(jì)算部分用于計(jì)算用于輸入的語(yǔ)句與語(yǔ)料庫(kù)的匹配程度（即該語(yǔ)句出現(xiàn)在某文檔的條件概率），并返回最相似的若干個(gè)詞條，通過(guò)flask在本地文本上顯示。

表1 文檔1與文檔2中所含單詞及其計(jì)數(shù)

3.1 爬蟲框架

本文爬取語(yǔ)料庫(kù)以爬取百度百科為例解釋爬蟲框架原理。本文使用的爬蟲框架使用requests庫(kù)爬取網(wǎng)頁(yè)html信息，使用bs4庫(kù)解析網(wǎng)頁(yè)并定位到需要的內(nèi)容［13］。同時(shí)使用隨機(jī)用戶代理（User Agent，UA）的方法避免被反爬蟲；使用正則表達(dá)式輔助定位信息等。在爬取時(shí)，需考慮到網(wǎng)頁(yè)出現(xiàn)的各種特殊情況，如出現(xiàn)多義詞時(shí)，需先定位該頁(yè)面各義項(xiàng)的二級(jí)網(wǎng)絡(luò)鏈接，定位到相應(yīng)的詞條進(jìn)行爬取，并自動(dòng)跳過(guò)不存在網(wǎng)頁(yè)。

網(wǎng)絡(luò)爬蟲的流程如圖1所示。

圖1 本文所使用的爬蟲框架流程

3.2 flask框架

本文提出的基于TF-IDF的搜索引擎框架的人機(jī)交互整體是通過(guò)flask構(gòu)建本地網(wǎng)站來(lái)實(shí)現(xiàn)的，flask框架構(gòu)建的系統(tǒng)通常由前端和后端兩個(gè)部分構(gòu)成［14］。前端為通過(guò)html語(yǔ)言設(shè)計(jì)的網(wǎng)站模板，用于設(shè)計(jì)網(wǎng)站的構(gòu)成（包括用戶輸入與結(jié)果輸出顯示）。當(dāng)用于輸入帶搜索的語(yǔ)句后，前端會(huì)發(fā)送獲取數(shù)據(jù)的請(qǐng)求給Flask app，而Flask app從后端獲取到數(shù)據(jù)，再通過(guò)route將數(shù)據(jù)返回給前端，通過(guò)模板設(shè)定好的參數(shù)，將處理后的數(shù)據(jù)顯示出來(lái)。

其中，F(xiàn)lask app接受到相應(yīng)的數(shù)據(jù)請(qǐng)求以后，分析數(shù)據(jù)請(qǐng)求信息，并確定請(qǐng)求來(lái)源之后，會(huì)調(diào)用程序中數(shù)據(jù)處理的函數(shù)完成相應(yīng)的計(jì)算（即TF-IDF值的計(jì)算）。其流程如圖2所示。

圖2 本文使用的flask框架流程

3.3 TF-IDF計(jì)算

首先數(shù)據(jù)處理函數(shù)從Flask app后端獲取到用戶輸入的語(yǔ)句，并將語(yǔ)句基于結(jié)巴（jieba）中文分詞［15］分成對(duì)應(yīng)的各個(gè)詞語(yǔ)；繼而根據(jù)式（2）、式（5）和式（10）計(jì)算各個(gè)詞語(yǔ)在語(yǔ)料庫(kù)D（事先由爬蟲框架爬取得到）中的tfidf值，然后將其相加得到該條用戶輸入的語(yǔ)句的tfidf值。在這里需引入停止詞的概念，即若分得的單詞為特定的一組單詞時(shí)，如“的”等對(duì)區(qū)分語(yǔ)料庫(kù)無(wú)作用的單詞等時(shí)，不計(jì)算其tfidf值。最后，該數(shù)據(jù)處理函數(shù)將計(jì)算出的語(yǔ)料庫(kù)中對(duì)應(yīng)tfidf值最大的若干個(gè)文檔返回給Flask app前端，作為用戶搜索的結(jié)果輸出。其流程如圖3所示。

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

為驗(yàn)證該系統(tǒng)的搜索效率與準(zhǔn)確度，在百度百科網(wǎng)站上進(jìn)行了實(shí)驗(yàn)和結(jié)果分析。實(shí)驗(yàn)平臺(tái)為筆記本電腦一臺(tái)，CPU使用i5-8400，主頻2.8GHz，最大睿頻4GHz，內(nèi)存使用8GDDR4，使用有線校園網(wǎng)，網(wǎng)速為10M/s。

圖3 本文使用的計(jì)算tfidf值函數(shù)流程

4.1 爬蟲爬取結(jié)果

百度百科的各個(gè)詞條鏈接為“https：//baike.bai?du.com/view/”后接不同的index序號(hào)即可，例如百度百科的詞條鏈接為“https：//baike.baidu.com/view/1”，界面如圖4所示，其中標(biāo)注區(qū)域?yàn)榕老x需爬取部分。

圖4 網(wǎng)站index=1及所需爬取內(nèi)容

不過(guò)如前文所述，有些詞條為多義詞，需搜索當(dāng)前頁(yè)面下的所有二級(jí)詞條的鏈接，進(jìn)行二次搜索，如“https：//baike.baidu.com/view/7”。同時(shí)有些index對(duì)應(yīng)網(wǎng)站為空網(wǎng)站，需識(shí)別并跳過(guò)，如“https：//baike.baidu.com/view/3”，兩種特殊情況如圖5所示。

因此考慮到所有情況，使用該爬蟲框架爬取能夠迅速準(zhǔn)確地爬取百度百科的各個(gè)詞條信息，爬取結(jié)果與保存文件格式如圖6所示。

如圖所示，該爬蟲程序能夠準(zhǔn)確地爬取各個(gè)詞條，并且能夠區(qū)分出有效網(wǎng)頁(yè)與多義詞的特殊情況，大大提高了爬取速度。保存文件的第一行為該詞條名稱，第二行至倒數(shù)第二行為詞條解釋，最后一行為百科詞條所在URL地址。

圖5 兩種特殊情況

圖6 爬取結(jié)果

在本文實(shí)驗(yàn)條件下，經(jīng)過(guò)多次實(shí)驗(yàn)該爬蟲爬取速度如表2所示，平均爬取速度約692條/分鐘。

4.2 基于TF-IDF的搜索引擎運(yùn)行

在應(yīng)用爬蟲爬取信息，構(gòu)成詞條語(yǔ)料庫(kù)后，可以由TF-IDF算法進(jìn)行第二階段的精確搜索，系統(tǒng)設(shè)計(jì)的搜索引擎界面如圖7所示。

表2 爬蟲的爬取速度

圖7 搜索引擎輸入界面

以搜索“百度”為例，其結(jié)果如圖8、圖9所示。

圖8 搜索引擎查詢結(jié)果界面

圖9 搜索結(jié)果詳細(xì)信息

根據(jù)TF-IDF算法的計(jì)算原理，計(jì)算函數(shù)從Flask app后端獲取用戶輸入的語(yǔ)句，按照?qǐng)D3的計(jì)算流程得到與之最匹配的若干文檔并予以顯示。圖7和圖8給出了使用html語(yǔ)言構(gòu)建的本地網(wǎng)站模板效果（搜索引擎界面）。

實(shí)驗(yàn)結(jié)果表明，該搜索引擎能夠做到在語(yǔ)料庫(kù)中準(zhǔn)確地搜索出與輸入語(yǔ)句最匹配的文檔。并且點(diǎn)擊每個(gè)搜素結(jié)果，可以進(jìn)一步調(diào)出詳細(xì)信息。

表3給出TF-IDF算法的搜索速度實(shí)驗(yàn)結(jié)果。搜索詞條的時(shí)間一般不超過(guò)1s，能夠滿足用戶迅速準(zhǔn)確地搜索到相關(guān)內(nèi)容的要求。

表3 搜索引擎的搜索速度

5 結(jié)語(yǔ)

本文設(shè)計(jì)了一種基于TF-IDF算法的分層搜索引擎。首先，利用網(wǎng)絡(luò)爬蟲爬取網(wǎng)絡(luò)詞條并構(gòu)造語(yǔ)料庫(kù)粗糙集，然后基于TF-IDF算法在語(yǔ)料庫(kù)中實(shí)現(xiàn)相關(guān)信息的精確檢索。該搜索引擎的GUI顯示界面運(yùn)用Flask框架構(gòu)建本地Web頁(yè)面，界面清晰易維護(hù)。該設(shè)計(jì)方案在利用網(wǎng)絡(luò)爬蟲爬取信息時(shí)，能夠安全快速地覆蓋網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)，構(gòu)造較為完備的語(yǔ)料庫(kù)粗燥集；TF-IDF算法則保證了二次深層搜索的精確度；整個(gè)搜索過(guò)程具有較高的效率，能夠滿足實(shí)時(shí)性的要求。