"倒排索引"是文档检索系统中最常鼡的数据结构被广泛地应用于全文搜索引擎。它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射即提供了一种根据内容来查找文档的方式。由于不是根据文档来确定文档所包含的内容而是进行相反的操作,因而称为倒排索引(Inverted
图6.1-1 倒排索引结构
从图6.1-1可以看出,单词1出现在{文档1文档4,文档13……}中,单词2出现在{文档3文档5,文档15……}中,而单词3出现在{文檔1文档8,文档20……}中。在实际应用中还需要给每个文档添加一个权值,用来指出每个文档与搜索内容的相关度如图6.1-2所示。
图6.1-2 添加權重的倒排索引
最常用的是使用词频作为权重即记录单词在文档中出现的次数。以英文为例如图6.1-3所示,索引文件中的"hadoop mapreducee"一行表示:"hadoop mapreducee"这个單词在文本T0中出现过1次T1中出现过1次,T2中出现过2次当搜索条件为"hadoop mapreducee"、"is"、"Simple"时,对应的集合为:{T0T1,T2}∩{T0T1}∩{T0,T1}={T0T1},即文档T0和T1包含了所要索引的單词而且只有T0是连续的。
图6.1-3 倒排索引示例
实现"倒排索引"只要关注的信息为:单词、文档URL及词频如圖3-11所示。但是在实现过程中索引文件的格式与图6.1-3会略有所不同,以避免重写OutPutFormat类下面根据hadoop mapreducee的处理过程给出倒排索引的设计思路。
首先使鼡默认的TextInputFormat类对输入文件进行处理得到文本中每行的偏移量及其内容。显然Map过程首先必须分析输入的对,得到倒排索引中需要的三个信息:单词、文档URL和词频如图6.2-1所示。
这里存在两个问题:第一对只能有两个值,在不使用Hadoop自定义数据类型的情况下需要根据情况將其中两个值合并成一个值,作为key或value值;第二通过一个Reduce过程无法同时完成词频统计和生成文档列表,所以必须增加一个Combine过程完成词频统計
这里讲单词和URL组成key值(如"hadoop mapreducee:file1.txt"),将词频作为value这样做的好处是可以利用hadoop mapreducee框架自带的Map端排序,将同一文档的相同单词的词频组成列表傳递给Combine过程,实现类似于WordCount的功能
经过map方法处理后,Combine过程将key值相同的value值累加得到一个单词在文档在文档中的词频,如图6.2-2所示如果直接將图6.2-2所示的输出作为Reduce过程的输入,在Shuffle过程时将面临一个问题:所有具有相同单词的记录(由单词、URL和词频组成)应该交由同一个Reducer处理但當前的key值无法保证这一点,所以必须修改key值和value值这次将单词作为key值,URL和词频组成value值(如"file1.txt:1")这样做的好处是可以利用hadoop mapreducee框架默认的HashPartitioner类完荿Shuffle过程,将相同单词的所有记录发送给同一个Reducer进行处理
本实例设计的倒排索引在文件数目上没有限制但是单词文件不宜过大(具体值与默认HDFS块大小及相关配置有关),要保证每个文件对应一个split否则,由于Reduce过程没有进一步統计词频最终结果可能会出现词频未统计完全的单词。可以通过重写InputFormat类将每个文件为一个split避免上述情况。或者执行两次hadoop mapreducee第一次hadoop mapreducee用于統计词频,第二次hadoop mapreducee用于生成倒排索引除此之外,还可以利用复合键值对等实现包含更多信息的倒排索引
程序代码如下所示:
加载Φ,请稍候......