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

譚黔林, 莫春娟

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

?

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

譚黔林, 莫春娟

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

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

大數(shù)據(jù)；MapReduce；檢索；分布式系統(tǒng)

0　引言

大規(guī)模數(shù)據(jù)如果集中在一臺機器上進行檢索，其檢索速度將十分緩慢，如何解決這個問題至關(guān)重要。目前很多文件檢索的方式都是基于數(shù)據(jù)庫系統(tǒng)進行[1]，當數(shù)據(jù)量較大的時候，檢索的效率將會變得相當?shù)停虼耍Ａ繑?shù)據(jù)背景下，研究一種大規(guī)模數(shù)據(jù)集下的檢索方式至關(guān)重要。

1　基于MapReduce的系統(tǒng)設(shè)計

1.1MapReduce的概述

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

1.2MapReduce架構(gòu)應(yīng)用

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

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

圖1　MapReduce處理過程

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

利用MapReduce框架，可以實現(xiàn)分布式系統(tǒng)中各節(jié)點的并行處理，這樣可以提高分布式系統(tǒng)資源檢索的效率。

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

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

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

1.3文件資源系統(tǒng)

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

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

(1)處理超大文件；

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

(3)流式數(shù)據(jù)訪問。

2　基于MapReduce的海量文件檢索方法的實現(xiàn)

2.1文件檢索相似度的計算

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

特征提取過程即根據(jù)對應(yīng)特征的定義去計算該文本的特征值，比如，統(tǒng)計某個詞出現(xiàn)多少次，然后按照以下提及的特征值公式并以算術(shù)方法去計算。

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

如果要對文件庫中的某一個文件file[x]進行特征提取，則需要進行四類特征提取：文件名特征、文件內(nèi)容特征、檢索同義詞文件名特征、檢索同義詞內(nèi)容特征。假設(shè)文件名特征用FM表示，文件內(nèi)容特征用FC表示，檢索詞同義詞文件名特征用CFM表示，檢索詞同義詞內(nèi)容特征用CFC表示，最后根據(jù)查詢、分析原理對文件的四類特征進行提取[10]。

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

FM=Kall/FNall

(1)

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

Fc=Ktall/Fcall

(2)

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

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

(3)

(4)

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

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

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

(5)

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

2.2Map與Reduce算法

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

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

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

在MapReduce架構(gòu)中，Map算法主要執(zhí)行待檢文本的關(guān)鍵詞提取，計算文本數(shù)與待檢索關(guān)鍵詞的特征向量，得出向量指標后，根據(jù)每項特征的權(quán)重指標，用各項特征乘以對應(yīng)的權(quán)重再相加，再將該文件的綜合相似度指標提交給Reduce進行化簡操作。

2.3匹配

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

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

(2)作業(yè)分配階段：系統(tǒng)收到請求后，由JobTracker執(zhí)行。JobTracker執(zhí)行各項任務(wù)的分配，將檢索任務(wù)合理地分配到各個節(jié)點之上，為各節(jié)點之間的并行運行提供了基礎(chǔ)。

(3)Map階段：分配任務(wù)之后，會調(diào)度各項Map任務(wù)并行處理，Map任務(wù)的并行執(zhí)行，可以提高分布式系統(tǒng)檢索的效率。

(4)Reduce階段：完成Map任務(wù)之后，Reduce會收集Map階段產(chǎn)生的中間結(jié)果。

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

3　實驗分析

3.1Hadoop分布式系統(tǒng)搭建

表1　服務(wù)器配置信息表

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

在阿里云平臺上搭建Hadoop環(huán)境，機器數(shù)量為三臺，編號1為傳統(tǒng)方法，編號2為2個數(shù)據(jù)節(jié)點的MapReduce檢索方法，編號3為3個數(shù)據(jù)節(jié)點的MapReduce檢索方法，分別配置如表1所示。

3.2性能分析

圖2　傳統(tǒng)方式檢索效率與分布式方式檢索效率的性能對比

在測試該分布式系統(tǒng)的性能時，采用不同的數(shù)據(jù)集以及不同的節(jié)點數(shù)來進行測試，測試結(jié)果如圖2所示。

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

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

(3)隨著數(shù)據(jù)量的增大，在MapReduce架構(gòu)下的多結(jié)點檢索系統(tǒng)的優(yōu)勢越突出，并且檢索效率隨著節(jié)點數(shù)的增加而提高；

(4)對比分布式系統(tǒng)常規(guī)檢索方法(單節(jié)點)的檢索效果與經(jīng)過優(yōu)化的檢索方法的檢索效果，可以看得出，經(jīng)過優(yōu)化的檢索方法比常規(guī)檢索方法的檢索效果要優(yōu)越很多，并且效果隨著優(yōu)化的節(jié)點數(shù)的增加而增強。

4　結(jié)論及展望

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

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

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

[3]應(yīng)毅,劉亞軍.MapReduce并行計算技術(shù)發(fā)展綜述[J].計算機系統(tǒng)應(yīng)用,2014(4):1-6,11.

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

[5]宋杰,王智,李甜甜,于戈.一種優(yōu)化MapReduce系統(tǒng)能耗的數(shù)據(jù)布局算法[J].軟件學(xué)報,2015(8):2091-2110.

[6]韓海雯.MapReduce計算任務(wù)調(diào)度的資源配置優(yōu)化研究[D].廣州：華南理工大學(xué),2013.

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

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

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

[10]趙輝,楊樹強,陳志坤,尹洪,金松昌.基于MapReduce模型的范圍查詢分析優(yōu)化技術(shù)研究[J].計算機研究與發(fā)展,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-)，男，貴州鳳岡人，河池學(xué)院計算機與信息工程學(xué)院教師，主要研究方向：數(shù)據(jù)挖掘與信息分析研究。

廣西高校科學(xué)技術(shù)研究項目(LX2014320)；CALIS廣西壯族自治區(qū)文獻信息服務(wù)中心預(yù)研項目(LALISGX2014006)。

2016-01-07