大数据平台与编程Ch5-MapReduce 程序设计2

MapReduce程序设计（2）,南华大学医学信息工程系,深入理解大数据-大数据处理与编程实践,关系代数运算,选择操作投影操作交运算差运算连接运算,差运算,计算R-T（这里关系T和关系R为同一种模式），也即希望找出在R中存在而在T中不存在的记录。Map：对于R和T中的每一条记录r，分别输出键值对（r,R）和(r,T）。Reduce：阶段检查一条记录r的所有对应值列表，如果只有R而没有T则将该条记录输出。,自然连接,我们需要在属性皿上做关系R和关系S的自然连接。Map：每一条R和S中的记录r，我们把它的ID的值作为键，其余属性的值以及R(S中的记录为S的名称）的名称作为值输出出去。Reduce：我们则将同一键中所有的值根据它们的来源（R和S）分为两组做笛卡尔乘积然后将得到的结果输出出去。例如以上面的关系R和关系S为例。关系R中ID为l的记录会以键值对（1,（(）（relationR,张小雅，20,91）发射出去，而关系S中ID为1的记录会以键值对（1,(relationS，女，165）发射出去，这里在值前面添加来源关系的名称是为了Reduce端能够辨别键值对的来源。在Reduce端ID为1的值有两个，按照它们的来源分为两组（张小雅，20,91）和（女，165），然后将这两组进行笛卡尔乘积并添加上ID（也就是键）作为新的值发出去，这里新的值为：（l，张小雅，20,91，女，165）。,矩阵乘法,工程中大矩阵一般以稀疏矩阵存储，仅存储非0值,矩阵乘法,矩阵乘法,HadoopI/O介绍,键、值类的主要特征1.作为键和值的类应该可以被序列化和反序列化、2.作为Reducer端的键类应该支持用户自定义排序,Writable和WritableComparable接口,WritableComparable同时实现Writable和Comparable接口Comparable接口intcompareTo(To)方法比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。,Writable类型举例,WritableComparable类型举例,单词共现算法,单词共现算法是MapReduce可以用来高效解决的一大类问题的抽象化描述。问题描述：在海量语料库中发现在固定窗口内单词a和单词b共同出现的频率，从而构建单词共现矩阵，这样的矩阵可以是对称的，也可以是不对称的应用：自然语言处理发现不同物品被同时购买信息检索领域同义词词典的构建文本挖掘,设有一个英文语句：wearenotwhatwewanttobebutatleastwearenotwhatweusedtobe.,Map端伪代码如下（窗口Window可以根据不同的应用需求有不同的定义，比例，可定义为一个固定大小的窗口，或者是前后相连出现、在同一句中出现、在同一段落中出现的单词等）：,Reduce端伪代码如下：,窗口大小为7，那么首先窗口先覆盖了Mapreduceisanewtechniquetoprocessbigdata，然后该节点将键值对（Mapreduce,is),I),(Mapreduce,a),1),(Mapreduce,new),I),(Mapreduce,technique),I),(Mapreduce,to),I),(Mapreduce,process),I）发射出去。随后窗口向后滑动一格，与上面相似，这时将（is,a),1),(is,new),1),(is,technique),I),(is,to),1),(is,process),1),(is,big),1）发射出去。最后再向后滑动一个单词至文档的末尾，与上面相似，发送相应的键值对出去。当窗口尾部已经到达文档尾部时，滑动窗口则通过将窗口头部向后“缩进”来进行，此过程一直进行到窗口大小为2停止。,单词共现算法实现中的细节问题发射出去的键是单词对而不再是一些基本数据类型，因此首先我们需要自定义一个WordPair类该类需要实现WritableComparable接口：实现write,readFields,compareTo方法相同的WordPair主键，顺序不一致，应认为是相等2.分区问题：相同的WordPair主键（不考虑顺序）都被发送到相同的Reduce节点去Reducer=(key.hashCode()&Integer.MAX_VALUE)%numReduceTasks自定义的hashCode()方法,而Reduce端的代码则比较简单，只是将同一个键的所有值进行简单的累加而已,文档倒排索引,带词频等属性的文档倒排索引主要功能是实现每个单词的倒排索引，并且统计出单词在每篇文档中出现的次数，并且要求对每个单词term按照文挡的顺序形成postings。此外，本算法的倒排对象还移除了stopwords（即诸如恼，of,is这些在检索中没有必要实现倒排索引的词汇）。为了处理方便，让每个节点都能共享该停词表，需要在程序的main函数部分添加共享的CacheFile，其示例代码如下：,上述Mapper程序输出的中间结果中，会包含大量相同主键的键值对。为此，需要使用Combiner将Mapper部分的输出的中间结果中的词频进行累加，以此减少向Reduce节点的数据量。Combiner代码如下：,由于key值从原先的单词term变成了（term,docid），在对key-value对进行sh