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

譚黔林, 莫春娟

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

?

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

譚黔林, 莫春娟

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

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

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

0　引言

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

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

1.1MapReduce的概述

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

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

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

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

圖1　MapReduce處理過(guò)程

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

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

上述過(guò)程用代碼表示如下：

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部分的計(jì)算結(jié)果Cvalue最終存儲(chǔ)在HDFS中，如圖1所示。

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

(1)處理超大文件；

(2)運(yùn)行于廉價(jià)機(jī)器上；

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

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

2.1文件檢索相似度的計(jì)算

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

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

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

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

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

FM=Kall/FNall

(1)

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

Fc=Ktall/Fcall

(2)

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

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

(3)

(4)

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

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

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)對(duì)每個(gè)文件求得一個(gè)值，該值是該文件與待檢索關(guān)鍵詞的相關(guān)性，由此，可以按數(shù)字從大到小對(duì)文件進(jìn)行排序即得到按相關(guān)性從大到小進(jìn)行排序的文件。

2.2Map與Reduce算法

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

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

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

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

2.3匹配

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

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

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

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

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

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

3　實(shí)驗(yàn)分析

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

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

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

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

3.2性能分析

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

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

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

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

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

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

4　結(jié)論及展望

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

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

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

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

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

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

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

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

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

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

[10]趙輝,楊樹(shù)強(qiáng),陳志坤,尹洪,金松昌.基于MapReduce模型的范圍查詢分析優(yōu)化技術(shù)研究[J].計(jì)算機(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

[責(zé)任編輯劉景平]

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é)院計(jì)算機(jī)與信息工程學(xué)院教師，主要研究方向：數(shù)據(jù)挖掘與信息分析研究。

廣西高?？茖W(xué)技術(shù)研究項(xiàng)目(LX2014320)；CALIS廣西壯族自治區(qū)文獻(xiàn)信息服務(wù)中心預(yù)研項(xiàng)目(LALISGX2014006)。

2016-01-07