吳雨晨，劉萍萍，徐江濤

(西安工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院，西安710021)

大數(shù)據(jù)云計算技術(shù)是一種分布式計算的拓展，其在執(zhí)行工作時可將龐大的計算程序進行分解，得到很多個更小的子程序，由集群來統(tǒng)一的完成計算工作，并將最終的計算結(jié)果反饋給用戶。當(dāng)前已經(jīng)出現(xiàn)的分布式搜索引擎技術(shù)已經(jīng)有很多種，例如Ajax技術(shù)、基于策略的分布式架構(gòu)技術(shù)、基于Web service技術(shù)的分布式搜索引擎以及基于P2P技術(shù)的分布式搜索引擎等。分析發(fā)現(xiàn)，此類搜索引擎主要都是介于Lucene全文檢索引擎工具包來實現(xiàn)的，但是這種方式建立索引的效率較低。Hadoop 分布式系統(tǒng)作為一個強大的分布式計算平臺，具有較高的兼容性，其能夠運行在不同的硬件平臺中。目前Hadoop分布式系統(tǒng)已經(jīng)逐步應(yīng)用到了不同類型的智能系統(tǒng)中，使其系統(tǒng)的性能更加優(yōu)越。

文獻[1-2]從全文檢索的原理出發(fā)提出基于.net的索引器的海量非結(jié)構(gòu)文本搜索，驗證了搜索引擎優(yōu)化的效果。文獻[3-4]針對檢索網(wǎng)絡(luò)的復(fù)雜變動與檢索關(guān)鍵字的語義出發(fā)，基于Lucene架構(gòu)的搜索得分排序算法提出了結(jié)合詞項位置、文檔瀏覽量、更新時間等因素的AHP二次檢索公式，改進的AHP二次檢索公式能更有效地提高信息檢索的準確度。文獻[5-6]針對搜索的實體信息分散且缺乏語義，傳統(tǒng)搜索引擎語義如上下文信息時長缺失的缺點，用信息網(wǎng)模型(INM)對Web數(shù)據(jù)進行語義表示和建模，將實體的所有語義信息組織在一個對象中，快速獲取實體完整的語義信息，基于INM構(gòu)建復(fù)雜語義數(shù)據(jù)庫優(yōu)化搜索引擎性能。文獻[7-8]針對特定領(lǐng)域中的專業(yè)規(guī)律，為了更好的滿足專業(yè)領(lǐng)域用戶的信息需求，構(gòu)建了主題搜索引擎。該引擎采用錨文本匹配進行領(lǐng)域關(guān)鍵字過濾、加入IKAnalyzer中文分詞器，排序搜索結(jié)果，并通過STC算法對結(jié)果實時聚類，其構(gòu)建的主題搜索引擎能更高效的在專業(yè)領(lǐng)域進行搜索。文獻[9-11]針對數(shù)據(jù)實體信息與轉(zhuǎn)化語義信息之間的關(guān)聯(lián)性誤差，提出本體模型分詞高斯邊緣化融合的特定語義數(shù)據(jù)檢索算法，從而克服中心頻率變化對關(guān)聯(lián)性能的影響，實現(xiàn)海量數(shù)據(jù)干擾下算法的改進，改進算法消除大量關(guān)聯(lián)性誤差，提高搜索引擎查準率。

現(xiàn)有搜索算法在復(fù)雜問題搜索上性能不足且誤差較大，本文擬采用Hadoop分布式計算平臺來建立分布式搜索引擎，利用Map-Reduce實現(xiàn)分布式索引模塊，最終通過優(yōu)化自適應(yīng)性切換搜索算法來提高搜索引擎性能。

1 Hadoop分布式平臺及框架

Hadoop分布式平臺是一種分布式的系統(tǒng)架構(gòu)，Hadoop最初分為三部分[12-13]，分別是Hadoop Common、HDFS(Hadoop Distributed File System)以及Map-Reduce，每部分能夠發(fā)揮不同的功能，此外還有很多相關(guān)的開源框架。Hadoop分布式平臺的組成結(jié)構(gòu)較為復(fù)雜，其中最底層為 HDFS，也就是一個分布式文件存儲系統(tǒng)。HDFS不僅能夠?qū)崿F(xiàn)文件管理系統(tǒng)的各添加以及刪除等操作，而且具有傳統(tǒng)存儲方式所不具有的優(yōu)勢?；贖adoop平臺來實現(xiàn)對數(shù)據(jù)的處理和存儲具有很大的優(yōu)勢，尤其是對于海量數(shù)據(jù)的存儲和管理，而且對于故障的恢復(fù)率比較高、可移植性較強。HDFS組織架構(gòu)如圖1所示。

本文設(shè)計的分布式搜索引擎為企業(yè)或個人提供個性化的搜索服務(wù)，為保證服務(wù)器端HDFS文件系統(tǒng)與客戶端文件系統(tǒng)的同步，需要對Windows本地文件系統(tǒng)進行監(jiān)控。因此客戶端必須具有多個功能，例如對文件的上傳、下載、新建、刪除以及修改等操作的實時監(jiān)控功能。服務(wù)器端主要實現(xiàn)的是存取文件以及同步事件等功能，例如需要對文件修改、刪除以及建立等事件進行同步處理。

分布式索引子系統(tǒng)主要是對預(yù)處理之后文檔的分詞處理等，能夠得到倒排索引并存儲到倒排索引庫內(nèi)，其系統(tǒng)總體架構(gòu)基于Map-Reduce框架實現(xiàn)。實現(xiàn)基于字符串的查詢功能，通過界面獲得使用者輸入的文本，對其進行解析得到關(guān)鍵詞等條件，并對倒排索引庫進行查詢即可得到最終的結(jié)果。具體的分布式查詢子系統(tǒng)整體架構(gòu)為：① 輸入查詢內(nèi)容。② 對查詢內(nèi)容進行中文分詞。③ 對分詞結(jié)果執(zhí)行查詢。④ 獲得查詢文檔的倒排索引。⑤ 將查詢文檔的倒排索引存儲到索引庫。⑥ 利用Map-Reduce計算框架按行分割查詢結(jié)果，key為文本偏移量，value為一行文檔的內(nèi)容。⑦ 將⑥結(jié)果再進行一輪Reduce過程，合并索引的查詢結(jié)果。

圖1 HDFS組織架構(gòu)Fig.1 HDFS organization

2 算法優(yōu)化

2.1 TF-IDF算法

通常文檔數(shù)據(jù)量非常巨大，用戶進行查詢時會得到很多不同的查詢結(jié)果[14]。為找到與用戶真正需求一致的查詢結(jié)果就需要借助于一定的評分策略，通過特定的網(wǎng)頁評分功能來滿足用戶對查詢結(jié)果精確性的要求?；诖髷?shù)據(jù)的數(shù)據(jù)檢索系統(tǒng)系統(tǒng)，不同文檔之間都是相互獨立的，而同一個文檔內(nèi)的標題和內(nèi)容具有較強的關(guān)聯(lián)性。為了使系統(tǒng)滿足用戶的個性化查詢需求，設(shè)計了一種基于用戶偏好的搜索方法，并且結(jié)合了TF-IDF(Term Frequency-Inverse Document Frequency)算法來改進現(xiàn)有的文檔評分策略，從而為用戶提供真正符合其需求的搜索服務(wù)。

TF-IDF作為一類統(tǒng)計方法，能夠有效地對文件集中某個文件的重要程度進行合理地統(tǒng)計。其原理可以理解為兩層含義：① 可以認為某個詞在文檔中出現(xiàn)的次數(shù)在很大程度上能夠表明這個詞與文檔的相關(guān)程度，這個詞出現(xiàn)的次數(shù)越多說明相關(guān)性越大；② 某個詞用來驗證文檔相關(guān)性的作用與含有此詞的文檔數(shù)是一種反比關(guān)系。TF-IDF算法的計算公式為

(1)

(2)

tfidfi,j=tfi,j×idfi

(3)

式中：ni,j為文件dj中詞的數(shù)量，∑knk,j為文件dj中的所有詞之和。|D|為語料庫的文件數(shù)目，|{j:ti∈dj}|為含有詞語ti的文件數(shù)，而tfidfi,j為詞ti和文檔的相關(guān)性大小。在一份給定的文件里，詞頻(Term Frequency，TF)為某一個給定的詞語在該文件中出現(xiàn)的頻率，它是對詞數(shù)(Term Count)的歸一化，以防止它偏向長的文件。對于在某一特定文件里的詞語ti來說，它的重要性可表示為逆向文件頻率(Inverse Document Frequency，IDF)，是一個詞語普遍重要性的度量。某一特定詞語的IDF，可以由總文件數(shù)目除以包含該詞語之文件的數(shù)目，再將得到的商取對數(shù)得到。某一特定文件內(nèi)的高詞語頻率，以及該詞語在整個文件集合中的低文件頻率，可以產(chǎn)生出高權(quán)重的TF-IDF。因此，TF-IDF傾向于過濾掉常見的詞語，保留重要的詞語。本文對原始的TF-IDF算法進行了改進，在計算Rank評分時將文檔中詞的位置納入影響因素，對于文檔中標題和正文出現(xiàn)的關(guān)鍵詞分別設(shè)置不一樣的權(quán)重值。例如在詞頻值計算方面，標題中含有此關(guān)鍵詞時就將詞頻值大小增加6；正文內(nèi)出現(xiàn)關(guān)鍵詞時就將詞頻值大小增加1。

2.2 算法優(yōu)化

本文設(shè)計的自適應(yīng)性切換搜索算法，需要基于索引的大小來針對性的處理索引過程。如果索引很小，可以將其直接存入內(nèi)存；如果索引文件很大，可以建立二級索引，讀到內(nèi)存中的索引列表，可以進行分布式的查詢。通過這種方式可以有效地提高對索引文件的搜索效率。

自適應(yīng)性切割搜索算法的基本原理是基于索引文件大小選擇合適的搜索算法[15-16]，以256 MB大小的索引文件為界限，如果索引文件大小不超過256 MB，此時用戶查詢時將索引文件讀進內(nèi)存，對其直接進行查詢。如果索引文件大小超過256 MB，需要構(gòu)建二級索引，查詢時先將二級索引讀進內(nèi)存中，用戶先對此二級索引進行查詢，并以此來查詢到原始的索引文件。最終獲取的索引文件即為Map-Reduce查詢?nèi)蝿?wù)的輸入，可以得到最終的查詢結(jié)果。在執(zhí)行Map-Reduce任務(wù)時，將輸入文件分割為多個split，同時為每個split建立Mapper。通常情況下split是64 MB，如果輸入文件很少，只需少數(shù)Mapper就能完成處理任務(wù)，此時不能充分發(fā)揮分布式計算的高性能優(yōu)勢。同時可能會因為過多的文件分割以及分發(fā)過程使得計算效率降低。默認情況下，Map-Reduce任務(wù)處理小于256 MB的文件是采用直接將其讀入內(nèi)存的方式，而超過256 MB采用的是并發(fā)執(zhí)行4個Mapper的方式。相關(guān)統(tǒng)計數(shù)據(jù)表明，當(dāng)前在漢字中使用最普遍的詞大約有56 000左右。如果索引文件中囊括了全部的詞，此時也可以加載二級索引文件到內(nèi)存中。另外關(guān)鍵詞通常只有少數(shù)幾個，此時通過建立二級索引的方式，就可以有效地降低查詢時的索引文件數(shù)。

算法的具體執(zhí)行過程如下：

1) 對索引文件的大小進行統(tǒng)計，當(dāng)索引文件超過256MB時就建立二級索引，并將其存儲到HDFS。二級索引建立過程如下：

① 啟動查詢器。

② 統(tǒng)計索引文件大小。

③ 判斷索引文件是否大于256M，若索引文件小于或等于256M直接寫入內(nèi)存；索引文件大于256M，流程繼續(xù)執(zhí)行。

④ 判斷是否已經(jīng)存在對應(yīng)二級索引文件，若存在，則將二級索引直接利用哈希表寫入內(nèi)存；若不存在則流程繼續(xù)執(zhí)行。

⑤ 對當(dāng)前索引文件構(gòu)建倒排索引。

⑥ 加入倒排索引數(shù)據(jù)庫。

⑦ 構(gòu)建二級索引。

⑧ 加入二級索引庫，并寫入內(nèi)存。

2) 對是否存在二級索引進行判斷，同時使用flag變量進行表示。如果不存在二級索引，就直接把索引文件存入特定的數(shù)據(jù)結(jié)構(gòu)中。具體的數(shù)據(jù)結(jié)構(gòu)如圖2所示，其主體是多個哈希表，在每一個哈希表中都有一個指向沖突鏈表的指針，而哈希值一樣的關(guān)鍵詞就組成了鏈表結(jié)構(gòu)。鏈表節(jié)點也就是結(jié)構(gòu)體，其含有關(guān)鍵詞及其文檔索引信息等。

圖2 哈希鏈表結(jié)構(gòu)示意

3) 如果索引文件很大，此時也需要先將二級索引加載到一個數(shù)據(jù)結(jié)構(gòu)中，但是此數(shù)據(jù)結(jié)構(gòu)與之前的哈希鏈表結(jié)構(gòu)有所不同，其鏈表結(jié)構(gòu)體主要包括了關(guān)鍵詞及其索引文檔URL。

4) 自適應(yīng)搜索算法首先是系統(tǒng)獲取用戶輸入的查詢內(nèi)容，作中文分詞處理。

5) 此時需要對索引文件大小進行確定，如果其低于256 MB，可以直接按照關(guān)鍵詞的哈希值來查詢內(nèi)存中的索引文件并得到結(jié)果。

6) 當(dāng)索引文件的大小超過了256 MB時，需要基于關(guān)鍵詞的哈希值來查詢二級索引文件。此時將得到的索引文件作為Map-Reduce輸入，來得到最終的查詢結(jié)果。

同時需要基于Map-Reduce框架來建立二級索引，其步驟如下：

① 執(zhí)行Map-Reduce任務(wù)的輸入即為之前的倒排索引文件，使用TextInputFormat完成對輸入文件的分割。

② 將輸入文件中沒行內(nèi)容作為Map()函數(shù)的輸入，此時的新key值也就是其中含有的關(guān)鍵詞；相應(yīng)的新value值即為關(guān)鍵詞所在文件的URL。

③ 通過Reduce()來合并Map()函數(shù)的輸出，并將最終的結(jié)果存儲到HDFS文件系統(tǒng)的二級索引庫內(nèi)。

2.3 算法測試

在測試自適應(yīng)搜索算法的計算性能時，采用了按照大、小索引兩種類型計算的方式，并與之前算法的計算性能作對比。測試結(jié)果見表1和表2。

表1 小索引文件新舊算法性能測試結(jié)果

表2 大索引文件新舊算法性能測試結(jié)果

進行查詢測試時，選取了五組低于256 MB的索引文件來進行測試。針對每一組索引文件作10次查詢，統(tǒng)計每次的查詢時間并計算出時間的平均值。測試結(jié)果如圖3所示，從圖3中可以發(fā)現(xiàn)，小索引情況時使用新搜索算法花費的時間明顯低于原始搜索算法，這說明這種新算法在性能方面具有較大的優(yōu)勢。

圖3 小索引的算法測試結(jié)果比較

測試超過256 MB的索引文件的查詢性能，這里選擇了三組索引文件進行測試。針對每一組索引文件作10次查詢，統(tǒng)計查詢時間并計算出時間的平均值。得到的測試結(jié)果如圖4所示，可以發(fā)現(xiàn)使用新搜索算法進行查詢花費的時間顯著小于原始的搜索算法。

通過測試發(fā)現(xiàn)，使用文中算法的查詢效率顯著提高，原因是由于本文的查詢測試是基于5節(jié)點集群，共有4個索引文件，關(guān)鍵詞數(shù)也是4個左右，因此關(guān)鍵詞可能出現(xiàn)在2個或者是3個索引文件內(nèi)。而通過二級索引檢索能夠降低索引文件數(shù)，使其變?yōu)?個或者3個。同理，如果集群的節(jié)點更多，可以將索引文件進行更精細的劃分，新算法的計算效率也會更高。

圖4 大索引的算法測試結(jié)果

3 系統(tǒng)構(gòu)建

大數(shù)據(jù)數(shù)據(jù)檢索自適應(yīng)系統(tǒng)包括客戶端與服務(wù)器端。在系統(tǒng)正常運行的時候，監(jiān)控模塊會實現(xiàn)對文件的實時監(jiān)控功能。對于客戶端來說，操作本地文件時，系統(tǒng)會對用戶的操作事件進行實時的監(jiān)控處理，同時對監(jiān)控結(jié)果進行劃分。下一步為文件同步過程的執(zhí)行，此時需要文件同步模塊提供相應(yīng)的同步服務(wù)。此模塊能夠基于不同的事件來做出特定的響應(yīng)，具體的響應(yīng)包括對服務(wù)器端HDFS中文件的增刪改查。

3.1 客戶端功能模塊

在客戶端中，對HDFS文件系統(tǒng)進行操作主要包括文件新建、文件下載、文件刪除以及文件打開等，其功能分別為：文件新建實現(xiàn)新HDFS文件的創(chuàng)建； 下載實現(xiàn)將服務(wù)器端的HDFS文件下載到本地文件夾中；刪除實現(xiàn)對HDFS文件的刪除；重命名實現(xiàn)對HDFS文件系統(tǒng)中文件的重新命名；打開將HDFS文件系統(tǒng)中相應(yīng)的文件打開并查看其具體內(nèi)容；刷新實現(xiàn)對HDFS的文件列表刷新顯示。H按鈕操作事件監(jiān)控及分類處理如圖5所示。

3.2 服務(wù)器端功能模塊

系統(tǒng)的后臺存儲系統(tǒng)使用了HDFS文件系統(tǒng)，可以有效地實現(xiàn)分布式存儲功能。結(jié)構(gòu)分為3個節(jié)點，其中一個為Namenode主節(jié)點，主要實現(xiàn)對元數(shù)據(jù)信息的存儲功能；其余兩個為Datanode從節(jié)點，主要實現(xiàn)對文件數(shù)據(jù)塊的存儲功能。Datanode的文件分塊大小為64MB，復(fù)制因子為2，表示文件分塊備份了2個。系統(tǒng)服務(wù)器端的架構(gòu)如圖6所示。

圖5 H按鈕操作事件監(jiān)控及分類處理

圖6 系統(tǒng)服務(wù)端的整體架構(gòu)圖

4 性能測試與分析

為充分利用現(xiàn)有的硬件資源進行測試，直接使用一臺IBM服務(wù)器來模擬五個配置完全一致的節(jié)點。具體硬件配置如下：CPU是單處理器單核；內(nèi)存大小是1 G，硬盤大小是20 G。選擇使用Linux下的ubuntu-12.04操作系統(tǒng) ；使用jdk1.7與Eclipse 3.5來進行Java程序開發(fā)；Hadoop平臺選擇的是hadoop-0.20.2版本；虛擬機選擇的是VMware-workstation full-v10.0.0版本。本系統(tǒng)在配置Hadoop集群時，選擇其中一個作為Master，其他的都作為 Slave節(jié)點，并將網(wǎng)絡(luò)設(shè)置成橋接模式。節(jié)點的具體信息見表3。

表3 集群的節(jié)點設(shè)置

常規(guī)的搜索引擎主要在建立索引時需要花費較多的時間，查詢過程較為迅速，而查詢時間過短會導(dǎo)致受到帶寬等因素的干擾，因此對本系統(tǒng)測試時主要是對索引建立進行了測試。為了確定Hadoop集群的性能與節(jié)點數(shù)量之間的關(guān)系，本文將集群的節(jié)點數(shù)分別設(shè)置為2,3,4和5進行測試；對系統(tǒng)運行時間進行比較，分別選擇了100,1 000,10 000,100 000以及1 000 000個網(wǎng)頁文檔來建立倒排索引。性能測試結(jié)果如圖7所示。

圖7 性能測試結(jié)果

從圖7可以發(fā)現(xiàn)，如果網(wǎng)頁文檔的數(shù)量很少，建立索引時間與節(jié)點數(shù)量。其主要原因為：如果網(wǎng)頁文檔的數(shù)量較少，也只有很少部分節(jié)點來執(zhí)行建立索引任務(wù)，其分布式計算性能沒有發(fā)揮，索引時間也不會隨著文檔的增多而變化，因為在任務(wù)分隔等過程中花費了較多的時間。而如果網(wǎng)頁文檔足夠多時，此時建立索引需要的時間與節(jié)點數(shù)呈現(xiàn)出負增長關(guān)系，即節(jié)點數(shù)量越大，索引時間就越短，這就證明系統(tǒng)性能隨著節(jié)點的增多而提升。因此可以采用增加節(jié)點數(shù)量的方式來提升整個系統(tǒng)的性能。這表明，本系統(tǒng)具有較高的可靠性，即使有多個節(jié)點發(fā)生了故障，系統(tǒng)仍然能夠完成相應(yīng)任務(wù)。

5 結(jié) 論

本文設(shè)計并實現(xiàn)了一種自適應(yīng)性切換搜索算法，通過對索引文件大小的有效分析和處理，利用了Map-Reduce框架完成了對索引以及查詢兩個子系統(tǒng)的設(shè)計和實現(xiàn)，優(yōu)化了分布式搜索引擎的搜索效率。

1) 基于用戶的個性化搜索需求來選擇合適的搜索方式，提高了搜索結(jié)果的精確性。用戶在使用Map/Reduce框架進行文件處理時，只需要重新對Map以及Reduce函數(shù)進行編寫即可實現(xiàn)分布式處理功能，而完全不需要考慮其處理過程中涉及到的通信問題、存儲問題以及負載均衡問題等。

2) 選擇100,1 000,10 000,100 000以及1 000 000個網(wǎng)頁文檔來建立倒排索引，建立索引需要的時間與節(jié)點數(shù)呈現(xiàn)出負增長關(guān)系，即節(jié)點數(shù)目越大，索引時間就越短，證明系統(tǒng)性能隨著節(jié)點的增多而提升。

3) 通過對五組低于256 MB的索引文件和三組超過256 MB的索引文件進行測試，并針對每一組索引文件作10次查詢。當(dāng)索引文件大小在1 000 MB左右時，算法效果達到最優(yōu)，搜索時間相較原算法大幅縮短。