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

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

1 引言

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

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

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

2 TF-IDF算法

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

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

2.1 TF-IDF的定義

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

2.1.1 詞語頻率TF

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

1）布爾頻率。

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

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

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

2.1.2 逆文檔頻率IDF

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

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

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

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

2）平滑的逆文檔頻率。

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

4）概率逆文檔頻率。

2.1.3 詞語頻率-逆文檔頻率TF-IDF

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

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

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

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

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

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

2.2 TF-IDF的計算

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

計算詞語“apple”的TF-IDF的步驟如下：

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

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

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

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

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

3 程序設(shè)計框架

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

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

3.1 爬蟲框架

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

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

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

3.2 flask框架

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

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

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

3.3 TF-IDF計算

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

4 實驗結(jié)果與分析

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

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

4.1 爬蟲爬取結(jié)果

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

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

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

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

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

圖5 兩種特殊情況

圖6 爬取結(jié)果

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

4.2 基于TF-IDF的搜索引擎運行

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

表2 爬蟲的爬取速度

圖7 搜索引擎輸入界面

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

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

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

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

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

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

表3 搜索引擎的搜索速度

5 結(jié)語

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