网易视频云教你如何实现倒排索引

网易视频云教你如何实现倒排索引常规的索引是文档到关键词的映射：文档——关键词,但是这样检索关键词的时候很费力，要一个文档一个文档的遍历一遍。于是人们发明了倒排索引！倒排索引是关键词到文档的映射：关键词——文档。因此，只要有关键词，立马就能找到在那个文档里出现过，带来了极大的方便。下面，网易视频云就教教各位，倒排索引究竟是怎么实现的！1.倒排索引倒排索引有两种不同的反向索引形式：一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。举例：以英文为例，下面是要被索引的文本：T0=itiswhatitisT1=whatisitT2=itisabanana我们就能得到下面的反向文件索引：检索的条件what,is和it将对应这个集合：{0,1}∩{0,1,2}∩{0,1,2}={0,1}。对相同的文字，我们得到后面这些完全反向索引，有文档数量和当前查询的单词结果组成的的成对数据。同样，文档数量和当前查询的单词结果都从零开始。所以，banana:{(2,3)}就是说“banana”在第三个文档里(T2)，而且在第三个文档的位置是第四个单词(地址为3)。如果我们执行短语搜索whatisit我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。2.Map过程首先使用默认的TextInputFormat类对输入文件进行处理，得到文本中每行的偏移量及其内容，Map过程首先必须分析输入的key,value对，得到倒排索引中需要的三个信息：单词、文档URI和词频，如图所示：存在两个问题，第一：key,value对只能有两个值，在不使用Hadoop自定义数据类型的情况下，需要根据情况将其中的两个值合并成一个值，作为value或key值；第二，通过一个Reduce过程无法同时完成词频统计和生成文档列表，所以必须增加一个Combine过程完成词频统计。3.Combine过程将key值相同的value值累加，得到一个单词在文档中的词频，如图。4.Reduce过程讲过上述两个过程后，Reduce过程只需将相同key值的value值组合成倒排索引文件所需的格式即可，剩下的事情就可以直接交给MapReduce框架进行处理了。完整代码如下：学会倒排索引，跟着网易视频云一起走向云计算的捷径~~~