MapReduce实战:倒排索引

1.倒排索引简介

倒排索引(Inverted index),也常被称为反向索引置入档案反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

有两种不同的反向索引形式:

  • 一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。
  • 一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。

后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。

举例:

以英文为例,下面是要被索引的文本:

  • T0 = "it is what it is"
  • T1 = "what is it"
  • T2 = "it is a banana"

我们就能得到下面的反向文件索引:

检索的条件"what""is" 和 "it" 将对应这个集合:{0,1}∩{0,1,2}∩{0,1,2}={0,1}。

对相同的文字,我们得到后面这些完全反向索引,有文档数量和当前查询的单词结果组成的的成对数据。 同样,文档数量和当前查询的单词结果都从零开始。

所以,"banana": {(2, 3)} 就是说 “banana”在第三个文档里 (T2),而且在第三个文档的位置是第四个单词(地址为 3)。

如果我们执行短语搜索"what is it" 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。

2.分析和设计

(1)Map过程

首先使用默认的TextInputFormat类对输入文件进行处理,得到文本中每行的偏移量及其内容,Map过程首先必须分析输入的<key, value>对,得到倒排索引中需要的三个信息:单词、文档URI和词频,如图所示:

182227128605743

存在两个问题,第一:<key, value>对只能有两个值,在不使用Hadoop自定义数据类型的情况下,需要根据情况将其中的两个值合并成一个值,作为value或key值;

第二,通过一个Reduce过程无法同时完成词频统计和生成文档列表,所以必须增加一个Combine过程完成词频统计

(2)Combine过程

将key值相同的value值累加,得到一个单词在文档中的词频,如图

221942393901921

(3)Reduce过程

讲过上述两个过程后,Reduce过程只需将相同key值的value值组合成倒排索引文件所需的格式即可,剩下的事情就可以直接交给MapReduce框架进行处理了

3

完整代码如下:

参考资料

http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95

《实战Hadop:开启通向云计算的捷径.刘鹏》

3 收藏 2 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 看完感觉下面的程序并没有完成上面所说的倒排索引的建立,只是个简单的wordcount而已。而且combiner的使用也不正确,combiner是跟随在map输出之后执行的,如果一个文件分成两个map来处理,那么combiner并不能对整个文件中的单词进行处理,只能单个map的输出结果,所以reduce的输入中会存在同一个文件中同一个单词的词频未累加的情况。

跳到底部
返回顶部