基于Map/Reduce框架實現的倒排索引文本檢索

馬 飛

（寧夏大學信息工程學院， 寧夏 銀川 750021）

提到索引，首先想到的是最常用的百度搜索和google搜索。目前，搜索引擎面對海量的數據，需要解決的是如何能在海量的數據下快速找到用戶所需要的文檔，滿足用戶需求。面對如此大型的數據集，數據庫一般很難做到有效地管理。而搜索引擎的數據操作簡單，通常僅需要增、刪、改、查功能，并且底層以特定的結構存儲數據，可以針對該結構設計出簡單高效的應用程序。搜索引擎需要面對的是多用戶檢索需求，這對搜索引擎的搜索速度提出挑戰，即需要快速響應用戶的請求。而通常使用的傳統數據庫很難承受大規模用戶的請求，而且在檢索響應時間和檢索并發度上都不及多處理器下設計的索引系統，文章研究了基于Map/Reduce框架實現的倒排索引文本檢索。

1 相關工作簡介

1.1 Map/Reduce工作原理

MapReduce[1]是由Google提出的云計算核心計算模型，Hadoop[2]計劃將它實現開源化。Hadoop[2]的Map/Reduce實現、Common及HDFS一起，構成了Hadoop初期的三個組件。在分布式計算模型中，對大規模數據集的分析和處理主要通過開源計算模型Map/Reduce完成。

Map/Reduce的工作原理如圖1所示。當向Map/Reduce框架提交相應的計算作業時，該框架首先進行計算作業的拆分，分成若干個Map任務后，將不同任務部署到多個計算節點上執行。通常每個Map任務對部分輸入數據進行處理，當相應的Map任務完成后，該過程會生成相應的中間文件，而Reduce任務主要以這些中間文件作為其輸入。Reduce函數設計的主要目標是對前面若干個Map的輸出進行匯總計算并將最終的結果進行輸出。

圖1 Map/Reduce的工作原理圖

從邏輯設計方面對分布式計算模型進行分析，Map/Reduce計算框架在運行過程中主要分為五個階段：輸入分片、map處理、combiner階段、shuffle階段和reduce合并。其中，Map/Reduce計算模型的核心函數Map和Reduce主要通過用戶自己設定完成。Map和Reduce函數的主要功能是進行鍵值對的相互轉換，通過前期分析設定相應的映射規則，將輸入的鍵值對＜key, value＞轉換成相應的＜key, value＞鍵值對輸出。Map函數對輸入數據進行處理后生成＜key, value＞類型的輸出列表。在Reduce函數處理過程中，將Map函數處理階段的輸出列表作為Reduce函數的輸入列表，隨后將key值相同的value生成一個聚集值，作為最后的輸出，最終需要將不同Map任務重所有相同key值的列表交換到同一個Reduce任務中。最終結果存儲在HDFS上。

1.2 索引系統定義

一般在搜索引擎[3]中，每個搜索對象都被抽象成一組特征項，即P={w1, w2, …wn}。從網頁里提取特征項的過程就是文章分析，通過定義函數Pextract來描述[4]這個過程：

其中，集合P={w1, w2, …wn}用于表示特征項詞典，網頁集合T(P)表示當前保存的整個網頁系統，通過定義集合表示系統的索引表：

其中，集合D={w1, w2, …wn}表示文檔系統的特征項詞典，r表示相關度函數，r(w, p)代表詞匯w和網頁p的相關度，如果網頁p的某個特征項用w表示，通過使用相關度算法會給出相應的正值。

1.3 倒排索引定義及結構

在實際應用中，查找的記錄如果需要根據屬性值來判斷，則可以使用倒排索引查找。通過該索引表的建立的數據結構中，每個數據項中都包括對應的屬性值和包含該屬性值的每條記錄的地址。因為該數據結構不是通過記錄來查找相應的屬性值，而是由對應的屬性值來確定需要查找記錄的位置，因此，將這種查找方式稱為倒排索引[4]（inverted index）。通過這種索引方式對文件結構進行組織后，通常稱該文件為倒排索引文件，簡稱倒排文件（inverted file）。

倒排索引的另一種稱謂為反向索引、置入檔案或反向檔案[5]。該方式在搜索引擎中很常見，通常在已知所有的數據項中，搜索某個關鍵字在一組文檔中的存儲位置的映射，這種數據結構常用于文檔檢索系統之中。通過倒排索引進行文件查找時，主要根據關鍵詞匹配技術獲取包含該關鍵詞的所有文檔列表。因此從邏輯結構方面理解倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”。

通常利用倒排索引對文本檢索時，將每個索引詞對應的文檔表按文檔編號增序排序，通過這種方式進行數據的壓縮保存。數據結構如圖2所示。

圖2 索引結構示意圖

左側為詞典中的某個索引詞t，右側為t的倒排表內容，它包含ft項，即為文檔集合中含有詞t的文檔的個數。每一項包括di文檔編號，文檔的權值wdt，以及該詞在文檔內出現的位置序列loc。

在倒排索引中，利用單詞詞典對文檔進行結構存儲，通過單詞詞典記錄每個單詞及所在文檔的相關信息，同時用包括該單詞對應的文件在倒排索引中的位置信息。在進行搜索時，通過用戶給定的關鍵詞，在單詞詞典中進行查詢，這樣可以快速獲得相應的倒排列表，并以此作為后續排序的基礎。對于規模的較大的文檔集合來說，包含幾十萬甚至上百萬的不同單詞，能否快速對查找單詞進行定位，這對搜索過程中響應速度有直接影響，所以需要對單詞詞典借助高效的數據結構進行構建和查找，倒排索引中常用的數據結構包括哈希加鏈表結構和樹形詞典結構。

2 倒排索引算法實現文本檢索

在Map/Reduce實現的倒排索引主要包含Map、Combine及Reduce三個過程[6]。在Map過程中，通過分布式文件系統hdfs存儲需要處理文檔，首先通過Hadoop中的核心類TextInputFormat對輸入的文件進行處理，通過處理后可以得到文件中每行對應的偏移量和內容，將偏移量及內容構成的鍵值對＜偏移量，內容＞作為map的輸入。map函數的關鍵是對key和value的進行設置以適應Map/Reduce框架，從而得到正確的結果。對于文件inverted1.txt與inverted2.txt，搜索關鍵詞的詳細設計過程如圖3所示。

設計過程中首先需要對整個文檔進行切分，得到單詞、所屬的文檔URL及詞頻，文中設計key=單詞＋URL，value=詞頻。即map的輸出為＜單詞＋URL，詞頻＞。

圖3 map過程輸入／輸出

通過map函數處理后的輸出的數據中，鍵值＜單詞＋URL，詞頻＞做為combine過程的輸入，該過程需要將同一文檔中Key值相同的value值進行累加，如圖4所示。

圖4 Combine過程輸入/輸出

在最后reduce處理階段，是對最終結果進行合并的階段，需要對不同文檔中相同的key值進行處理，該過程根據倒排索引需要的格式進行輸出，輸出結果為＜單詞，URL+詞頻＞，如圖5所示。

圖5 Reduce過程輸入/輸出

3 試驗結果與分析

試驗中，對比了利用Hadoop集群與集中式搜索兩種方式實現倒排索引文本檢索的耗時，同時也比較了利用不同數目主機搭建的Hadoop集群實現的倒排索引文本檢索速度，試驗中，設定主題為“找工作”，分別爬取15、50、100、300、500個網頁，以“工程師”為關鍵字檢索與該職位相關的招聘信息，數據采集如表1所示。

表1 不同方式實現的倒排索引文本檢索速度表

圖6對比了利用Hadoop集群實現的Map/Reduce倒排索引文本平均檢索速度與集中式文本檢索速度，試驗結果表明，當抓取網頁數量達到70個時，通過Hadoop集群與集中式實現的倒排索引耗時均接近75 000 ms。當爬取的網頁數量為15個時，利用集中式實現的倒排文本索引檢索耗時低于Hadoop集群的耗時，而平均檢索速度則優于分布式集群。而隨著抓取網頁的數量增長到500個時，利用集中式實現的文本檢索耗時呈比例增長，而通過Hadoop集群進行檢索速度明顯優于集中式實現的文本檢索，造成該現象的主要原因在于集群啟動時需要一定的時間，在對網頁數據進行分片、復制及不同主機間通信時會消耗大量時間。隨著集群所需要的準備工作完畢，利用集群實現的倒排索引文本檢索速度遠優于集中式文本檢索速度。

圖6 集中式與分布式文本平均檢索速度對比

圖7 試驗結果表明當抓取網頁數量少于70個時，集群主機數越少，主機間通信耗時越少，這是造成集群中利用不同數目主機檢索速度不相同的主要原因，當集群中主機間通信的完成時，隨著主機數的增加，利用Map/Reduce實現的倒排索引文本檢索速度更快，完成文本檢索的整個過程中耗時會更少。通過分布式集群實現的Map/Reduce倒排索引文本檢索算法在未來搜索引擎中擁有良好的應用空間，該方式會使人們更快的從網絡中獲取所需要的知識。

圖7 不同數目分布式集群實現文本檢索對比

4 結語

文本檢索在現實應用中是一個重要而迫切的問題，使用倒排索引的文本檢索技術可以解決這個問題。而面對現在海量的數據，使用單處理器進行文本檢索已無法滿足現實的需要。因此，通過Map/Reduce框架，將多個文本交給多個處理器進行檢索，不僅提升了文本檢索的速度和索引更新速度，同時也減輕了單處理器處理時內存和處理器的壓力。