《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于MapReduce的三元N-gram算法的并行化研究
基于MapReduce的三元N-gram算法的并行化研究
2019年電子技術(shù)應(yīng)用第5期
龔永罡1,，田潤琳1，廉小親1,，夏 天2
1.北京工商大學(xué) 計算機與信息工程學(xué)院,，北京100024；2.中國人民大學(xué) 信息資源管理學(xué)院,，北京100872
摘要： 大規(guī)模語料庫的訓(xùn)練是使用三元N-gram算法進行中文文本自動查錯中一個重要的基礎(chǔ)工作,。面對新媒體平臺每日高達百萬篇需處理的語料信息，單一節(jié)點的三元N-gram語言模型詞庫的構(gòu)建存在計算瓶頸,。在深入研究三元N-gram算法的基礎(chǔ)上,，提出了基于MapReduce計算模型的三元N-gram并行化算法的思想。MapReduce計算模型中,，將運算任務(wù)平均分配到m個節(jié)點,，三元N-gram算法在Map函數(shù)部分的主要任務(wù)是計算局部字詞分別與其前兩個字詞搭配出現(xiàn)的次數(shù)，Reduce函數(shù)部分的主要任務(wù)是合并Map部分統(tǒng)計字詞搭配出現(xiàn)的次數(shù),，生成全局統(tǒng)計結(jié)果,。實驗結(jié)果表明，運行在Hadoop集群上的基于MapReduce的三元N-gram并行化算法具有很好的運算性和可擴展性,，對于每日120億字的訓(xùn)練語料數(shù)據(jù)集,，集群環(huán)境下該算法得到訓(xùn)練結(jié)果的速率更接近于線性。
中圖分類號： TP301.6
文獻標(biāo)識碼： 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.
Research on parallelization of trigram N-gram algorithm based on MapReduce
Gong Yonggang1，Tian Runlin1,，Lian Xiaoqin1,，Xia Tian2
1.School of Computer and Information Engineering，Beijing Technology and Business University,，Beijing 100024,，China； 2.School of Information Resource Management,，Renmin University of China,，Beijing 100872，China
Abstract： The training of large-scale corpora is an important basic work for the automatic detection of Chinese texts using the trigram N-gram algorithm. Faced with up to one million pieces of data to be processed by the new media platform per day, there is a computational bottleneck in the construction of a single-node trigram N-gram language model lexicon. Based on the deep research of the trigram N-gram algorithm, the idea of trigram N-gram parallelization algorithm based on MapReduce programming model is proposed. In the MapReduce programming model, the arithmetic tasks are evenly distributed to m nodes. The main task of the trigram N-gram algorithm in the Map function part is to calculate the number of times the local words are matched with the first two words, while the main part of the Reduce function,，its task is to merge the number of occurrences of the statistical word matching in the Map part to generate global statistical results. The experimental results show that the MapReduce-based trigram N-gram parallelization algorithm running on Hadoop clusters has good performance and scalability. For a 12 billion word-per-day training corpus data set, the algorithm is obtained in a cluster environment. The rate of training results is more linear.
Key words : Chinese text ternary,；trigram N-gram；MapReduce framework,；parallelization,；Hadoop clusters

0 引言

    隨著“互聯(lián)網(wǎng)+”時代的到來和快速發(fā)展，新媒體（微博,、微信公眾號,、博客、論壇,、新聞客戶端等）已成為人們生活中不可分割的一部分,很多新聞媒體平臺,，每天原創(chuàng)新聞發(fā)布量巨大，而新聞的時效性使其會在短時間內(nèi)被各大媒體廣泛轉(zhuǎn)載轉(zhuǎn)發(fā),，人工審核是不切實際的,。因此，必須在稿件發(fā)出前采用基于語義分析的自動識別技術(shù)手段才能確?！凹皶r,、準(zhǔn)確”發(fā)現(xiàn)問題、定位問題,、解決問題[1-2],。利用概率統(tǒng)計方法來識別真詞錯誤的是采用詞和詞性的三元N-gram語言模型的方法可以以較小的存儲空間得到較高約束的N-gram平滑概率,，大大降低了統(tǒng)計模型的復(fù)雜度,，后繼訓(xùn)練工作量適宜,，對應(yīng)用域語言的適應(yīng)能力較強，三元N-gram語言模型在中文文本自動查錯應(yīng)用效果很好,，但需要大規(guī)模的中文語料庫進行訓(xùn)練[3-4],。以單機運行為主的數(shù)據(jù)處理方式制約了計算效率的提高，訓(xùn)練時間過長,、占用內(nèi)存過大等問題難以解決[5],。面對海量數(shù)據(jù)的處理，MapReduce模型將大規(guī)模數(shù)據(jù)處理作業(yè)拆分成若干個可獨立運行的任務(wù),，使用廣泛,，能夠降低并行編程難度，極大地縮短了處理時間,，已成為當(dāng)前大規(guī)模數(shù)據(jù)處理的主流技術(shù)[6-7],。

    本文在開源式分布處理平臺Hadoop基礎(chǔ)上，設(shè)計并實現(xiàn)了利用MapReduce框架并行的三元N-gram算法,，解決了單機運行三元N-gram算法時間過長,、內(nèi)存不足等問題，并通過實驗驗證該算法具有較好的處理速度和準(zhǔn)確率,。

1 模型的建立

1.1 三元N-gram模型的構(gòu)造

    在文本數(shù)據(jù)處理中,，首先以序列的方式對詞料進行切分, 在這之后對其序列展開分組處理。假定預(yù)測窗口的實際大小等于w,，當(dāng)存在全新的元數(shù)據(jù)請求時,，通過它對時間較長的元數(shù)據(jù)請求進行替換，如此就產(chǎn)生全新的組G[8-9],。因為在這個過程中應(yīng)用了3-gram模型,，因此針對所有組G來說,對前面2個文件元數(shù)據(jù)請求進行固定處理,而對于有序的序列,之后的w-2充當(dāng)無序序列。在分組結(jié)束之后,，對得到的組展開標(biāo)準(zhǔn)化的冗余處理,，并消除無序序列內(nèi)完全一致的元數(shù)據(jù)請求。除此之外,，應(yīng)將通過處理的組按照先后秩序進行數(shù)據(jù)連接[10],。進而從所有數(shù)據(jù)內(nèi)尋求概率最高的，并將其組建為規(guī)則,所有規(guī)則對預(yù)取的組進行標(biāo)準(zhǔn)化的合并,。下文將給出其具體的算法描述,。鄰接三元的概率估計的公式為：

     jsj3-gs1-2.gif

式中，P代表搭配出現(xiàn)的概率,；Wi代表隨機某一中文字符,，Wi-1,、Wi+1分別代表隨機某一中文字符的前、后中文字符,，Count(...)代表一個特定詞序列在整個語料庫中出現(xiàn)的累計次數(shù),。

    如圖1所示，識別步驟如下：

jsj3-t1.gif

    (1)預(yù)處理：對錄入的一篇文章,，通常情況下為TXT文件,，先對詞進行切分。作為語料庫,，一定要確保其不存在任何誤差,。

    (2)初次掃描：提取所有的特征序列，通過N-gram計算模型統(tǒng)計字詞出現(xiàn)次數(shù)N,，并把這個字詞以及統(tǒng)計的次數(shù)結(jié)果添加至mongo數(shù)據(jù)庫,。

    (3)第二次掃描：假如P不小于特定的閾值，那么識別結(jié)果不存在誤差,，判定為正確詞生成語料庫,；假如運算得到的詞句可信度P小于閾值，那么可具體執(zhí)行擴散操作,。

    (4)第三次掃描：對檢錯規(guī)則進行具體執(zhí)行,，排除沒有幾率出現(xiàn)的字詞，從而優(yōu)化整體的準(zhǔn)確率,。

1.2 MapReduce模型

    MapReduce是一類操作性強,、容錯性優(yōu)良的并行編程模型，基于MapReduce設(shè)計的程序具有很好的穩(wěn)定性和可擴展性,。其框架一般應(yīng)用“分而治之”的方式,，將對大規(guī)模數(shù)據(jù)集進行的各項操作進行分布處理，從而讓多個分節(jié)點一起完成,，之后對所有分節(jié)點的中間結(jié)果進行整合處理,，進而獲得所需的結(jié)果[11-12]。其處理的整個過程依托于兩類函數(shù),，分別是Map函數(shù)和Reduce函數(shù),，其中前者將任務(wù)進行分解處理，后者將任務(wù)處理的結(jié)果進行規(guī)范化的匯總處理,。而針對并行編程內(nèi)的其他問題,，其中比較具有代表性的包括分布式存儲、容錯處理等,，它們都是通過MapReduce框架進行標(biāo)準(zhǔn)化的處理,。

    MapReduce分布處理數(shù)據(jù)的過程如圖2所示。在數(shù)據(jù)輸入環(huán)節(jié),，MapReduce可以進行數(shù)據(jù)量的等分處理,，從而得到規(guī)模相差無幾的數(shù)據(jù)塊,。Map任務(wù)(一般將其命名為Mapper)能夠?qū)τ脩艚缍ǖ腗ap函數(shù)進行具體執(zhí)行[13]。在Map環(huán)節(jié)中,，所有Map任務(wù)都能夠?qū)μ囟ǖ膕plit進行處理,，得到特定的＜key，values＞鍵值對,，在通過Map函數(shù)處理以后,，構(gòu)成了一部分中間數(shù)據(jù),，這些數(shù)據(jù)在指定的位置進行儲存,，在其提升至某個水平之后，將其轉(zhuǎn)移至本地磁盤,。在Reduce階段,，接收Map函數(shù)的數(shù)據(jù)結(jié)果，對輸入的＜key,，value＞對展開標(biāo)準(zhǔn)化的處理,。輸出環(huán)節(jié)：把處理得到的結(jié)果進行寫入，在任務(wù)執(zhí)行的過程中,，Hadoop框架會對任務(wù)調(diào)度進行有效的管理,，并對任務(wù)的執(zhí)行情況進行嚴(yán)密的監(jiān)視，對一些運行未成功的任務(wù)進行重啟[14-15],。

jsj3-t2.gif

2 基于MapReduce的三元N-gram算法模型實現(xiàn)

2.1 MapReduce的三元N-gram算法并行化思想

    通過分析單機運行的三元N-gram算法,，針對其有序的計算模式進行并行化改進，提出了MapReduce框架下的三元N-gram算法,。對比MapReduce框架下的三元N-gram算法和常規(guī)單機運行的三元N-gram算法的時間長度和內(nèi)存空間占據(jù)量,，證明把三元N-gram算法移植到MapReduce框架下實現(xiàn)了對海量中文文本數(shù)據(jù)集的并行處理。

    運用三元N-gram算法對大量的中文文本數(shù)據(jù)集展開處理時,，其運算量達到較高的水平,，進而導(dǎo)致消耗的時間延長，這是該算法的不足之處,。盡管對這種算法展開了多次優(yōu)化,，然而伴隨數(shù)據(jù)規(guī)模的不斷擴增，三元N-gram算法由于計算需求超過一定限度而降低了效率,。因此,，該算法可應(yīng)用“分而治之”的理念:Hadoop的HDFS文件系統(tǒng)將文本數(shù)據(jù)分成n份規(guī)模相當(dāng)?shù)臄?shù)據(jù)塊進行存儲，然后把數(shù)據(jù)塊發(fā)送到m個節(jié)點,，運行Map函數(shù),，掃描每個數(shù)據(jù)塊，通過統(tǒng)計每個字詞分別與前兩個字詞搭配出現(xiàn)的次數(shù)產(chǎn)生字詞搭配統(tǒng)計數(shù)值,，每個數(shù)據(jù)集的局部數(shù)據(jù)統(tǒng)計算法與經(jīng)典的三元N-gram算法相同,；編寫Combine將Map階段結(jié)果進行合并,，之后依據(jù)相同字詞就統(tǒng)計結(jié)果進行重新分組，生成新的數(shù)據(jù)集,；利用Reduce函數(shù)得出全局相鄰詞間統(tǒng)計概率結(jié)果,，對概率統(tǒng)計結(jié)果進行閾值分割，根據(jù)統(tǒng)計結(jié)果與閾值的比較得出判定字詞搭配出現(xiàn)的正誤,，依次迭代,，對其文本進行詞組校對。

    基于MapReduce的三元N-gram算法極大縮短了大規(guī)模數(shù)據(jù)量的計算運行時間以及對內(nèi)存空間的依賴,，執(zhí)行效率相對于傳統(tǒng)的三元N-gram算法提升顯著,。

2.2 MapReduce的三元N-gram算法并行化策略

    MapReduce的三元N-gram算法的并行化計算是先將大規(guī)模中文文本數(shù)據(jù)集分成N份一定規(guī)模大小的數(shù)據(jù)塊(默認(rèn)以64 MB大小數(shù)據(jù)量進行就等分割存儲)，以便并行處理,，之后運行Map和Reduce函數(shù)計算,，得出統(tǒng)計結(jié)果。

    其算法流程如圖3所示,。MapReduce程序中包含多個Map和Reduce任務(wù),，且每個Map任務(wù)不僅要進行數(shù)據(jù)塊的運算，還要讀取數(shù)據(jù)塊的統(tǒng)計結(jié)果,。三元N-gram算法通過Map函數(shù)將每個字詞分別于其前一個及前兩個詞的搭配映射為<key,，values>的鍵值對，并將分區(qū)存儲的初始<key1,value1>鍵值對傳輸給相對數(shù)量的Map函數(shù),，這里增加多個Combine任務(wù),，它的作用主要是將<key1，value1>鍵值對中相同key鍵的value值進行累加處理,，生成新的鍵值對<key2,，value2>，之后通過Partinner根據(jù)相同key鍵的鍵值對進行重新均等分布存儲,，相同key鍵的鍵值對分布在同一數(shù)據(jù)集中,，其中Barrier負(fù)責(zé)將任務(wù)分配給空閑的map函數(shù)，同時采取概率統(tǒng)計的方式通過統(tǒng)計每個漢字分別與前兩個漢字搭配出現(xiàn)的次數(shù)產(chǎn)生檢驗詞并將Map階段結(jié)果進行合并得到局部統(tǒng)計結(jié)果,，最后將Map函數(shù)處理的結(jié)果傳輸?shù)絉educe,，并進行整合處理，完成對分區(qū)后的<key2,，value2>進行疊加處理,，形成新的鍵值對<key3，value3>,。如圖4所示,，統(tǒng)計結(jié)果為<我是，1><我愛，2><中國,，3><中國人,，3>……得到全局統(tǒng)計結(jié)果，并設(shè)置閾值進行比較,，對于大于閾值的字詞搭配結(jié)果定義為正確項,，從而生成語料庫。

jsj3-t3.gif

jsj3-t4.gif

2.3 MapReduce的三元N-gram算法并行化實現(xiàn)

    基于MapReduce的三元N-gram 算法得出統(tǒng)計概率結(jié)果的具體實現(xiàn)流程如下：

    (1)對中文文本數(shù)據(jù)集進行節(jié)點分割,。InputFormat將對文本內(nèi)容進行劃分,，從而得到n個規(guī)模相差無幾的數(shù)據(jù)塊并同時對其進行格式化處理，得到<key,，values>鍵值對(key為分詞編號,，values為該分詞所出現(xiàn)的次數(shù))，在這之后將數(shù)據(jù)塊傳輸至m個節(jié)點,。

    (2)啟動Map程序,，對所有數(shù)據(jù)塊進行掃描，把鍵值對轉(zhuǎn)換為特定的＜字詞,，次數(shù)>格式。

    (3)Map程序編寫本地輸出的各類數(shù)據(jù)塊,，將每個漢字分別與前兩個漢字搭配出現(xiàn)的次數(shù)進行統(tǒng)計,，之后進行合并累加處理，并根據(jù)相同key將的鍵值對重新切分?jǐn)?shù)據(jù)集,，從而減少對中間結(jié)果數(shù)據(jù)量的統(tǒng)計,，顯著提高計算效率。

    (4)調(diào)用Mapper接口對所有文本數(shù)據(jù)塊展開Map函數(shù)處理,，將包含相同鍵的鍵值對進行合并處理,，并將統(tǒng)計結(jié)果輸送至Reduce函數(shù)。所有Reduce函數(shù)獲得的結(jié)果都是從全部Map節(jié)點傳輸?shù)逆I值對,。該函數(shù)能夠?qū)㈡I與值進行分離,，利用Reduce階段對相同鍵的values值進行統(tǒng)計處理。

    (5)通過Reduce函數(shù)將概率統(tǒng)計結(jié)果與定義閾值進行比較,，將符合閾值的分詞展開合并處理判定為正確字詞存入數(shù)據(jù)庫,，對不滿足閾值的項進行分化操作，分別生成新生詞詞庫或錯誤集詞庫,。

3 測試

3.1 測試環(huán)境

    選擇5臺計算機在Linux環(huán)境下構(gòu)建Hadoop集群,，Hadoop平臺版本為2.6.0，操作系統(tǒng)均采用Ubuntu-16.04．04,，JDK版本為Sun JDK1.8,。一臺計算機作為Master和JobTracker服務(wù)節(jié)點，其他4臺計算機作為Slave TaskTracker服務(wù)節(jié)點，每個節(jié)點的處理器為Intel酷睿i5,，4 GB內(nèi)存,。為體現(xiàn)MapReduce框架下的三元N-gram算法對海量中文文本數(shù)據(jù)的處理優(yōu)勢，在此以50本小說的中文文本數(shù)據(jù)充當(dāng)實驗數(shù)據(jù)集,。通過兩類算法在數(shù)據(jù)集上展開標(biāo)準(zhǔn)化的操作,，結(jié)合得到的數(shù)據(jù)證明了對于處理海量數(shù)據(jù)而言，基于MapReduce的三元N-gram并行化算法的性能更加優(yōu)良,。

3.2 實驗結(jié)果與分析

    實驗過程中,，首先設(shè)定數(shù)據(jù)集大小，然后分析該算法在各類數(shù)目節(jié)點上實際運行的時間,。通過圖5(a)的實驗數(shù)據(jù)表明,，在數(shù)據(jù)規(guī)模相對較小時，基于MapReduce的三元N-gram算法的平均效率低于傳統(tǒng)三元N-gram算法,。這是因為剪枝分布式計算中對節(jié)點的調(diào)配增添了其他的開銷,，該開銷在一定程度上增加了運行時間。圖5(b)的實驗數(shù)據(jù)表明,，伴隨檢驗文本數(shù)據(jù)的不斷擴增,，傳統(tǒng)三元N-gram算法的時間消耗持續(xù)增加，遠(yuǎn)大于基于MapReduce的三元N-gram算法,，體現(xiàn)了基于MapReduce的三元N-gram算法的優(yōu)越性,。這是由于傳統(tǒng)三元N-gram算法在對數(shù)據(jù)集進行運算的過程中應(yīng)用了序列化字符串查找的方法，特別是在對海量數(shù)據(jù)集進行處理時,，序列化字符串查找過程的檢驗文本數(shù)據(jù)總量很大,，如此就顯著延長了計算時間。而優(yōu)化的三元N-gram算法利用并行的Map與Reduce過程來分布并行統(tǒng)計查找,，當(dāng)計算機節(jié)點總量擴增時,，計算過程中消耗的時間縮減。這是由于它將數(shù)據(jù)進行劃分,，在這之后通過服務(wù)器節(jié)點對其進行處理,，然后并行執(zhí)行算法，如此就顯著優(yōu)化了整體的運行效率,。結(jié)果對比如圖5所示,。

jsj3-t5.gif

4 結(jié)論

    本文設(shè)計并實現(xiàn)了基于MapReduce框架并行訓(xùn)練三元N-gram的算法，在應(yīng)用此算法對大規(guī)模語料庫進行訓(xùn)練之后,，得到以下結(jié)論：

    (1)該算法能夠?qū)Ａ繑?shù)據(jù)進行均等分割,，分別部署到計算機集群中，減少了單機運行的內(nèi)存空間占據(jù)量,。

    (2)該算法對海量數(shù)據(jù)的處理能夠發(fā)揮理想的效果,，很大程度上解決了傳統(tǒng)算法在處理海量數(shù)據(jù)集計算時間過長的問題,。

    (3)局部統(tǒng)計結(jié)果都分別存儲在磁盤中，確保了統(tǒng)計結(jié)果不會丟失以及全局統(tǒng)計結(jié)果的重新計算,，有效提高了對大量文本查錯的效率,。

參考文獻

[1] 黃偉建.異構(gòu)云環(huán)境下MapReduce高效性的優(yōu)化研究[J].科學(xué)技術(shù)與工程，2014,，14(31)：73-77.

[2] 李書豪.基于N-gram模型的中文分詞前k優(yōu)算法[J].智能計算機與應(yīng)用,，2016，6(6)：31-35.

[3] 駱聰.基于改進的n-gram模型的URL分類算法研究[J].計算機技術(shù)與發(fā)展,，2018(9)：1-5.

[4] 沈濤.結(jié)合N-gram模型與句法分析的語法糾錯[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] 劉曉群,，鄒欣，范虹.基于并行云計算模式的建筑結(jié)構(gòu)設(shè)計[J].電子技術(shù)應(yīng)用,，2011,，37(10)：123-125.

[8] 劉杰，沈微微,，戈軍,，等.基于MapReduce的并行抽樣路徑K-匿名隱私保護算法[J].電子技術(shù)應(yīng)用，2017,，43(9)：132-136.

[9] 吳信東.MapReduce與Spark用于大數(shù)據(jù)分析之比較[J].軟件學(xué)報，2018(6)：1770-1791.

[10] 劉云霞.MapReduce下相似性連接算法改進的研究[D].大連：大連海事大學(xué),，2017.

[11] 李學(xué)明.基于3-gram模型和數(shù)據(jù)挖掘技術(shù)的元數(shù)據(jù)預(yù)取[J].重慶大學(xué)學(xué)報,，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é) 計算機與信息工程學(xué)院，北京100024；2.中國人民大學(xué) 信息資源管理學(xué)院,，北京100872）

此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載。