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

（江蘇科技大學電子信息學院 鎮江 212003）

1 引言

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

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

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

2 TF-IDF算法

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

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

2.1 TF-IDF的定義

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

2.1.1 詞語頻率TF

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

1）布爾頻率。

2）根據文件長度調整的詞語頻率。

3）對數縮放頻率。

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

2.1.2 逆文檔頻率IDF

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

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

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

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

2）平滑的逆文檔頻率。

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

4）概率逆文檔頻率。

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

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

逆文檔頻率兩個統計量的乘積，即：

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

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

在得到GMC的估計量后，我們還需要確定帶寬。帶寬的選擇可以采用Sain等(1994)提出的方法，該方法可以通過R軟件的“ks”包實現，也可以采用交叉驗證法來選擇。由于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的計算

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

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

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

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

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

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

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

3 程序設計框架

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

表1 文檔1與文檔2中所含單詞及其計數

3.1 爬蟲框架

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

網絡爬蟲的流程如圖1所示。

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

3.2 flask框架

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

其中，Flask app接受到相應的數據請求以后，分析數據請求信息，并確定請求來源之后，會調用程序中數據處理的函數完成相應的計算（即TF-IDF值的計算）。其流程如圖2所示。

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

3.3 TF-IDF計算

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

4 實驗結果與分析

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

圖3 本文使用的計算tfidf值函數流程

4.1 爬蟲爬取結果

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

圖4 網站index=1及所需爬取內容

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

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

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

圖5 兩種特殊情況

圖6 爬取結果

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

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

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

表2 爬蟲的爬取速度

圖7 搜索引擎輸入界面

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

圖8 搜索引擎查詢結果界面

圖9 搜索結果詳細信息

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

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

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

表3 搜索引擎的搜索速度

5 結語

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