琥珀春秋

上周到这周四一直都在解决我的mapreduce程序的模式问题，应该说写的这个mapreduce程序经历过三次改变，就叫做v1，v2，v3三个版本吧。

v1版本出来后，在写入hbase中的时候，key值没有经过任何的处理，完全按照unicode码的方式存储。起初认为这个过程导致key值的分布过于紧密，因此考虑用md5加密对key值进行映射，使key值离散。然而在v2效率更低，原因猜测是key值在hbase中存储时，还是要按照顺序排放，那么的话就存在大量的io操作，再者经过md5加密后，key值变成了32位的字符串，可能也加大了寻找key值的难度。

第二：程序中存在大量的临时变量，在集群的几千万条记录中来回创建，回收内存，也是会耗费大量的时间和内存。虽然java存在垃圾回收机制，但是也不完美。所以，在从v1到v2的变化中，主要在于代码的优化，能够用静态变量来代替的就用静态变量来处理，以减少变量的来回创建。

v2版本的运行时间是131hours，这简直是无法忍受的。因此必须改变，必须从编程模型中改变。在v1，v2版本中，只是简单的运用了mapreduce这一编程模型中的map部分，对reduce部分没有运用，起初的想法也很简单，从一个表中读取数据，处理过后，放到另外一个表中，很简单。只需要运用到mapreduce分布式这一个特点就可以解决。事实证明，当时的想法过于简单了。 当涉及大量的io操作后，通过将数据以块的形式写入表中，而不是记录的方式，来减少io操作。这是我当时考虑的第一点。后来就想到利用mapreduce这一整个模型来计算。这一点，我和国华师兄不谋而合。

下面就把我的编程模型写下来：

新的优化方案，要减少io操作。涉及mapper,combiner,reducer整个过程，之前的方案只运用了mapper。

mapper设计思路：

1 从unindexedPapers 表中读取每篇paper的authors

2 进行分词

3 以名为key值（经SHA－1加密）, 姓＋次数（num表示） 作为value 作为输出。 list()

combiner思路：

1 以mapper输出作为输入

2 key2值相同，value2值也相同的，将num相加；key2值相同，value2值不同的，将其组合成一个集合即可

3 将 作为输出

reducer思路

1 将combiner传来的数据再次进行类似的combiner操作

2 从hbase中，以key2作为关键字从hbase中获取records，进行计算合并。

3 计算合并结果，再次插入hbase中。

今天早上在集群上运行这个程序后，最终以37mins中在6台电脑的集群上跑完了3000万条记录。证明方案是可行的。

早上小高兴了一把，不过随之而来的就是以前要考虑的一个问题，如何给出一个合理的数学公式，设计出一个合理的权重出来。下一阶段，要把概率统计的课本在翻看下，和国华师兄在好好分析分析，找出点idea，设计一个合理的数学公式出来。

科研的路真是不容易，各种绊脚石都存在，一一克服吧。

最近和国华师兄一起做的项目提出一种设想。通过将中文姓名进行切分，来为每一个姓名增加一个权重，从而利于后期解决学者关系中的重名问题。中文姓名目前能够通过一定的规则加以区分，目前问题出现在对于一些复姓的处理上，中国有很多很怪的复姓，举个例子：“周阳”。这是一个复姓。但是我想几乎没人会认为这个一个复姓。这样就出现一个问题，如果一个人叫“周阳明”，那么是“周阳，明”还是“周，阳明”呢？基于习惯，我想更多的人会选择后者。那天的讨论，我还记忆犹新，发散到新疆，西藏，日本等地的人名。今天叶小平教授说，分词不可能达到100%准确。这话讲的有道理。下面附上一篇博文，这里面我用到了第一种基于规则和基于统计的分词方法，同时我加入了一个模糊集，以保证匹配的正确性。
一、什么是分词：
分词就是将连续的字（词）序列按照一定的规范重新组合成词序列的过程。《信息处理用现代汉语分词规范》中对分词的定义是：从信息处理需要出发，按照特定的规范，对汉语按分词单位进行划分的过程。对于英文分词，只要简单地以空格为分界符就能很好地把句子分析出来。这是由于英文是以词为单位的。不同于英文，计算机对中文分词时，由于中文句子中词与词之间是没有空格的，而且，两个字组合起来看似是一个词在句子中未必是一个词，所以计算机想要识别出中文句子中的词，就必须采用不同于英文分词的新技术。

二、分词出现的必要性:
1)人与计算机的沟通的基础。
由于中文文本的字与字之间的连续性，即汉语文本中词与词之间却没有明确的分隔标记，计算机无法识别出中文文本中哪些汉字串组合成词，导致处理中文信息无法直接理解中文的意义。所以，中文信息处理就必须比西文信息处理多了中文分词这一基本的步骤。汉语的中文信息处理就是要“用计算机对汉语的音、形、义进行处理”。而“词是最小的能够独立活动的有意义的语言成分”。
2）中文信息处理的基础性工作。
互联网的出现，彻底改变了人们对世界的认识;获得信息的成本越来越低，时间越来越短，信息量也越来越大.在信息贫泛与信息爆炸同时存在的时候，伴着信息几何级增长，如何对海量数据的处理，快速的定位到资源，是信息化时代不可缺少的部分。由此发展而来的，信息检索技术，文本挖掘，都是依赖于分词技术，分词技术还广泛应用于，文本校对、机器翻译、语音识别等领域。

三、分词处理技术：
目前对汉语分词方法的研究主要有三个方面：基于规则的分词方法、基于统计的分词方法和基于理解的分词方法。

1）基于规则的分词方法，这种方法又叫做机械分词方法,它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功(识别出一个词) 。常用的方法：最小匹配算法(Minimum Matching)，正向（逆向）最大匹配法(Maximum Matching)，逐字匹配算法,神经网络法、联想一回溯法，基于N-最短路径分词算法,以及可以相互组合，例如,可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法等。目前机械式分词占主流地位的是正向最大匹配法和逆向最大匹配法.
在所有的分词算法中，最早研究的是最小匹配算法(Minimum Matching)，该算法从待比较字符串左边开始比较，先取前两个字符组成的字段与词典中的词进行比较，如果词典中有该词，则分出此词，继续从第三个字符开始取两个字符组成的字段进行比较，如果没有匹配到，则取前3个字符串组成的字段进行比较，依次类推，直到取的字符串的长度等于预先设定的阈值，如果还没有匹配成功，则从待处理字串的第二个字符开始比较，如此循环。例如，“如果还没有匹配成功”，取出左边两个字组成的字段与词典进行比较，分出“如果”；再从“还”开始，取“还没”，字典中没有此词，继续取“还没有”，依次取到字段“还没有匹配”(假设阈值为5)，然后从“没”开始，取“没有”，如此循环直到字符串末尾为止。这种方法的优点是速度快，但是准确率却不是很高，比如待处理字符串为“中华人民共和国”，此匹配算法分出的结果为：中华、人民、共和国，因此该方法基本上已经不被采用 。
基于字符串的最大匹配，这种方法现在仍比较常用，最大匹配(Maximum Matching)分为正向和逆向两种最大匹配，正向匹配的基本思想是：假设词典中最大词条所含的汉字个数为n个，取待处理字符串的前n个字作为匹配字段，查找分词词典。若词典中含有该词，则匹配成功，分出该词，然后从被比较字符串的n+1处开始再取n个字组成的字段重新在词典中匹配；如果没有匹配成功，则将这n个字组成的字段的最后一位剔除，用剩下的n一1个字组成的字段在词典中进行匹配，如此进行下去，直到切分成功为止。例如，待处理字符串为“汉字多为表意文字”，取字符串“汉语多为表”(假设比较的步长为5，本文步长step都取5)与词典进行比较，没有与之对应的词，去除“表”字，用字段“汉语多为”进行匹配，直至匹配到“汉语”为至，再取字符串“多为表意”，循环到切分出“文字”一词。目前，正向最大匹配方法作为一种基本的方法已被肯定下来，但是由于错误比较大，一般不单独使用。如字符串“处理机器发生的故障”，在正向最大匹配方法中会出现歧义切分，该字符串被分为：处理机、发生、故障，但是使用逆向匹配就能得到有效的切分。
逆向最大匹配RMM(Reverse Directional Maximum Matching Method)的分词原理和过程与正向最大匹配相似，区别在于前者从文章或者句子(字串)的末尾开始切分，若不成功则减去最前面的一个字。比如对于字符串“处理机器发生的故障”，第一步，从字串的右边取长度以步长为单位的字段“发生的故障”在词典中进行匹配，匹配不成功，再取字段“生的故障”进行匹配，依次匹配，直到分出“故障”一词，最终使用RMM方法切分的结果为：故障、发生、机器、处理。该方法要求配备逆序词典。
一般来说根据汉语词汇构成的特点，从理论上说明了逆向匹配的精确度高于正向匹配，汉语语句的特点一般中心语偏后。有研究数据,单纯使用正向最大匹配的错误率为1/ 169 ,单纯使用逆向最大匹配的错误率为1/245。实际应用中可以从下面几方面改进，同时采取几种分词算法，来提高正确率;改进扫描方式，称为特征扫描或标志切分,优先在待分析字符串中识别和切分出一些带有明显特征的词,以这些词作为断点,可将原字符串分为较小的串再来进机械分词,
从而减少匹配的错误率等。
逐字匹配算法，基于TRIE索引树的逐字匹配算法,是建立在树型词典机制上，匹配的过程是从索引树的根结点依次同步匹配待查词中的每个字，可以看成是对树某一分枝的遍历。因此，采用该算法的分词速度较快，但树的构造和维护比较复杂。一种改进的算法是和最大匹配算法相结合，吸取最大匹配算法词典结构简单、TRIE索引树算法查询速度快的优点。因此词典结构和最大匹配词典构造机制相似，区别在于词典正文前增加了多级索引。匹配过程类似TRIE索引树进行逐字匹配，在性能上和TRIE索引树相近。
神经网络分词算法，尹峰等提出了以神经网络理论(BP模型)为基础的汉语分词模型,为汉语分词研究开辟了新途径。在实用中,BP算法存在收敛速度慢、易陷入局部最小等缺点,严重妨碍了分词速度。一种改进算法采用Levenbery2Marquart 算法来加速收敛速度,加快了收敛速度利用神经网络的基本原理进行分词。
联想—回溯法(Association－Backtracking Method，简称 AB 法)。这种方法要求建立三个知识库——特征词词库、实词词库和规则库。首先将待切分的汉字字符串序列按特征词词库分割为若干子串，子串可以是词，也可以是由几个词组合而成的词群；然后，再利用实词词库和规则库将词群再细分为词。切词时，要利用一定的语法知识，建立联想机制和回溯机制。联想机制由联想网络和联想推理构成，联想网络描述每个虚词的构词能力，联想推理利用相应的联想网络来判定所描述的虚词究竟是单独成词还是作为其他词中的构词成分。回溯机制主要用于处理歧义句子的切分。联想—回溯法虽然增加了算法的时间复杂度和空间复杂度，但这种方法的切词正确率较高，是一种行之有效的方法。
基于N-最短路径分词算法，其基本思想是根据词典，找出字串中所有可能的词，构造词语切分有向无环图。每个词对应图中的一条有向边，并赋给相应的边长(权值)。然后针对该切分图，在起点到终点的所有路径中，求出长度值按严格升序排列(任何两个不同位置上的值一定不等，下同)依次为第1，第2，…，第i，…，第N的路径集合作为相应的粗分结果集。如果两条或两条以上路径长度相等，那么他们的长度并列第 i，都要列入粗分结果集，而且不影响其他路径的排列序号，最后的粗分结果集合大小大于或等于N。N一最短路径方法实际上是最短路径方法和全切分的有机结合。该方法的出发点是尽量减少切分出来的词数，这和最短路径分词方法是完全一致的；同时又要尽可能的包含最终结果，这和全切分的思想是共通的。通过这种综合，一方面避免了最短路径分词方法大量舍弃正 确结果的可能，另一方面又大大解决了全切分搜索空间过大，运行效率差的弊端。N一最短路径方法相对的不足就是粗分结果不唯一 ，后续过程需要处理多个粗分结果。 但是 ，对于预处理过程来讲，粗分结果的高召回率至关重要。因为低召回率就意味着没有办法 再作后续的补救措施。预处理一旦出错，后续处理只能是一错再错 ，基本上得不到正确的最终 结果。而少量的粗分结果对后续过程的运行效率影响不会太大，后续处理可以进一步优选排 错，如词性标注、句法分析等。
除上面之外，还有基于词频统计的切词法， 基于期望的切词法，有穷多级列举法等。

2）基于统计的分词方法，基于统计的方法是基于(两个或多个) 汉字同时出现的概率,通过对语料库(经过处理的大量领域文本的集合)中的文本进行有监督或无监督的学习．可以获取该类文本的某些整体特征或规律。如果 能够充分地利用这些统计现象、规律 ．就可以构造基于语料 库的统计学信息抽取算法统计的分析方法多种多样．近来研究的热点主要集中于由随机过程发展而来的理论和方法，其中最重要的是应用隐马尔科夫模型(HMM)进行自然语言处理的方法。隐马尔科夫模型,在语音识别领域已经取得了很好的成效,在信息抽取领域的应用也正在不断的尝试和推广中 。

3）基于理解分词，又称之为知识分词,知识分词是一种理想的分词方法,但这类分词方案的算法复杂度高,其有效性与可行性尚需在实际工作中得到进一步的验证。知识分词利用有关词、句子等的句法和语义信息或者从大量语料中找出汉字组词的结合特点来进行评价,以期找到最贴近于原句语义的分词结果。