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）