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