精华内容
下载资源
问答
  • 文档倒排索引的MapReduce程序设计实现
  • 深入理解正排索引与倒排索引设计思想数据结构)

    在了解倒排索引之前,我们需要先了解下正排索引

    正排索引(foward index)

    正排索引也称为"前向索引"。它是创建倒排索引的基础,通过文档到关键字(doc->word)的映射,具有以下字段。

    (1)LocalId字段(表中简称"Lid"):表示一个文档的局部编号。

    (2)WordId字段:表示文档分词后的编号,也可称为"索引词编号"。

    (3)NHits字段:表示某个索引词在文档中出现的次数。

    (4)HitList变长字段:表示某个索引词在文档中出现的位置,即相对于正文的偏移量。

    基本结构可以理解为:

    docID1 -> word1:出现次数,出现的位置List;word2:出现次数,出现的位置List;

    docID2-> word1:出现次数,出现的位置List;word2:出现次数,出现的位置List;word3:出现次数,出现的位置List;

    以下是一个简单的图片示意:

    因此正排索引是通过文档标识(如:Doc1)来寻找关键字,可以知道一个网页中是否包含了某个关键字、关键字出现了几次以及关键字出现的位置。但是往往在网页检索或者其他搜索情况下是通过关键字来找文档,因此需要把正排索引转换为倒排索引,才能满足实际的需求。

    倒排索引

    接下来我们就需要一步步了解倒排索引的理念和结构

    1.单词——文档矩阵


          单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图1展示了其含义。图3-1的每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系。

     

                              图1 单词-文档矩阵

         从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其它单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过单词1,而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。

    2.倒排索引的基本概念

        搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式,所以本博文主要介绍“倒排索引”的技术细节。

           文档(Document):一般搜索引擎的处理对象是互联网网页,而文档这个概念要更宽泛些,代表以文本形式存在的存储对象,相比网页来说,涵盖更多种形式,比如Word,PDF,html,XML等不同格式的文件都可以称之为文档。再比如一封邮件,一条短信,一条微博也可以称之为文档。在本书后续内容,很多情况下会使用文档来表征文本信息。

           文档集合(Document Collection):由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。

           文档编号(Document ID):在搜索引擎内部,会将文档集合内每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识,这样方便内部处理,每个文档的内部编号即称之为“文档编号”,后文有时会用DocID来便捷地代表文档编号。

           单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。

           倒排索引(Inverted Index):倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

           单词词典(Lexicon):搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

           倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。

           倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

    可以通过以下图了解其结构:

    word1 -> 文档列表(不仅仅包含了文档ID,还可以记录额外的信息,比如:词频等)

    3.倒排索引简单实例


          倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。

          假设文档集合包含五个文档,每个文档内容如图3所示,在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。

    图示为文档集合:

                  

                               图3   文档集合

      中文和英文等语言不同,单词之间没有明确分隔符号,所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流,为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引(参考图3-4)。在图4中,“单词ID”一栏记录了每个单词的单词编号,第二栏是对应的单词,第三栏即每个单词对应的倒排列表。比如单词“谷歌”,其单词编号为1,倒排列表为{1,2,3,4,5},说明文档集合中每个文档都包含了这个单词。

                  

                                图4   简单的倒排索引

      之所以说图4所示倒排索引是最简单的,是因为这个索引系统只记载了哪些文档包含某个单词,而事实上,索引系统还可以记录除此之外的更多信息。图5是一个相对复杂些的倒排索引,与图4的基本索引系统比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。在图5的例子里,单词“创始人”的单词编号为7,对应的倒排列表内容为:(3:1),其中的3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次,其它单词对应的倒排列表所代表含义与此相同。

                  

                                图 5 带有单词频率信息的倒排索引

       实用的倒排索引还可以记载更多的信息,图6所示索引系统除了记录文档编号和单词频率信息外,额外记载了两类信息,即每个单词对应的“文档频率信息”(对应图6的第三栏)以及在倒排列表中记录单词在某个文档出现的位置信息。

                      

                           图6   带有单词频率、文档频率和出现位置信息的倒排索引

       “文档频率信息”代表了在文档集合中有多少个文档包含某个单词,之所以要记录这个信息,其原因与单词频率信息一样,这个信息在搜索结果排序计算中是非常重要的一个因子。而单词在某个文档中出现的位置信息并非索引系统一定要记录的,在实际的索引系统里可以包含,也可以选择不包含这个信息,之所以如此,因为这个信息对于搜索系统来说并非必需的,位置信息只有在支持“短语查询”的时候才能够派上用场。

         以单词“拉斯”为例,其单词编号为8,文档频率为2,代表整个文档集合中有两个文档包含这个单词,对应的倒排列表为:{(3;1;<4>),(5;1;<4>)},其含义为在文档3和文档5出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第四个单词是“拉斯”。

         图6所示倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此,区别无非是采取哪些具体的数据结构来实现上述逻辑结构。

         有了这个索引系统,搜索引擎可以很方便地响应用户的查询,比如用户输入查询词“Facebook”,搜索系统查找倒排索引,从中可以读出包含这个单词的文档,这些文档就是提供给用户的搜索结果,而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序,计算文档和查询的相似性,按照相似性得分由高到低排序输出,此即为搜索系统的部分内部流程,具体实现方案本书第五章会做详细描述。

    如:Facebook-> doc1,doc2....(排序后)呈现给网页

    4. 单词词典


      单词词典是倒排索引中非常重要的组成部分,它用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。
           对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构和树形词典结构。


    4.1   哈希加链表


           图7是这种词典结构的示意图。这种词典结构主要由两个部分构成:

            主体部分是哈希表,每个哈希表项保存一个指针,指针指向冲突链表,在冲突链表里,相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词获得相同的哈希值,如果是这样,在哈希方法里被称做是一次冲突,可以将相同哈希值的单词存储在链表里,以供后续查找。               

      在建立索引的过程中,词典结构也会相应地被构建出来。比如在解析一个新文档的时候,对于某个在文档中出现的单词T,首先利用哈希函数获得其哈希值,之后根据哈希值对应的哈希表项读取其中保存的指针,就找到了对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词,说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,相应的词典结构也就建立起来了。

           在响应用户查询请求时,其过程与建立词典类似,不同点在于即使词典里没出现过某个单词,也不会添加到词典内。以图7为例,假设用户输入的查询请求为单词3,对这个单词进行哈希,定位到哈希表内的2号槽,从其保留的指针可以获得冲突链表,依次将单词3和冲突链表内的单词比较,发现单词3在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的倒排列表来进行后续的工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

    4.2   树形结构


           B树(或者B+树)是另外一种高效查找结构,图8是一个 B树结构示意图。B树与哈希方式查找不同,需要字典项能够按照大小排序(数字或者字符序),而哈希方式则无须数据满足此项要求。
           B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用,最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。

     

    小结:

    从上面的可以大致看到倒排列表起到的作用,倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里面会有很多文档包含某个单词,每个文档会记录文档编号(DocID),单词在这个文档中出现的次数(TF-term frequency)以及单词在文档中出现的位置信息等,这样与一个文档相关的信息被称作倒排索引项(Posting),包含这个单词的一系列倒排索引项形成了列表结构,这就是某个单词对应的倒排列表。如下图:

    在实际的搜索引擎中,并不存储倒排索引项中的实际文档编号,而是使用文档编号差值,为什么?

    文档编号差值是倒排索引列表中相邻的两个倒排索引项文档编号的差值,一般在索引构建过程中,可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号,索引文档编号的差值总是大于0的整数。如下图,将原始的文档编号为187,196,199,通过编号差值计算,转为:187,9,3

    之所以要对文档编号进行差值计算,主要原因是为了更好地对数据进行压缩,原始文档编号一般都是大数值,通过差值计算,就有效地将大叔之转为了小数值,有助于增加数据的压缩率。

    正排索引、倒排索引在搜索引擎的作用


    倒排所有主要的作用就是召回,正排索引的作用主要是排序(计算分数),聚合等操作,获取dataid对应的detail信息
    对一个大型搜索引擎,召回只是最基本、最简单的功能,所以倒排index 只占整个搜索index的20%--30%;相反正排索引真正占70--80%(其中排序的正排又占大头)
    对于taobao 等的搜索来说:key 对应的doc集合就是所有title里面包括了搜索key(分过词、纠过错的)的所有宝贝的集合
    正排索引主要是用来进行排序的

    参考:

    《这就是搜索引擎——核心技术详解》

    展开全文
  • 倒排索引 参考链接:https://blog.csdn.net/Xw_Classmate/article/details/50639848 “ 倒排索引”是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。 它主要是用来存储某个单词(或词组) 在一个...

    倒排索引

    • 参考链接:https://blog.csdn.net/Xw_Classmate/article/details/50639848

    “ 倒排索引”是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。 它主要是用来存储某个单词(或词组) 在一个文档或一组文档中的存储位置的映射,即提 供了一种根据内容来查找文档的方式。由于不是根据文档来确定文档所包含的内容,而是进 行相反的操作,因而称为倒排索引( Inverted Index)。

    1 实例描述

    通常情况下,倒排索引由一个单词(或词组)以及相关的文档列表组成,文档列表中的 文档或者是标识文档的 ID 号,或者是指文档所在位置的 URL,如图 6.1-1 所示。

    [外链图片转存失败(img-a6OHY0ai-1567902000353)(assets/1566473796048.png)]

    从图 6.1-1 可以看出,单词 1 出现在{文档 1,文档 4,文档 13, ……}中,单词 2 出现 在{文档 3,文档 5,文档 15, ……}中,而单词 3 出现在{文档 1,文档 8,文档 20, ……} 中。在实际应用中, 还需要给每个文档添加一个权值,用来指出每个文档与搜索内容的相 关度,如图 6.1-2 所示。

    在这里插入图片描述

    最常用的是使用词频作为权重,即记录单词在文档中出现的次数。以英文为例,如图 6.1-3 所示,索引文件中的“ MapReduce”一行表示:“ MapReduce”这个单词在文本 T0 中 出现过 1 次,T1 中出现过 1 次,T2 中出现过 2 次。当搜索条件为“ MapReduce”、“ is”、“ Simple” 时,对应的集合为: {T0, T1, T2}∩{T0, T1}∩{T0, T1}={T0, T1},即文档 T0 和 T1 包 含了所要索引的单词,而且只有 T0 是连续的。

    在这里插入图片描述

    更复杂的权重还可能要记录单词在多少个文档中出现过,以实现 TF-IDF( Term Frequency-Inverse Document Frequency)算法,或者考虑单词在文档中的位置信息(单词是 否出现在标题中,反映了单词在文档中的重要性)等。

    样例输入如下所示。

    file1:

    MapReduce is simple
    

    file2:

    MapReduce is powerful is simple
    

    file3:

    Hello MapReduce bye MapReduce
    

    样例输出如下所示:

    MapReduce file1.txt:1;file2.txt:1;file3.txt:2;
    is file1.txt:1;file2.txt:2;
    simple file1.txt:1;file2.txt:1;
    powerful file2.txt:1;
    Hello file3.txt:1;
    bye file3.txt:1;
    

    2 设计思路

    实现“ 倒排索引”只要关注的信息为: 单词、 文档 URL 及词频,如图 3-11 所示。但是 在实现过程中,索引文件的格式与图 6.1-3 会略有所不同,以避免重写 OutPutFormat 类。下 面根据 MapReduce 的处理过程给出倒排索引的设计思路。

    1)Map过程

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

    在这里插入图片描述

    这里存在两个问题: 第一, <key,value>对只能有两个值,在不使用 Hadoop 自定义数据 类型的情况下,需要根据情况将其中两个值合并成一个值,作为 key 或 value 值; 第二,通 过一个 Reduce 过程无法同时完成词频统计和生成文档列表,所以必须增加一个 Combine 过程完成词频统计。

    这里讲单词和 URL 组成 key 值(如“ MapReduce: file1.txt”),将词频作为 value,这样 做的好处是可以利用 MapReduce 框架自带的 Map 端排序,将同一文档的相同单词的词频组 成列表,传递给 Combine 过程,实现类似于 WordCount 的功能。

    2)Combine过程

    经过 map 方法处理后, Combine 过程将 key 值相同的 value 值累加,得到一个单词在文 档在文档中的词频,如图 6.2-2 所示。 如果直接将图 6.2-2 所示的输出作为 Reduce 过程的输 入,在 Shuffle 过程时将面临一个问题:所有具有相同单词的记录(由单词、 URL 和词频组 成) 应该交由同一个 Reducer 处理,但当前的 key 值无法保证这一点,所以必须修改 key 值 和 value 值。这次将单词作为 key 值, URL 和词频组成 value 值(如“ file1.txt: 1”)。这样 做的好处是可以利用 MapReduce 框架默认的 HashPartitioner 类完成 Shuffle 过程,将相同单 词的所有记录发送给同一个 Reducer 进行处理。

    在这里插入图片描述

    3)Reduce过程

    经过上述两个过程后, Reduce 过程只需将相同 key 值的 value 值组合成倒排索引文件所 需的格式即可,剩下的事情就可以直接交给 MapReduce 框架进行处理了。如图 6.2-3 所示。 索引文件的内容除分隔符外与图 6.1-3 解释相同。

    4)需要解决的问题

    本实例设计的倒排索引在文件数目上没有限制,但是单词文件不宜过大(具体值与默 认 HDFS 块大小及相关配置有关),要保证每个文件对应一个 split。否则,由于 Reduce 过 程没有进一步统计词频,最终结果可能会出现词频未统计完全的单词。可以通过重写 InputFormat 类将每个文件为一个 split,避免上述情况。或者执行两次 MapReduce, 第一次 MapReduce 用于统计词频, 第二次 MapReduce 用于生成倒排索引。除此之外,还可以利用 复合键值对等实现包含更多信息的倒排索引。

    在这里插入图片描述

    3 程序代码

    InvertedIndexMapper:
    package cn.nuc.hadoop.mapreduce.invertedindex;
     
    import java.io.IOException;
     
    import org.apache.commons.lang.StringUtils;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.lib.input.FileSplit;
     
    public class InvertedIndexMapper extends Mapper<LongWritable, Text, Text, Text> {
     
    	private static Text keyInfo = new Text();// 存储单词和 URL 组合
    	private static final Text valueInfo = new Text("1");// 存储词频,初始化为1
     
    	@Override
    	protected void map(LongWritable key, Text value, Context context)
    			throws IOException, InterruptedException {
     
    		String line = value.toString();
    		String[] fields = StringUtils.split(line, " ");// 得到字段数组
     
    		FileSplit fileSplit = (FileSplit) context.getInputSplit();// 得到这行数据所在的文件切片
    		String fileName = fileSplit.getPath().getName();// 根据文件切片得到文件名
     
    		for (String field : fields) {
    			// key值由单词和URL组成,如“MapReduce:file1”
    			keyInfo.set(field + ":" + fileName);
    			context.write(keyInfo, valueInfo);
    		}
    	}
    }
    
    InvertedIndexCombiner:
    package cn.nuc.hadoop.mapreduce.invertedindex;
     
    import java.io.IOException;
     
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Reducer;
     
    public class InvertedIndexCombiner extends Reducer<Text, Text, Text, Text> {
     
    	private static Text info = new Text();
     
    	// 输入: <MapReduce:file3 {1,1,...}>
    	// 输出:<MapReduce file3:2>
    	@Override
    	protected void reduce(Text key, Iterable<Text> values, Context context)
    			throws IOException, InterruptedException {
    		int sum = 0;// 统计词频
    		for (Text value : values) {
    			sum += Integer.parseInt(value.toString());
    		}
     
    		int splitIndex = key.toString().indexOf(":");
    		// 重新设置 value 值由 URL 和词频组成
    		info.set(key.toString().substring(splitIndex + 1) + ":" + sum);
    		// 重新设置 key 值为单词
    		key.set(key.toString().substring(0, splitIndex));
    		
    		context.write(key, info);
    	}
    }
    
    InvertedIndexReducer:
    package cn.nuc.hadoop.mapreduce.invertedindex;
     
    import java.io.IOException;
     
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Reducer;
     
    public class InvertedIndexReducer extends Reducer<Text, Text, Text, Text> {
     
    	private static Text result = new Text();
     
    	// 输入:<MapReduce file3:2>
    	// 输出:<MapReduce file1:1;file2:1;file3:2;>
    	@Override
    	protected void reduce(Text key, Iterable<Text> values, Context context)
    			throws IOException, InterruptedException {
    		// 生成文档列表
    		String fileList = new String();
    		for (Text value : values) {
    			fileList += value.toString() + ";";
    		}
     
    		result.set(fileList);
    		context.write(key, result);
    	}
    }
    
    InvertedIndexRunner:
    	package cn.nuc.hadoop.mapreduce.invertedindex;
     
    import java.io.IOException;
     
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
     
    public class InvertedIndexRunner {
    	public static void main(String[] args) throws IOException,
    			ClassNotFoundException, InterruptedException {
    		Configuration conf = new Configuration();
    		Job job = Job.getInstance(conf);
     
    		job.setJarByClass(InvertedIndexRunner.class);
     
    		job.setMapperClass(InvertedIndexMapper.class);
    		job.setCombinerClass(InvertedIndexCombiner.class);
    		job.setReducerClass(InvertedIndexReducer.class);
     
    		job.setOutputKeyClass(Text.class);
    		job.setOutputValueClass(Text.class);
     
    		FileInputFormat.setInputPaths(job, new Path(args[0]));
    		// 检查参数所指定的输出路径是否存在,若存在,先删除
    		Path output = new Path(args[1]);
    		FileSystem fs = FileSystem.get(conf);
    		if (fs.exists(output)) {
    			fs.delete(output, true);
    		}
    		FileOutputFormat.setOutputPath(job, output);
     
    		System.exit(job.waitForCompletion(true) ? 0 : 1);
    	}
    }
    
    打成jar包并执行:
    hadoop jar invertedindex.jar cn.nuc.hadoop.mapreduce.invertedindex.InvertedIndexRunner /user/exe_mapreduce/invertedindex/input /user/exe_mapreduce/invertedindex/output
    
    查看结果:
    [hadoop@master ~]$ hadoop fs -cat /user/exe_mapreduce/invertedindex/output/part-r-00000
    Hello	file3:1;
    MapReduce	file3:2;file1:1;file2:1;
    bye	file3:1;
    is	file1:1;file2:2;
    powerful	file2:1;
    simple	file2:1;file1:1;
    
    展开全文
  • 倒排索引

    2015-09-18 16:21:24
    倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted ...

    倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。

    概述

    在关系数据库系统里,索引是检索数据最有效率的方式,。但对于搜索引擎,它并不能满足其特殊要求:
    1)海量数据:搜索引擎面对的是海量数据,像Google,百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ,面对如此海量数据 ,使得数据库系统很难有效的管理。
    2)数据操作简单:搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、 删、 改、 查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 ,搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。

    相关概念及定义

    倒排列表

    倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词,每个文档会记录文档编号(DocID),单词在这个文档中出现的次数(TF)及单词在文档中哪些位置出现过等信息,这样与一个文档相关的信息被称做倒排索引项(Posting),包含这个单词的一系列倒排索引项形成了列表结构,这就是某个单词对应的倒排列表。右图是倒排列表的示意图,在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。
    在实际的搜索引擎系统中,并不存储倒排索引项中的实际文档编号,而是代之以文档编号差值(D-Gap)。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值,一般在索引构建过程中,可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号,所以文档编号差值总是大于0的整数。如图2所示的例子中,原始的 3个文档编号分别是187、196和199,通过编号差值计算,在实际存储的时候就转化成了:187、9、3。
    之所以要对文档编号进行差值计算,主要原因是为了更好地对数据进行压缩,原始文档编号一般都是大数值,通过差值计算,就有效地将大数值转换为了小数值,而这有助于增加数据的压缩率。

    倒排索引

    也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。
    倒排索引
    有两种不同的反向索引形式:

      • 一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。
      • 一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。
      后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。
      现代搜索引擎的索引 都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构, “倒排索引” 是实现单词到文档映射关系的最佳实现方式和最有效的索引结构.

    【转自】百度百科http://baike.baidu.com/view/676861.htm

    展开全文
  • Lucene倒排索引实现原理探秘...本文将对Lucene的倒排索引实现原理技术细节进行详细的剖析,这些内容适用于Lucene 5.x至7.x系列版本。文章整体内容组织如下: 倒排索引理论 Lucene倒排索引实现 Lucene索引文件...

    Lucene倒排索引实现原理探秘(1)

    前言

    在全文检索领域, Lucene可谓是独领风骚数十年。倒排索引构成全文检索的根基,只有深入理解了倒排索引的实现原理,才能算是入门了全文检索领域。本文将对Lucene的倒排索引的实现原理和技术细节进行详细的剖析,这些内容适用于Lucene 5.x至7.x系列版本。文章整体内容组织如下:

    1. 倒排索引理论
    2. Lucene倒排索引实现
    3. Lucene索引文件构成
    4. 什么是Terms Index?
    5. 什么是Terms Dictionary?
    6. 结束语

    理论

    在学术上,倒排索引结构非常简明易懂,如下:

    也许你已接触过倒排索引,下面这张图你或许已经看过很多次了。本文将从你熟悉的部分开始,一步步深入去挖掘这张图的一个个细节。这里先介绍两个重要概念:

    1. 索引,索引词表。倒排索引并不需要扫描整个文档集,而是对文档进行预处理,识别出文档集中每个词。

    2. 倒排表,倒排表中的每一个条目也可以包含词在文档中的位置信息(如词位置、句子、段落),这样的结构有利于实现邻近搜索。词频和权重信息,用于文档的相关性计算。

    倒排索引由两部分组成,所有独立的词列表称为索引,词对应的一系列表统称为倒排表。 —— 来自《信息检索》

    如图,整个倒排索引分两部分,左边是Term Dictionary(索引表,可简称为Dictionary),是由一系列的Terms组成的;右边为Postings List(倒排表),由所有的Term对应的Postings组成。

    实际上Lucene所用的信息信息检索方面的术语基本跟Information Retrieval(《信息检索》原版)保持一致。比如Term、Dictionary、Postings等。

    首先,有必要解释一下,每个Segment中的每个字段(Field)都有这么一个独立的结构。其次,它是不可改写的,即不能添加或更改。至于为何选择不可改写的设计,简单说有两个方面:一是更新对磁盘来说不够友好;另一方面是写性能的影响,可能会引发各种并发问题。

    我们可以用一个HashMap来简单描述这个结构:Map<String, List<Integer>>,这个Map的Key的即是Term,那它的Value即是Postings。所以它的Key的集合即是Dictionary了,这与上图的描述太贴切了。由于HashMap的Key查找还是用了HashTable,所以它还解决Dictionary的快速查找的问题,一切显得太美好了。这可以说是一个hello world版的倒排索引实现了。

    Lucene的实现

    全文搜索引擎通常是需要存储大量的文本,Postings可能会占据大量的存储空间,同样Dictionary也可能是非常大的,因此上面说的基于HashMap的实现方式几乎是不可行的。在海量数据背景下,倒排索引的实现都极其复杂,因为它直接关系到存储成本以及搜索性能。为此,Lucene引入了多种巧妙的数据结构和算法。

    Lucene索引文件构成

    我们知道Lucene将索引文件拆分为了多个文件,这里我们仅讨论倒排索引部分。Lucene把用于存储Term的索引文件叫Terms Index,它的后缀是.tip;把Postings信息分别存储在.doc.pay.pox,分别记录Postings的DocId信息和Term的词频、Payload信息、pox是记录位置信息。Terms Dictionary的文件后缀称为.tim,它是Term与Postings的关系纽带,存储了Term和其对应的Postings文件指针。

    总体来说,通过Terms Index(.tip)能够快速地在Terms Dictionary(.tim)中找到你的想要的Term,以及它对应的Postings文件指针与Term在Segment作用域上的统计信息。

    postings: 实际上Postings包含的东西并不仅仅是DocIDs(我们通常把这一个有序文档编号系列叫DocIDs),它还包括文档编号、以及词频、Term在文档中的位置信息、还有Payload数据。

    所以关于倒排索引至少涉及5类文件,本文不会全面展开。

    什么是Terms Index

    下面引用了一张来自网络上的图,非常直观:

    Terms Index即为上图中.tip部分,它实际上是由一个或多个FST组成的,Segment上每个字段都有自己的一个FST(FSTIndex)记录在.tip上,所以图中FSTIndex的个数即是Segment拥有字段的个数。另外图中为了方便我们理解把FST画成Trie结构,然后其叶子节点又指向了tim的Block的,这实际上是用了一种叫Burst-Trie的数据结构。

    Burst-Trie

    .tip看起来是像一棵Trie,所以整张图表现出来就是论文上的Burst-Trie结构了。上面一棵Trie,Trie的叶子节点是Container(即是Lucene中的Block)。下图就是Paper上描述的Burst-Trie的结构:

    来自Burst-Trie论文上的一张图

    Burst-Trie,关于Burst-Trie,网上有很多专业资料,这里只做简单介绍。Burst-Trie可以认为是Trie的一种变种,它主要是将后缀进行了压缩,降低了Trie的高度,从而获取更好查询性能。

    Lucene工程上的实现方式

    Burst-Trie在Lucene是如何应用的?

    前面提到了Lucene是采用Burst-Trie的思想,但在实现上存在一定的出入,Lucene的Burst-Trie被拆成两部分。如果一定把它们对应起来的话,我认为Burst-Trie的AccessTree的实现是FST,存在.tip文件中;Container的实现是Block,存在.tim文件里。Burst-Trie的Container内部是开放性结构,可能是Binary-Tree,可以也List。Lucene的block是数组,准确的说,就是把一系列的Block系列化写到文件上,这里好像并没有做特殊的处理。

    FST

    在Lucene,Terms Dictionary被存储在.tim文件上。当一个Segment的文档数量越来越多的时候Dictionary的词汇也会越来越多,那查询效率必然也会逐渐变低。因此需要一个很好的数据结构为Dictionary建构一个索引,将Dictionary的索引进一步压缩,这就是后来的Terms Index(.tii)。这是在早期的版本中使用的,到Lucene 4.0之后做一次重构和升级,同时改名为.tip。

    FST:Finite-State-Transducer,结构上是。我们知道把一堆字符串放一堆,把它们的共同前缀进行压缩就会变成Burst-Trie。如果把后缀变成一个一个节点,那么它就是Trie结构了。如果将后缀也进行压缩的话,那你就能发现他更变成一张图结构了。 那么我们易知FST是压缩字典树后缀的图结构,她拥有Trie高效搜索能力,同时还非常小。这样的话我们的搜索时,能把整个FST加载到内存。

    实际上,FST的结构非常复杂,我们可以简单的将其理解为一个高效的K-V结构,而且空间占用率更高。这里想简单强调一下:Lucene到底在FST里存了什么数据? 如果你已经了解FST在Lucene中充当的角色和作用的话,我想你可能会误认为FST中存了Dictionary中所有的Terms数据,这样可以通过FST是找到具体的Term的位置,或者通过FST可以切实获知一个Term是否存在。

    然而,事实并非如此。 FST即不能知道某个Term在Dictionary(.tim)文件上具体的位置,也不能仅通过FST就能确切的知道Term是否真实存在。它只能告诉你,查询的Term可能在这些Blocks上,到底存不存在FST并不能给出确切的答案,因为FST是通过Dictionary的每个Block的前缀构成,所以通过FST只可以直接找到这个Block在.tim文件上具体的File Pointer,并无法直接找到Terms。关于FST的详细细节,后面将以一篇独立的文章来讲解,这里暂时不展开过多细节。

    下面会详细的介绍Dictionary的文件结构,这里先提一下。每个Block都有前缀的,Block的每个Term实际不记录共同前缀的。只有通过Block的共同的前缀,这是整个Block的每个Term共同的,所以每个Term仅需要记录后缀可以通过计算得到,这可以减少在Block内查找Term时的字符串比较的长度。

    简单理解的话,你可以把它当成一个高级的BloomFilter,我们BloomFilter是有一定的错误率的;同时BloomFilter是通过HashCode实现的,只能用它来测试是否存在,并无法快速定位。在FST中,并无错误率且能快速定位。但是BloomFilter有更高的性能。

    说了这么多,Terms Index到底带来哪些实质性的功能呢? Terms Index是Dictionary的索引,它采用 了FST结构。上面已经提及了,FST提供两个基本功能分别是:

    1. 快速试错,即是在FST上找不到可以直接跳出不需要遍历整个Dictionary。类似于BloomFilter的作用。

    2. 快速定位Block的位置,通过FST是可以直接计算出Block的在文件中位置(offset,FP)。

    上面已经介绍了FST的一种功能,此外,FST还有别的功能,因为FST也是一个Automation(自动状态机)。这是正则表达式的一种实现方式,所以FST能提供正则表达式的能力。通过FST能够极大的提高近似查询的性能,包括通配符查询、SpanQuery、PrefixQuery等,甚至包括近期社区正在做的基于正则表达式的查询。

    什么是Terms Dictionary?

    前面我们已经介绍了Terms Dictionary的索引,Terms Index。已经频频提到的Terms Dictionary到底是什么东东?Terms Dictionary是Segment的字典,索引表。它能够让你知道你的查询的这个Term的统计信息,如tf-idfdf(doc_freq)Total Term Frequence(Term在整个Segment出现频率);还能让你知道Postings的元数据,这里是指Term的docids、tf以及offset等信息在Postings各个文件的文件指针FP。

    Block并不记录这个Block的起始和结束的范围,所以当FST最终指向多个Block时,就会退化为线性搜索。那什么时候会出现FST最终指向多个Block呢?最简单的一种情况是,超过48个的Term,且出现首字母相同的term的个数不超过25个。这种情况下由于没有每个Block都没有共同前缀,所以构建出来的FST只有一个结束节点记录每个Block的文件寻址的偏移增量。

    Lucene规定,每个Block的大小在25-48范围内

    说这么多,还是觉得太抽象了,我们来看一下.tim文件结构示意图:

    主要是大两部分信息,1. Block信息,包含所有Term的详情;2. Field的自有属性和统计信息。接下来我们将展开来介绍这两部分内容。

    Block信息 — NodeBlock

    在整个.tim文件上,我觉得比较复杂且值得拎出来讲的只有NodeBlock。那么,Block又是什么东东?它是如何被构建的?这部分代码,还是比较晦涩难懂得,我每次读时也都会产生一些新的疑问。

    我们前面所有说的Block即是NodeBlock的一个Entry。 由上图可以知道,Block中有两种OuterNode和InnerNode。这里我想引用代码上两个类名来辅助我们接下来的剖析:PendingTerm/PendingBlock,我们暂且把它们叫作待写的Term子Block的指针吧。

    NodeBlock从构建逻辑上来讲是它是树型结构,所以它由叶子节点和非叶子节点两种节点组成。叶子节点就叫OutterNode,非叶子节点就叫InnerNode。一个Block可能含有一堆的Term(PendingTerm)和PendingBlock(当它是非叶子节点时),实际上PendingBlock也是不可能出现在叶子节点上的。如果是PendingBlock,那么这个Entry只记录两个信息:后缀(这个Block的共同后缀)以及子Block的文件指针,此时就不必再记上所说的统计信息和postings信息了。

    如图所示,一个Block记录的信息非常多,首先是Block的类型和Entry的条数等元数据信息,而后是该Block拥有的所有Entry。

    这里每个Entry含有后缀、统计信息(对应为前面据说的权重,它含有ttf和df)、Postings的位置信息(这就是反复提及postings相关的文件指针,postings是拆分多文件存储的)。 关于Postings更多细节,放到下个章节来讨论。

    Field信息 — FieldMetadata

    相对来说FieldMetadata组织结构就简单多了,纯粹的线性写入即可。但Field信息记录的内容还是挺多的,包括字段本身的属性,如字段编号、Terms的个数、最大和最小的Terms;此外还记录了Segment级别的一些统计信息,包括tdf、拥有该字段的文档总数(如果文档没有该字段,或者该字段为空就不计了)。

    1. RootCode实际上指向该字段第一个Block的文件指针。

    2. LongsSize这个名字有点隐晦,它是说该字段的字段存储哪些Postings信息。因为我们是可以指定Postings存储或者不存储诸如位置信息和Payload信息的,存与不存将被表现在这里了。

    从搜索流程来看,Lucene先读到FieldMetadata的信息,然后判断Query上Terms是否落在这里字段的MinTerm和MaxTerm之间。如果不在的话,完全不需要去读NodeBlock的。MinTerm和MaxTerm可以有效的避免读取不必要的.tip文件。

    结束语

    到这里,关于倒排索引结构中第一部分内容已经介绍完了,限于篇幅的原因,还有更多有趣的小细节没有呈现出来。简单总结一下:我们先从Information Retrieve开始了解学术上倒排索引结构,接着我们又对Luecne的实现做了深入剖析。Lucene对索引词表也做了索引(叫Terms Index,文件后缀是.tip),索引词表的索引采用Finite-State Transducer这种数据结构。由于这种结构占用空间极小,所以它完成可以被加载到内存加速Terms Dictionary的查找过程。而后又介绍了Terms Dictionary,Terms Dictionary以Terms Index共同构成与Burst-Trie类似的数据结构,Terms Dictionary含两部分信息:1. NodeBlock记录Dictionary的所有Terms;2. FieldMetadata存储了FieldInfos信息和Segment的统计信息。

    关于倒排索引还有Postings List,这部分内容将在下篇文章中介绍。

     

    转载自: 

    展开全文
  • 设计合适的数据结构对影响提升至关,在特定的场景使用的合适的结构是成功的基石,Lucene采用哪些数据结构解决构建索引的性能呢?本文将带你领略Lucene数据结构之美。
  • MapReduce功能实现十---倒排索引(Inverted Index)

    千次阅读 多人点赞 2017-08-02 10:59:30
    前言:"倒排索引"是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射,即提供了一种根据内容来查找文档的方式。由于不是...
  • C风格文件、C++风格读写操作 、英文文章单词的正确分割 、基于Trie树实现文件词频统计 、基于Trie树实现倒排索引的文件词频统计
  • 广告倒排索引架构与优化

    千次阅读 2019-06-16 20:52:23
    我们的倒排索引采用的是ElasticSearch(后面简称ES),考虑点是社区活跃,相关采集、可视化、监控以及报警等组件比较完善,同时ES基于java开发,所以调优二次开发相对方便 先看下我们的倒排索引的架构图 ...
  • 使用Hadoop 实现文档倒排索引

    千次阅读 2015-04-16 16:46:14
    文档倒排索引主要是统计每个单词在各个文档中出现的频数,因此要以单词为key,value为文档以及该单词在此文档频数,即输出数据的格式形如:  :表示word1这个单词在doc1文档中出现了3次,在doc2文档中出现了4次。...
  • 倒排索引 1.1 倒排索引 "倒排索引"是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射,即提供了一种...
  • 从搜索引擎谈起 、倒排索引的基本概念 、倒排索引举例 、浅谈正排索引 、倒排索引实现
  • 算法篇--倒排索引

    2021-08-01 17:28:39
      见其名知其意,有倒排索引,对应肯定,有正向索引。正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。   在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词...
  •  学习hadoop的童鞋,倒排索引这个算法还是挺重要的。这是以后展开工作的基础。首先,我们来认识下什么是倒排索引:  倒排索引简单地就是:根据单词,返回它在哪个文件中出现过,而且频率是多少的结果。这就像百度...
  • 倒排索引1.1 倒排索引的结构1.2 倒排索引不可变的好处二. 重建索引 一. 倒排索引 1.1 倒排索引的结构 (1)包含这个关键词的document list (2)包含这个关键词的所有document的数量:IDF(inverse document ...
  • MapReduce 案例之倒排索引1. 倒排索引倒排索引是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。 它主要是用来存储某个单词(或词组) 在一个文档或一组文档中的存储位置的映射,即提供了一种根据...
  • hadoop 倒排索引

    2014-06-18 23:23:00
    6、倒排索引 "倒排索引"是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射,即提供了一种根据内容来查找文档的方式。...
  • 海量数据处理——倒排索引

    千次阅读 2016-08-10 16:11:30
    一,什么是倒排索引 问题描述:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。 基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一...
  • Hadoop案例之倒排索引

    千次阅读 2016-12-29 23:42:40
    Hadoop案例之倒排索引    "倒排索引"是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎。它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射,即提供了一种根据内容来查找...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,392
精华内容 5,356
关键字:

倒排索引程序的设计和实现