基于MapReduce的海量文件檢索方法研究

譚黔林, 莫春娟

(河池學院　計算機與信息工程學院， 廣西　宜州　546300)

?

基于MapReduce的海量文件檢索方法研究

譚黔林, 莫春娟

(河池學院計算機與信息工程學院， 廣西宜州546300)

在文件檢索的方法中，目前主要是基于數據庫進行檢索。但是，當待檢索的數據量變得非常大的時候，再使用這種檢索方式，大量的檢索操作就會集中在一臺主機上進行，這會導致檢索效率降低。基于這種情況，擬采用分布式系統來解決這個問題。在分布式系統中進行資源檢索時，可以基于MapReduce架構來實現檢索，這樣，檢索操作的壓力將分散到分布式系統的各個節點中，這樣可以有效降低機器的壓力，大大提高檢索的效率。采用傳統方式檢索100萬條數據，需要耗時500 s，而采用基于MapReduce架構的分布式系統的方法來檢索100萬的數據，只需要花費40 s，相對于傳統檢索方法采用基于MapReduce架構的分布式系統檢索可使檢索效率提升接近12.5倍。

大數據；MapReduce；檢索；分布式系統

0　引言

大規模數據如果集中在一臺機器上進行檢索，其檢索速度將十分緩慢，如何解決這個問題至關重要。目前很多文件檢索的方式都是基于數據庫系統進行[1]，當數據量較大的時候，檢索的效率將會變得相當低，因此，海量數據背景下，研究一種大規模數據集下的檢索方式至關重要。

1　基于MapReduce的系統設計

1.1MapReduce的概述

MapReduce定義為一種編程模型，用于大規模數據集的并行運算[2]。在對分布式并行編程不熟悉的情況下，Mapreduce極大地方便了編程人員將程序在分布式系統上運行。

1.2MapReduce架構應用

J.Dean和S.Ghemawat在“MapReduce：Simplied Data Processing on Large Clusters”一文中講述了MapReduce框架的具體實現[3]。Hadoop主要為MapReduce提供了數據存儲以及計算的環境。

要提高分布式系統中文件檢索的效率，就要實現在分布式系統中，各個節點對數據流的并行處理，在MapReduce框架中可以用Map來實現在分布式系統中各個節點的并行處理。Map階段中，用戶向系統提交請求，jobtracker主線程接收這些請求，之后對數據集進行劃分，使每個分片都能并行運行。Map接到指令后將分片分解為鍵值對(key-value)，并會根據定義的Map函數對這些鍵值對進行處理，之后生成相對應的中間結果，并將這些中間結果進行分區和排序。

圖1　MapReduce處理過程

實現了分布式系統中各個節點的并行處理后， 還應當把分布式系統各個節點中處理的數據匯總到一起，匯總的過程可以用Reduce實現，將這些處理過的中間結果傳遞給Reduce進行再次處理[4-7]。在Reduce階段中，Reduce會接收到歸檔后的中間鍵值對，并根據這些接收到的數據進行相關計算，最后得到計算結果終鍵值對(ckey-cvalue),過程如圖1所示。

利用MapReduce框架，可以實現分布式系統中各節點的并行處理，這樣可以提高分布式系統資源檢索的效率。

上述過程用代碼表示如下：

Map階段：(key，value)-->list(mkey,mvalue)

Reduce階段：(mkey,list(mvalue))-->list(ckey,cvalue)

1.3文件資源系統

在分布式系統中最常用的是Hadoop分布式文件系統，即HDFS文件系統，Reduce部分的計算結果Cvalue最終存儲在HDFS中，如圖1所示。

HDFS文件系統的特點[8]主要有以下幾個方面：

(1)處理超大文件；

(2)運行于廉價機器上；

(3)流式數據訪問。

2　基于MapReduce的海量文件檢索方法的實現

2.1文件檢索相似度的計算

檢索時，首先需要進行檢索詞與索引數據庫詞相似度的計算。在計算相似度的過程中，需要根據待搜索的關鍵字與文件資源的文件名特征和內容特征的相近程度進行相應的計算，同時還要考慮待搜索關鍵字的同義詞、文件資源庫里文件名特征和文件內容特征。

特征提取過程即根據對應特征的定義去計算該文本的特征值，比如，統計某個詞出現多少次，然后按照以下提及的特征值公式并以算術方法去計算。

假設需要檢索的文件為file0,在整個文件庫中，有若干的文件，這些文件可以表示為file[n],n為文件庫中文件的總數量。

如果要對文件庫中的某一個文件file[x]進行特征提取，則需要進行四類特征提?。何募卣鳌⑽募热萏卣鳌z索同義詞文件名特征、檢索同義詞內容特征。假設文件名特征用FM表示，文件內容特征用FC表示，檢索詞同義詞文件名特征用CFM表示，檢索詞同義詞內容特征用CFC表示，最后根據查詢、分析原理對文件的四類特征進行提取[10]。

待檢索關鍵詞與文件名的相似程度，用該關鍵詞在文件名中出現的次數按比例進行計算，該特征可用關鍵字在文件名中出現的字數總和除以文件名字數總和進行計算。例如，需要檢索的關鍵詞是“心理”，檢索庫中存在文件名是“心理學心理書”的文件，那么待檢索的關鍵詞與該文件的相似程度為4/6，該相似程度即為文件名特征。假設關鍵詞在文件名中出現的字數總和是Kall，而文件名字數總和是FNall，那么有如下公式：

FM=Kall/FNall

(1)

根據2IDF算法中，關鍵詞的出現次數與文章字數權重關系，在文本特征提取過程中，通過關鍵詞在文本中出現的次數與文本字數之間的比例關系來確定。比如，假設 需要檢索的關鍵字是“心理”，檢索庫中某一文件內容為“一個人的心理，如果每一顆心都是有是好的，那么，心理學也不錯”，那么檢索關鍵詞與文件內容的相似程度就是2/26，即“心理”這個關鍵詞在內容中出現了兩次，而內容總字數為26字。假設關鍵詞在內容中出現的總次數用Ktall表示，文章內容的總字數用Fcall表示，那么有如下公式：

Fc=Ktall/Fcall

(2)

接下來 將討論待檢關鍵詞的同義詞的相關特征計算。文件檢索過程中，檢索與一個關鍵詞相關的文件，不僅要考慮該關鍵詞，還要考慮該關鍵詞的同義詞，比如 “心理”，那么其關聯詞可能是“心理學”、“心理健康”、“心理咨詢”等。所以，在計算同義詞特征時，需要依次計算關鍵詞的每個同義詞。

假設待選關鍵詞的同義詞個數一共有n個，同義詞i(1≤i≤n)字數是Call,同義詞i在文件內容中出現的次數是Ctall次，那么將有如下公式：

(3)

(4)

以上(1)～(4)式是計算文件庫中的每個文件與檢索詞相似的特征的計算方法。

計算出各文件的特征值之后，需要綜合計算出某個文件與待檢索關鍵詞的相關性，相關性的計算方式如下：

Sim=FM*w1+Fc*w2+CFM*w3+CFC*w4

(5)

其中，w1+w2+w3+w4=1,w1，w2，w3，w4分別為文件名特征、文件內容特征、檢索詞同義詞文件名特征、檢索詞同義詞內容特征的權重值。最終由公式(5)對每個文件求得一個值，該值是該文件與待檢索關鍵詞的相關性，由此，可以按數字從大到小對文件進行排序即得到按相關性從大到小進行排序的文件。

2.2Map與Reduce算法

在MapReduce核心是Map和Reduce算法，其算法描述過程如下。

Map算法，首先，讀取需要檢索的關鍵詞及讀取文件庫中某文件的數據；其次，獲取文件庫中現在讀取的文件的地址，如果滿足檢索條件，則比較關鍵詞與文件名的相似度、比較關鍵字與文件內容的相似度、比較關鍵詞同義詞與文件名的相似度、比較關鍵詞同義詞與文件內容的相似度，隨后，綜合四種特征計算總相似度；最后，提交相似度與文件地址。

Reduce算法，首先對各文件按相似度從大到小進行排序，然后提交經過排序后的文件相似度和文件地址。

在MapReduce架構中，Map算法主要執行待檢文本的關鍵詞提取，計算文本數與待檢索關鍵詞的特征向量，得出向量指標后，根據每項特征的權重指標，用各項特征乘以對應的權重再相加，再將該文件的綜合相似度指標提交給Reduce進行化簡操作。

2.3匹配

上面的論述中，分析了檢索的原理以及Map和Reduce實現的過程，但沒有具體涉及匹配的過程，本節將會具體闡述匹配的各項過程與任務，具體的實現過程如下。

(1)檢索請求的提交階段：匹配過程中，首先需要進行檢索請求的提交，即用戶提交檢索請求的過程，檢索請求提交標志著任務的開始，是進行匹配步驟的第一階段，完成后方可執行后續階段。

(2)作業分配階段：系統收到請求后，由JobTracker執行。JobTracker執行各項任務的分配，將檢索任務合理地分配到各個節點之上，為各節點之間的并行運行提供了基礎。

(3)Map階段：分配任務之后，會調度各項Map任務并行處理，Map任務的并行執行，可以提高分布式系統檢索的效率。

(4)Reduce階段：完成Map任務之后，Reduce會收集Map階段產生的中間結果。

(5)任務完成階段：Reduce計算之后，通過Internet返回給用戶，實現過程結束。

3　實驗分析

3.1Hadoop分布式系統搭建

表1　服務器配置信息表

Hadoop為MapReduce提供了分布式存儲和計算環境。我們將在Hadoop中進行MapReduce相關的試驗。

在阿里云平臺上搭建Hadoop環境，機器數量為三臺，編號1為傳統方法，編號2為2個數據節點的MapReduce檢索方法，編號3為3個數據節點的MapReduce檢索方法，分別配置如表1所示。

3.2性能分析

圖2　傳統方式檢索效率與分布式方式檢索效率的性能對比

在測試該分布式系統的性能時，采用不同的數據集以及不同的節點數來進行測試，測試結果如圖2所示。

(1)當數據在15和30萬條時，傳統方式所消耗的時間稍長，此時檢索所消耗時間差距并不大；

(2)隨著數據量的增大，Hadoop系統的性能優勢越明顯。當數據量超過30萬條時，用傳統方式進行檢索所耗時間急速上升，相比之下利用MapReduce架構進行檢索時，節點數越多檢索所消耗的時間就越少；

(3)隨著數據量的增大，在MapReduce架構下的多結點檢索系統的優勢越突出，并且檢索效率隨著節點數的增加而提高；

(4)對比分布式系統常規檢索方法(單節點)的檢索效果與經過優化的檢索方法的檢索效果，可以看得出，經過優化的檢索方法比常規檢索方法的檢索效果要優越很多，并且效果隨著優化的節點數的增加而增強。

4　結論及展望

使用MapReduce在分布式系統上進行文件檢索的相關操作，核心部分是待檢索關鍵詞與文件相關性的計算，本文算法在實現過程中根據文件名檢索、根據文件內容來檢索、根據本關鍵詞來檢索以及根據關鍵詞的同義詞來進行檢索，在一定程度上提高了文件檢索的準確率。本文實現了基于MapReduce在分布式系統中進行文件的高放檢索，檢索峰值測試優化檢索算法，以提高分布式系統的檢索效率，是下一步所要開展的研究。

[1]陳立博,李金友,畢建偉,黃灝.基于數據庫檢索信息的一種實現方法[J].黑龍江科技信息,2015，11(2):156.

[2]宋杰,劉雪冰,朱志良等.一種能效優化的MapReduce資源比模型[J].計算機學報,2015(1):59-73.

[3]應毅,劉亞軍.MapReduce并行計算技術發展綜述[J].計算機系統應用,2014(4):1-6,11.

[4]荀亞玲,張繼福,秦嘯.MapReduce集群環境下的數據放置策略[J].軟件學報,2015(8):2056-2073.

[5]宋杰,王智,李甜甜,于戈.一種優化MapReduce系統能耗的數據布局算法[J].軟件學報,2015(8):2091-2110.

[6]韓海雯.MapReduce計算任務調度的資源配置優化研究[D].廣州：華南理工大學,2013.

[7]江務學,張璟,王志明.MapReduce并行編程架構模型研究[J].微電子學與計算機,2011(6):168-170，175.

[8]黃斌,許舒人,蒲衛.基于MapReduce的數據挖掘平臺設計與實現[J].計算機工程與設計,2013(2):495-501.

[9]李偉衛,趙航,張陽,王勇.基于MapReduce的海量數據挖掘技術研究[J].計算機工程與應用,2013(20):112-117.

[10]趙輝,楊樹強,陳志坤,尹洪,金松昌.基于MapReduce模型的范圍查詢分析優化技術研究[J].計算機研究與發展,2014(3):606-617.

[Abstract]In the document retrieval method, the key is built on the database search. However, when the amount of data to be retrieved becomes very large, using this search method, a large number of retrieval operations will be concentrated on a single host, which can result in reduced efficiency of retrieval. Under this background, a distributed system can be used to solve the problem. Retrieving resources in a distributed system can be based on MapReduce architecture to achieve retrieval. Thus, the pressure of retrieval operation will be allocated to each node in a distributed system, which can effectively reduce the pressure of the machine and greatly improve the retrieval efficiency. Using the traditional way, retrieving 1 million data consumes 500 seconds, while using the method based on MapReduce architecture for distributed systems to retrieve one million data only needs 40 seconds. Compared with traditional search method, method of distributed systems based on MapReduce architecture can promote efficiency to 12.5 times.

[Key words]big data； MapReduce； searching； distributed system

[責任編輯劉景平]

Research on Massive File Retrieval Method Based on MapReduce

TAN Qian-lin, MO Chun-juan

(School of Computer and Information Engineering, Hechi University, Yizhou, Guangxi 546300, China)

TP311

A

1672-9021(2016)02-0101-05

譚黔林(1983-)，男，貴州鳳岡人，河池學院計算機與信息工程學院教師，主要研究方向：數據挖掘與信息分析研究。

廣西高?？茖W技術研究項目(LX2014320)；CALIS廣西壯族自治區文獻信息服務中心預研項目(LALISGX2014006)。

2016-01-07