文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.190008
中文引用格式： 龔永罡,，田潤琳,，廉小親，等. 基于MapReduce的三元N-gram算法的并行化研究[J].電子技術(shù)應(yīng)用,，2019,，45(5)：70-73，77.
英文引用格式： Gong Yonggang,，Tian Runlin,，Lian Xiaoqin，et al. Research on parallelization of trigram N-gram algorithm based on MapReduce[J]. Application of Electronic Technique,，2019,，45(5)：70-73，77.
0 引言
隨著“互聯(lián)網(wǎng)+”時(shí)代的到來和快速發(fā)展,，新媒體（微博,、微信公眾號(hào)、博客,、論壇,、新聞客戶端等）已成為人們生活中不可分割的一部分,很多新聞媒體平臺(tái)，每天原創(chuàng)新聞發(fā)布量巨大,，而新聞的時(shí)效性使其會(huì)在短時(shí)間內(nèi)被各大媒體廣泛轉(zhuǎn)載轉(zhuǎn)發(fā),，人工審核是不切實(shí)際的。因此,，必須在稿件發(fā)出前采用基于語義分析的自動(dòng)識(shí)別技術(shù)手段才能確?！凹皶r(shí)、準(zhǔn)確”發(fā)現(xiàn)問題,、定位問題,、解決問題[1-2]。利用概率統(tǒng)計(jì)方法來識(shí)別真詞錯(cuò)誤的是采用詞和詞性的三元N-gram語言模型的方法可以以較小的存儲(chǔ)空間得到較高約束的N-gram平滑概率,，大大降低了統(tǒng)計(jì)模型的復(fù)雜度,，后繼訓(xùn)練工作量適宜，對(duì)應(yīng)用域語言的適應(yīng)能力較強(qiáng),，三元N-gram語言模型在中文文本自動(dòng)查錯(cuò)應(yīng)用效果很好,，但需要大規(guī)模的中文語料庫進(jìn)行訓(xùn)練[3-4]。以單機(jī)運(yùn)行為主的數(shù)據(jù)處理方式制約了計(jì)算效率的提高,，訓(xùn)練時(shí)間過長,、占用內(nèi)存過大等問題難以解決[5]。面對(duì)海量數(shù)據(jù)的處理,，MapReduce模型將大規(guī)模數(shù)據(jù)處理作業(yè)拆分成若干個(gè)可獨(dú)立運(yùn)行的任務(wù),，使用廣泛，能夠降低并行編程難度,，極大地縮短了處理時(shí)間,，已成為當(dāng)前大規(guī)模數(shù)據(jù)處理的主流技術(shù)[6-7]。
本文在開源式分布處理平臺(tái)Hadoop基礎(chǔ)上,，設(shè)計(jì)并實(shí)現(xiàn)了利用MapReduce框架并行的三元N-gram算法,，解決了單機(jī)運(yùn)行三元N-gram算法時(shí)間過長、內(nèi)存不足等問題,，并通過實(shí)驗(yàn)驗(yàn)證該算法具有較好的處理速度和準(zhǔn)確率,。
1 模型的建立
1.1 三元N-gram模型的構(gòu)造
在文本數(shù)據(jù)處理中，首先以序列的方式對(duì)詞料進(jìn)行切分, 在這之后對(duì)其序列展開分組處理,。假定預(yù)測窗口的實(shí)際大小等于w,，當(dāng)存在全新的元數(shù)據(jù)請(qǐng)求時(shí)，通過它對(duì)時(shí)間較長的元數(shù)據(jù)請(qǐng)求進(jìn)行替換,，如此就產(chǎn)生全新的組G[8-9],。因?yàn)樵谶@個(gè)過程中應(yīng)用了3-gram模型,，因此針對(duì)所有組G來說,對(duì)前面2個(gè)文件元數(shù)據(jù)請(qǐng)求進(jìn)行固定處理,而對(duì)于有序的序列,之后的w-2充當(dāng)無序序列。在分組結(jié)束之后,，對(duì)得到的組展開標(biāo)準(zhǔn)化的冗余處理,，并消除無序序列內(nèi)完全一致的元數(shù)據(jù)請(qǐng)求。除此之外,，應(yīng)將通過處理的組按照先后秩序進(jìn)行數(shù)據(jù)連接[10],。進(jìn)而從所有數(shù)據(jù)內(nèi)尋求概率最高的，并將其組建為規(guī)則,所有規(guī)則對(duì)預(yù)取的組進(jìn)行標(biāo)準(zhǔn)化的合并,。下文將給出其具體的算法描述,。鄰接三元的概率估計(jì)的公式為：
式中，P代表搭配出現(xiàn)的概率,；Wi代表隨機(jī)某一中文字符,，Wi-1、Wi+1分別代表隨機(jī)某一中文字符的前,、后中文字符,，Count(...)代表一個(gè)特定詞序列在整個(gè)語料庫中出現(xiàn)的累計(jì)次數(shù)。
如圖1所示,，識(shí)別步驟如下：
(1)預(yù)處理：對(duì)錄入的一篇文章,，通常情況下為TXT文件，先對(duì)詞進(jìn)行切分,。作為語料庫,，一定要確保其不存在任何誤差。
(2)初次掃描：提取所有的特征序列,，通過N-gram計(jì)算模型統(tǒng)計(jì)字詞出現(xiàn)次數(shù)N,，并把這個(gè)字詞以及統(tǒng)計(jì)的次數(shù)結(jié)果添加至mongo數(shù)據(jù)庫。
(3)第二次掃描：假如P不小于特定的閾值,，那么識(shí)別結(jié)果不存在誤差,，判定為正確詞生成語料庫；假如運(yùn)算得到的詞句可信度P小于閾值,，那么可具體執(zhí)行擴(kuò)散操作,。
(4)第三次掃描：對(duì)檢錯(cuò)規(guī)則進(jìn)行具體執(zhí)行，排除沒有幾率出現(xiàn)的字詞,，從而優(yōu)化整體的準(zhǔn)確率,。
1.2 MapReduce模型
MapReduce是一類操作性強(qiáng),、容錯(cuò)性優(yōu)良的并行編程模型,，基于MapReduce設(shè)計(jì)的程序具有很好的穩(wěn)定性和可擴(kuò)展性。其框架一般應(yīng)用“分而治之”的方式,，將對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行的各項(xiàng)操作進(jìn)行分布處理,，從而讓多個(gè)分節(jié)點(diǎn)一起完成,，之后對(duì)所有分節(jié)點(diǎn)的中間結(jié)果進(jìn)行整合處理，進(jìn)而獲得所需的結(jié)果[11-12],。其處理的整個(gè)過程依托于兩類函數(shù),，分別是Map函數(shù)和Reduce函數(shù)，其中前者將任務(wù)進(jìn)行分解處理,，后者將任務(wù)處理的結(jié)果進(jìn)行規(guī)范化的匯總處理,。而針對(duì)并行編程內(nèi)的其他問題，其中比較具有代表性的包括分布式存儲(chǔ),、容錯(cuò)處理等,，它們都是通過MapReduce框架進(jìn)行標(biāo)準(zhǔn)化的處理。
MapReduce分布處理數(shù)據(jù)的過程如圖2所示,。在數(shù)據(jù)輸入環(huán)節(jié),，MapReduce可以進(jìn)行數(shù)據(jù)量的等分處理，從而得到規(guī)模相差無幾的數(shù)據(jù)塊,。Map任務(wù)(一般將其命名為Mapper)能夠?qū)τ脩艚缍ǖ腗ap函數(shù)進(jìn)行具體執(zhí)行[13],。在Map環(huán)節(jié)中，所有Map任務(wù)都能夠?qū)μ囟ǖ膕plit進(jìn)行處理,，得到特定的＜key,，values＞鍵值對(duì)，在通過Map函數(shù)處理以后,，構(gòu)成了一部分中間數(shù)據(jù),，這些數(shù)據(jù)在指定的位置進(jìn)行儲(chǔ)存，在其提升至某個(gè)水平之后,，將其轉(zhuǎn)移至本地磁盤,。在Reduce階段，接收Map函數(shù)的數(shù)據(jù)結(jié)果,，對(duì)輸入的＜key,，value＞對(duì)展開標(biāo)準(zhǔn)化的處理。輸出環(huán)節(jié)：把處理得到的結(jié)果進(jìn)行寫入,，在任務(wù)執(zhí)行的過程中,，Hadoop框架會(huì)對(duì)任務(wù)調(diào)度進(jìn)行有效的管理，并對(duì)任務(wù)的執(zhí)行情況進(jìn)行嚴(yán)密的監(jiān)視,，對(duì)一些運(yùn)行未成功的任務(wù)進(jìn)行重啟[14-15],。
2 基于MapReduce的三元N-gram算法模型實(shí)現(xiàn)
2.1 MapReduce的三元N-gram算法并行化思想
通過分析單機(jī)運(yùn)行的三元N-gram算法，針對(duì)其有序的計(jì)算模式進(jìn)行并行化改進(jìn),，提出了MapReduce框架下的三元N-gram算法,。對(duì)比MapReduce框架下的三元N-gram算法和常規(guī)單機(jī)運(yùn)行的三元N-gram算法的時(shí)間長度和內(nèi)存空間占據(jù)量，證明把三元N-gram算法移植到MapReduce框架下實(shí)現(xiàn)了對(duì)海量中文文本數(shù)據(jù)集的并行處理,。
運(yùn)用三元N-gram算法對(duì)大量的中文文本數(shù)據(jù)集展開處理時(shí),，其運(yùn)算量達(dá)到較高的水平,，進(jìn)而導(dǎo)致消耗的時(shí)間延長，這是該算法的不足之處,。盡管對(duì)這種算法展開了多次優(yōu)化,，然而伴隨數(shù)據(jù)規(guī)模的不斷擴(kuò)增，三元N-gram算法由于計(jì)算需求超過一定限度而降低了效率,。因此,，該算法可應(yīng)用“分而治之”的理念:Hadoop的HDFS文件系統(tǒng)將文本數(shù)據(jù)分成n份規(guī)模相當(dāng)?shù)臄?shù)據(jù)塊進(jìn)行存儲(chǔ)，然后把數(shù)據(jù)塊發(fā)送到m個(gè)節(jié)點(diǎn),，運(yùn)行Map函數(shù),，掃描每個(gè)數(shù)據(jù)塊，通過統(tǒng)計(jì)每個(gè)字詞分別與前兩個(gè)字詞搭配出現(xiàn)的次數(shù)產(chǎn)生字詞搭配統(tǒng)計(jì)數(shù)值,，每個(gè)數(shù)據(jù)集的局部數(shù)據(jù)統(tǒng)計(jì)算法與經(jīng)典的三元N-gram算法相同,；編寫Combine將Map階段結(jié)果進(jìn)行合并，之后依據(jù)相同字詞就統(tǒng)計(jì)結(jié)果進(jìn)行重新分組,，生成新的數(shù)據(jù)集,；利用Reduce函數(shù)得出全局相鄰詞間統(tǒng)計(jì)概率結(jié)果，對(duì)概率統(tǒng)計(jì)結(jié)果進(jìn)行閾值分割,，根據(jù)統(tǒng)計(jì)結(jié)果與閾值的比較得出判定字詞搭配出現(xiàn)的正誤,，依次迭代，對(duì)其文本進(jìn)行詞組校對(duì),。
基于MapReduce的三元N-gram算法極大縮短了大規(guī)模數(shù)據(jù)量的計(jì)算運(yùn)行時(shí)間以及對(duì)內(nèi)存空間的依賴,，執(zhí)行效率相對(duì)于傳統(tǒng)的三元N-gram算法提升顯著。
2.2 MapReduce的三元N-gram算法并行化策略
MapReduce的三元N-gram算法的并行化計(jì)算是先將大規(guī)模中文文本數(shù)據(jù)集分成N份一定規(guī)模大小的數(shù)據(jù)塊(默認(rèn)以64 MB大小數(shù)據(jù)量進(jìn)行就等分割存儲(chǔ)),，以便并行處理,，之后運(yùn)行Map和Reduce函數(shù)計(jì)算，得出統(tǒng)計(jì)結(jié)果,。
其算法流程如圖3所示,。MapReduce程序中包含多個(gè)Map和Reduce任務(wù)，且每個(gè)Map任務(wù)不僅要進(jìn)行數(shù)據(jù)塊的運(yùn)算,，還要讀取數(shù)據(jù)塊的統(tǒng)計(jì)結(jié)果,。三元N-gram算法通過Map函數(shù)將每個(gè)字詞分別于其前一個(gè)及前兩個(gè)詞的搭配映射為<key，values>的鍵值對(duì),，并將分區(qū)存儲(chǔ)的初始<key1,value1>鍵值對(duì)傳輸給相對(duì)數(shù)量的Map函數(shù),，這里增加多個(gè)Combine任務(wù)，它的作用主要是將<key1,，value1>鍵值對(duì)中相同key鍵的value值進(jìn)行累加處理,，生成新的鍵值對(duì)<key2，value2>，之后通過Partinner根據(jù)相同key鍵的鍵值對(duì)進(jìn)行重新均等分布存儲(chǔ),，相同key鍵的鍵值對(duì)分布在同一數(shù)據(jù)集中，其中Barrier負(fù)責(zé)將任務(wù)分配給空閑的map函數(shù),，同時(shí)采取概率統(tǒng)計(jì)的方式通過統(tǒng)計(jì)每個(gè)漢字分別與前兩個(gè)漢字搭配出現(xiàn)的次數(shù)產(chǎn)生檢驗(yàn)詞并將Map階段結(jié)果進(jìn)行合并得到局部統(tǒng)計(jì)結(jié)果,，最后將Map函數(shù)處理的結(jié)果傳輸?shù)絉educe，并進(jìn)行整合處理,，完成對(duì)分區(qū)后的<key2,，value2>進(jìn)行疊加處理，形成新的鍵值對(duì)<key3,，value3>,。如圖4所示，統(tǒng)計(jì)結(jié)果為<我是,，1><我愛,，2><中國，3><中國人,，3>……得到全局統(tǒng)計(jì)結(jié)果,，并設(shè)置閾值進(jìn)行比較，對(duì)于大于閾值的字詞搭配結(jié)果定義為正確項(xiàng),，從而生成語料庫,。
2.3 MapReduce的三元N-gram算法并行化實(shí)現(xiàn)
基于MapReduce的三元N-gram 算法得出統(tǒng)計(jì)概率結(jié)果的具體實(shí)現(xiàn)流程如下：
(1)對(duì)中文文本數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分割。InputFormat將對(duì)文本內(nèi)容進(jìn)行劃分,，從而得到n個(gè)規(guī)模相差無幾的數(shù)據(jù)塊并同時(shí)對(duì)其進(jìn)行格式化處理,，得到<key，values>鍵值對(duì)(key為分詞編號(hào),，values為該分詞所出現(xiàn)的次數(shù)),，在這之后將數(shù)據(jù)塊傳輸至m個(gè)節(jié)點(diǎn)。
(2)啟動(dòng)Map程序,，對(duì)所有數(shù)據(jù)塊進(jìn)行掃描,，把鍵值對(duì)轉(zhuǎn)換為特定的＜字詞，次數(shù)>格式,。
(3)Map程序編寫本地輸出的各類數(shù)據(jù)塊,，將每個(gè)漢字分別與前兩個(gè)漢字搭配出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，之后進(jìn)行合并累加處理,，并根據(jù)相同key將的鍵值對(duì)重新切分?jǐn)?shù)據(jù)集,，從而減少對(duì)中間結(jié)果數(shù)據(jù)量的統(tǒng)計(jì)，顯著提高計(jì)算效率,。
(4)調(diào)用Mapper接口對(duì)所有文本數(shù)據(jù)塊展開Map函數(shù)處理,，將包含相同鍵的鍵值對(duì)進(jìn)行合并處理，并將統(tǒng)計(jì)結(jié)果輸送至Reduce函數(shù)。所有Reduce函數(shù)獲得的結(jié)果都是從全部Map節(jié)點(diǎn)傳輸?shù)逆I值對(duì),。該函數(shù)能夠?qū)㈡I與值進(jìn)行分離,，利用Reduce階段對(duì)相同鍵的values值進(jìn)行統(tǒng)計(jì)處理。
(5)通過Reduce函數(shù)將概率統(tǒng)計(jì)結(jié)果與定義閾值進(jìn)行比較,，將符合閾值的分詞展開合并處理判定為正確字詞存入數(shù)據(jù)庫,，對(duì)不滿足閾值的項(xiàng)進(jìn)行分化操作，分別生成新生詞詞庫或錯(cuò)誤集詞庫,。
3 測試
3.1 測試環(huán)境
選擇5臺(tái)計(jì)算機(jī)在Linux環(huán)境下構(gòu)建Hadoop集群,，Hadoop平臺(tái)版本為2.6.0，操作系統(tǒng)均采用Ubuntu-16.04．04,，JDK版本為Sun JDK1.8,。一臺(tái)計(jì)算機(jī)作為Master和JobTracker服務(wù)節(jié)點(diǎn)，其他4臺(tái)計(jì)算機(jī)作為Slave TaskTracker服務(wù)節(jié)點(diǎn),，每個(gè)節(jié)點(diǎn)的處理器為Intel酷睿i5,，4 GB內(nèi)存。為體現(xiàn)MapReduce框架下的三元N-gram算法對(duì)海量中文文本數(shù)據(jù)的處理優(yōu)勢,，在此以50本小說的中文文本數(shù)據(jù)充當(dāng)實(shí)驗(yàn)數(shù)據(jù)集,。通過兩類算法在數(shù)據(jù)集上展開標(biāo)準(zhǔn)化的操作，結(jié)合得到的數(shù)據(jù)證明了對(duì)于處理海量數(shù)據(jù)而言,，基于MapReduce的三元N-gram并行化算法的性能更加優(yōu)良,。
3.2 實(shí)驗(yàn)結(jié)果與分析
實(shí)驗(yàn)過程中，首先設(shè)定數(shù)據(jù)集大小,，然后分析該算法在各類數(shù)目節(jié)點(diǎn)上實(shí)際運(yùn)行的時(shí)間,。通過圖5(a)的實(shí)驗(yàn)數(shù)據(jù)表明，在數(shù)據(jù)規(guī)模相對(duì)較小時(shí),，基于MapReduce的三元N-gram算法的平均效率低于傳統(tǒng)三元N-gram算法,。這是因?yàn)榧糁Ψ植际接?jì)算中對(duì)節(jié)點(diǎn)的調(diào)配增添了其他的開銷，該開銷在一定程度上增加了運(yùn)行時(shí)間,。圖5(b)的實(shí)驗(yàn)數(shù)據(jù)表明,，伴隨檢驗(yàn)文本數(shù)據(jù)的不斷擴(kuò)增，傳統(tǒng)三元N-gram算法的時(shí)間消耗持續(xù)增加,，遠(yuǎn)大于基于MapReduce的三元N-gram算法,，體現(xiàn)了基于MapReduce的三元N-gram算法的優(yōu)越性。這是由于傳統(tǒng)三元N-gram算法在對(duì)數(shù)據(jù)集進(jìn)行運(yùn)算的過程中應(yīng)用了序列化字符串查找的方法,，特別是在對(duì)海量數(shù)據(jù)集進(jìn)行處理時(shí),，序列化字符串查找過程的檢驗(yàn)文本數(shù)據(jù)總量很大，如此就顯著延長了計(jì)算時(shí)間,。而優(yōu)化的三元N-gram算法利用并行的Map與Reduce過程來分布并行統(tǒng)計(jì)查找,，當(dāng)計(jì)算機(jī)節(jié)點(diǎn)總量擴(kuò)增時(shí),，計(jì)算過程中消耗的時(shí)間縮減。這是由于它將數(shù)據(jù)進(jìn)行劃分,，在這之后通過服務(wù)器節(jié)點(diǎn)對(duì)其進(jìn)行處理,，然后并行執(zhí)行算法，如此就顯著優(yōu)化了整體的運(yùn)行效率,。結(jié)果對(duì)比如圖5所示,。
4 結(jié)論
本文設(shè)計(jì)并實(shí)現(xiàn)了基于MapReduce框架并行訓(xùn)練三元N-gram的算法，在應(yīng)用此算法對(duì)大規(guī)模語料庫進(jìn)行訓(xùn)練之后,，得到以下結(jié)論：
(1)該算法能夠?qū)Ａ繑?shù)據(jù)進(jìn)行均等分割,，分別部署到計(jì)算機(jī)集群中,，減少了單機(jī)運(yùn)行的內(nèi)存空間占據(jù)量,。
(2)該算法對(duì)海量數(shù)據(jù)的處理能夠發(fā)揮理想的效果，很大程度上解決了傳統(tǒng)算法在處理海量數(shù)據(jù)集計(jì)算時(shí)間過長的問題,。
(3)局部統(tǒng)計(jì)結(jié)果都分別存儲(chǔ)在磁盤中,，確保了統(tǒng)計(jì)結(jié)果不會(huì)丟失以及全局統(tǒng)計(jì)結(jié)果的重新計(jì)算，有效提高了對(duì)大量文本查錯(cuò)的效率,。
參考文獻(xiàn)
[1] 黃偉建.異構(gòu)云環(huán)境下MapReduce高效性的優(yōu)化研究[J].科學(xué)技術(shù)與工程,，2014，14(31)：73-77.
[2] 李書豪.基于N-gram模型的中文分詞前k優(yōu)算法[J].智能計(jì)算機(jī)與應(yīng)用,，2016,，6(6)：31-35.
[3] 駱聰.基于改進(jìn)的n-gram模型的URL分類算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2018(9)：1-5.
[4] 沈濤.結(jié)合N-gram模型與句法分析的語法糾錯(cuò)[D].南京：東南大學(xué),，2017.
[5] 鈕亮,，張寶友.MapReduce求解物流配送單源最短路徑研究[J].電子技術(shù)應(yīng)用，2014,，40(3)：123-125.
[6] 胡愛娜.基于MapReduce的分布式期望最大化算法[J].科學(xué)技術(shù)與工程,，2013，13(16)：4603-4606.
[7] 劉曉群,，鄒欣,，范虹.基于并行云計(jì)算模式的建筑結(jié)構(gòu)設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2011,，37(10)：123-125.
[8] 劉杰,，沈微微，戈軍,，等.基于MapReduce的并行抽樣路徑K-匿名隱私保護(hù)算法[J].電子技術(shù)應(yīng)用,，2017，43(9)：132-136.
[9] 吳信東.MapReduce與Spark用于大數(shù)據(jù)分析之比較[J].軟件學(xué)報(bào),，2018(6)：1770-1791.
[10] 劉云霞.MapReduce下相似性連接算法改進(jìn)的研究[D].大連：大連海事大學(xué),，2017.
[11] 李學(xué)明.基于3-gram模型和數(shù)據(jù)挖掘技術(shù)的元數(shù)據(jù)預(yù)取[J].重慶大學(xué)學(xué)報(bào),，2008，31(6)：658-662.
[12] Li Ning.Parallel improvement of Apriori algorithm based on MapReduce[J].Computer Technology and Development,，2017,，27(4)：64-68.
[13] LI B，ZHAO H,，LV Z H.Parallel ISODATA clustering of remote sensing images based on MapReduce[C].International Conference on Cyber-enabled Distributed Computing & Knowledge Discovery.IEEE Computer Society,，2010.
[14] Li Jianjian.Survey of MapReduce parallel programming model research[J].Electronic Journals，2011,，39(11)：2635-2642.
[15] BABU S.Towards automatic optimization of MapReduce programs[C].ACM Symposium on Cloud Computing,，2010.
作者信息:
龔永罡1，田潤琳1,，廉小親1,，夏 天2
（1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京100024,；2.中國人民大學(xué) 信息資源管理學(xué)院,，北京100872）