隨著“互聯(lián)網(wǎng)+”時(shí)代的到來和快速發(fā)展，新媒體已成為人們生活中不可分割的一部分,很多新聞媒體平臺(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ī)模的中文語料庫(kù)進(jìn)行訓(xùn)練^[3-4]。以單機(jī)運(yùn)行為主的數(shù)據(jù)處理方式制約了計(jì)算效率的提高，訓(xùn)練時(shí)間過長(zhǎng)、占用內(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框架并行的，解決了單機(jī)運(yùn)行三元N-gram算法時(shí)間過長(zhǎng)、內(nèi)存不足等問題，并通過實(shí)驗(yàn)驗(yàn)證該算法具有較好的處理速度和準(zhǔn)確率。

1 模型的建立

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

在文本數(shù)據(jù)處理中，首先以序列的方式對(duì)詞料進(jìn)行切分, 在這之后對(duì)其序列展開分組處理。假定預(yù)測(cè)窗口的實(shí)際大小等于w，當(dāng)存在全新的元數(shù)據(jù)請(qǐng)求時(shí)，通過它對(duì)時(shí)間較長(zhǎng)的元數(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)的概率；W_i代表隨機(jī)某一中文字符，W_i-1、W_i+1分別代表隨機(jī)某一中文字符的前、后中文字符，Count(...)代表一個(gè)特定詞序列在整個(gè)語料庫(kù)中出現(xiàn)的累計(jì)次數(shù)。

如圖1所示，識(shí)別步驟如下：

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

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

(3)第二次掃描：假如P不小于特定的閾值，那么識(shí)別結(jié)果不存在誤差，判定為正確詞生成語料庫(kù)；假如運(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í)間長(zhǎng)度和內(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í)間延長(zhǎng)，這是該算法的不足之處。盡管對(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><中國(guó)，3><中國(guó)人，3>……得到全局統(tǒng)計(jì)結(jié)果，并設(shè)置閾值進(jìn)行比較，對(duì)于大于閾值的字詞搭配結(jié)果定義為正確項(xiàng)，從而生成語料庫(kù)。

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ù)庫(kù)，對(duì)不滿足閾值的項(xiàng)進(jìn)行分化操作，分別生成新生詞詞庫(kù)或錯(cuò)誤集詞庫(kù)。

3 測(cè)試

3.1 測(cè)試環(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)勢(shì)，在此以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ù)總量很大，如此就顯著延長(zhǎng)了計(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ī)模語料庫(kù)進(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í)間過長(zhǎng)的問題。

(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.