0 引言

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

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

1 模型的建立

1.1 三元N-gram模型的構造

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

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

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

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

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

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

    (4)第三次掃描：對檢錯規則進行具體執行，排除沒有幾率出現的字詞，從而優化整體的準確率。

1.2 MapReduce模型

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

    MapReduce分布處理數據的過程如圖2所示。在數據輸入環節，MapReduce可以進行數據量的等分處理，從而得到規模相差無幾的數據塊。Map任務(一般將其命名為Mapper)能夠對用戶界定的Map函數進行具體執行^[13]。在Map環節中，所有Map任務都能夠對特定的split進行處理，得到特定的＜key，values＞鍵值對，在通過Map函數處理以后，構成了一部分中間數據，這些數據在指定的位置進行儲存，在其提升至某個水平之后，將其轉移至本地磁盤。在Reduce階段，接收Map函數的數據結果，對輸入的＜key，value＞對展開標準化的處理。輸出環節：把處理得到的結果進行寫入，在任務執行的過程中，Hadoop框架會對任務調度進行有效的管理，并對任務的執行情況進行嚴密的監視，對一些運行未成功的任務進行重啟^[14-15]。

2 基于MapReduce的三元N-gram算法模型實現

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

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

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

    基于MapReduce的三元N-gram算法極大縮短了大規模數據量的計算運行時間以及對內存空間的依賴，執行效率相對于傳統的三元N-gram算法提升顯著。

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

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

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

2.3 MapReduce的三元N-gram算法并行化實現

    基于MapReduce的三元N-gram 算法得出統計概率結果的具體實現流程如下：

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

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

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

    (4)調用Mapper接口對所有文本數據塊展開Map函數處理，將包含相同鍵的鍵值對進行合并處理，并將統計結果輸送至Reduce函數。所有Reduce函數獲得的結果都是從全部Map節點傳輸的鍵值對。該函數能夠將鍵與值進行分離，利用Reduce階段對相同鍵的values值進行統計處理。

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

3 測試

3.1 測試環境

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

3.2 實驗結果與分析

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

4 結論

    本文設計并實現了基于MapReduce框架并行訓練三元N-gram的算法，在應用此算法對大規模語料庫進行訓練之后，得到以下結論：

    (1)該算法能夠對海量數據進行均等分割，分別部署到計算機集群中，減少了單機運行的內存空間占據量。

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

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

參考文獻

[1] 黃偉建.異構云環境下MapReduce高效性的優化研究[J].科學技術與工程，2014，14(31)：73-77.

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

[3] 駱聰.基于改進的n-gram模型的URL分類算法研究[J].計算機技術與發展，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）