狠狠撸

狠狠撸Share a Scribd company logo

An introduction to inverted index

?Download as PPT, PDF?
?
W
weedge
1 of 26
Downloaded 29 times
An introduction to Inverted Index 倒排索引的介绍 邬 勇
引言 倒排索引 (Inverted index) ，也常被称为反向索 引、置入档案或反向档案，是一种索引方法，被用 来存储在全文搜索下某个单词在一个文档或者一组文 档中的存储位置的映射。它是文档检索系统中最常用 的数据结构。 有两种不同的反向索引形式： 文档水平 (Document-level) 反向索引（或者反向 档案索引）包含每个引用单词的文档的列表。 单词水平 (word-level) 反向索引（或者完全反向 索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的兼容性（比如短语搜 索），但是需要更多的时间和空间来创建。
主要内容 1. 倒排索引 (inverted index) 结构 2. 倒排索引构造流程 3. 倒排索引构造 (index construction) 4. 倒排索引压缩 (index compression)
1. 倒排索引 (inverted index) 结 构 ? 倒排索引由字典文件 (dictionary) 和记录文件 (postings file) 两部分组成。 ? 字典 (dictionary) 主要是由 term,termID, 包含该 term 的文 档数目 ft ，以及指向该记录表 (postings list) 的指针组成 。 dictionary: <term,termID,ft,pointer> [postings list] ? 记录 (posting) 主要是记录 term 所在的文档 (docID) ， term 在文档中出现的次数，以及在文档中的 位置，文档长度等信息。 posting: <docID, fd,t,<position1,… positionfd,t>>
1. 倒排索引 (inverted index) 结 构 下图是简单的倒排索引结构例子。 5 Dictionary Postings list Doc IDDoc ID Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 174 54101 TermTerm PointerPointer
2. 倒排索引的构造过程 Col l ect i on Par ser Modi f i ed t okens I ndexer I nver t ed I ndex 解析器。根据不同的文档采 用不同的解析器对其解析。 其中包括分词器( Tokeni zer ) 和语言模块( l i ngui st i c modul es) 如大小写折叠( case f ol di ng) 处理, ( st opper ) 停 用词处理，以及( st emmer ) 词 根化处理等. 索引器。主要是生成 ( di ct i onar y) 字典文件和 ( post i ngs f i l e) 记录文件组成 的倒排索引，其中包括( sor t ) 排 序操作。对于大规模的文档的处 理, 包括中间文件的合并( mer ge) 操作以及对字典文件和记录文件 的压缩( i ndex compr ess) 操作。
2. 倒排索引的构造过程 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Doc 1 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious Doc 2 Term Doc # I 1 did 1 enact 1 julius 1 caesar 1 I 1 was 1 killed 1 i' 1 the 1 capitol 1 brutus 1 killed 1 me 1 so 2 let 2 it 2 be 2 with 2 caesar 2 the 2 noble 2 brutus 2 hath 2 told 2 you 2 caesar 2 was 2 ambitious 2 Term Doc # ambitious 2 be 2 brutus 1 brutus 2 capitol 1 caesar 1 caesar 2 caesar 2 did 1 enact 1 hath 1 I 1 I 1 i' 1 it 2 julius 1 killed 1 killed 1 let 2 me 1 noble 2 so 2 the 1 the 2 told 2 you 2 was 1 was 2 with 2 构造无词语位置信息倒排索引的简单示例：
3. 倒排索引的构造方法 硬件基础回顾 : 2007 年系统的典型参数规格指标 （寻道时间指磁头重一个位置到另一个位置的时间。每字节传输时间指数据从外存到内存的时间比例） symbol statistic value s 平均寻道时间 5 ms = 5 x 10?3 s b 每字节传输时间 0.02 μs = 2 x10?8 s 处理器的时钟频率 109 s?1 p 低层次处理时间 0.01 μs = 10?8 s (e.g., compare & swap a word) 主要内存大小 several GB 外存空间大小 1 TB or more
3. 倒排索引的构造方法 ? 基于分块排序索引 (BSBI:Blocked sort-based Indexing) ? 一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing)
基于分块排序索引 (BSBI) 该方法主要包含以下步骤 : （ 1 ）将全部文档集合划分为若干相同大小的块，这 个块的大小一般和内存分配的大小正好相同。 （ 2 ）在内存中对每个块的所有词语号和文档号构成 的值对 (termID － docID) 进行排序。 （ 3 ）将这些排好序的中间结果存储到外存中。 （ 4 ）对全部的中间结果进行合并，生成最终的倒 排索引。 基于分块排序索引 (BSBI:Blocked sort-based Indexing)
基于分块排序索引 (BSBI:Blocked sort-based Indexing) Blocked sort-based indexing algorithm
基于分块排序索引 (BSBI:Blocked sort-based Indexing)
基于分块排序索引 (BSBI:Blocked sort-based Indexing) Merging in blocked sort-based indexing (2 个块文件（待合并的记录表（ postings list ））从外存加载到内存中。在内存中合并（合并好的记录 表）然后写回外存。为了方便理解，用词语 (term) 代替词语号（ termID ） ).
一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing) ? 基于分块排序索引方法虽然具有较好的可缩放性 (scaling properties) ，但是它要求一个数据结构存储 所有的词语和映射的词语号 (map term to termID) 。 对于大规模的文档集合而言，这个数据结构往往无 法存储在内存中。 ? 相对而言，一遍式内存排序（ Single-pass in- memory indexing ， SPIMI ）方法既有较高的可缩 放性，同时无需使用词语号，直接将每个字典数据 块信息写到外存，在开始新的字典数据块的生成。 所以，该方法可以索引任何大小规模的文档集合， 只要外存空间足够。
一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing) Merging of blocks is analogous to BSBI. Inversion of a block in single-pass in-memory indexing algorithm
一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing)
基于分块排序索引与一遍式内存排序索引比 较（ BSBI vs SPIMI ） BSBI 的时间复杂度为 O （ T×logT ），其中消 耗时间最多的是对块的排 序过程， T 是所要排序的 数量上限，也就是所有值 对的数量总和。这些时间 是基本稳定的，实际索引 的时间往往更易于受解析 文档和最终的合并过程所 影响。 SPIMI 的时间复杂度为 O(T) ， 因为没有值对的排序要求，对 于文档集的大小全部操作都是 一遍式的处理 ；直接将记录添 加到记录列表中。 该方法不去首先获取全部的词语 文档号的值对并对其排序，而把 记录列表做成动态形式，也就是 说，它的大小是可以动态调整的 ，并可以直接收集词语的记录信 息。这样做有两个优点： 一是由于没有额外的排序，所以 速度很快； 二是直接利用词语来得到相应的 记录信息，无需使用词语号。所 以该方法一次处理的数据块所包 含的信息更多，相应的索引构造 效率也就更高。
基于分块排序索引 (BSBI) 方法中各模 块处理时间
一遍式内存排序索引 (SPIMI) 方法中各 模块处理时间
相关资料： 1. Efficient Single-Pass Index Construction for Text Databases Steen Heinz ， Justin Zobel ， 2003 。 2. Chapter 5 of 《 Managing Gigabytes: Compressing and Indexing Documents and Images 》 2nd Morgan Kaufmann, San Francisco, California ， 1999 。
分布式索引 (Distributed indexing) ? 主要介绍分布式构造索引的过程，以及 Map- Reduce 方法。这部分由梁竹介绍。
动态索引 (Dynamic indexing) ? 主要介绍在动态变化的文档集情况下，如何构 造动态索引。这部分由蒋仁祥介绍。
4. 索引的压缩 分为字典压缩 (Dictionary Compress) 和记 录压缩 (Posting Compress) 。以及 Heaps’ law 和 Zipf’s law 。
字典压缩 (Dictionary Compress) 主要介绍 Heaps’ law 以及几种字典压缩的 编码方法。这部分由何泉昊介绍。
记录压缩 (Posting Compress) 主要介绍 Zipf’s law 以及几种记录压缩的编 码方法。这部分由刘影介绍。
Thank you!

More Related Content

An introduction to inverted index

  • 1. An introduction to Inverted Index 倒排索引的介绍 邬 勇
  • 2. 引言 倒排索引 (Inverted index) ，也常被称为反向索 引、置入档案或反向档案，是一种索引方法，被用 来存储在全文搜索下某个单词在一个文档或者一组文 档中的存储位置的映射。它是文档检索系统中最常用 的数据结构。 有两种不同的反向索引形式： 文档水平 (Document-level) 反向索引（或者反向 档案索引）包含每个引用单词的文档的列表。 单词水平 (word-level) 反向索引（或者完全反向 索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的兼容性（比如短语搜 索），但是需要更多的时间和空间来创建。
  • 3. 主要内容 1. 倒排索引 (inverted index) 结构 2. 倒排索引构造流程 3. 倒排索引构造 (index construction) 4. 倒排索引压缩 (index compression)
  • 4. 1. 倒排索引 (inverted index) 结 构 ? 倒排索引由字典文件 (dictionary) 和记录文件 (postings file) 两部分组成。 ? 字典 (dictionary) 主要是由 term,termID, 包含该 term 的文 档数目 ft ，以及指向该记录表 (postings list) 的指针组成 。 dictionary: <term,termID,ft,pointer> [postings list] ? 记录 (posting) 主要是记录 term 所在的文档 (docID) ， term 在文档中出现的次数，以及在文档中的 位置，文档长度等信息。 posting: <docID, fd,t,<position1,… positionfd,t>>
  • 5. 1. 倒排索引 (inverted index) 结 构 下图是简单的倒排索引结构例子。 5 Dictionary Postings list Doc IDDoc ID Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 174 54101 TermTerm PointerPointer
  • 6. 2. 倒排索引的构造过程 Col l ect i on Par ser Modi f i ed t okens I ndexer I nver t ed I ndex 解析器。根据不同的文档采 用不同的解析器对其解析。 其中包括分词器( Tokeni zer ) 和语言模块( l i ngui st i c modul es) 如大小写折叠( case f ol di ng) 处理, ( st opper ) 停 用词处理，以及( st emmer ) 词 根化处理等. 索引器。主要是生成 ( di ct i onar y) 字典文件和 ( post i ngs f i l e) 记录文件组成 的倒排索引，其中包括( sor t ) 排 序操作。对于大规模的文档的处 理, 包括中间文件的合并( mer ge) 操作以及对字典文件和记录文件 的压缩( i ndex compr ess) 操作。
  • 7. 2. 倒排索引的构造过程 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Doc 1 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious Doc 2 Term Doc # I 1 did 1 enact 1 julius 1 caesar 1 I 1 was 1 killed 1 i' 1 the 1 capitol 1 brutus 1 killed 1 me 1 so 2 let 2 it 2 be 2 with 2 caesar 2 the 2 noble 2 brutus 2 hath 2 told 2 you 2 caesar 2 was 2 ambitious 2 Term Doc # ambitious 2 be 2 brutus 1 brutus 2 capitol 1 caesar 1 caesar 2 caesar 2 did 1 enact 1 hath 1 I 1 I 1 i' 1 it 2 julius 1 killed 1 killed 1 let 2 me 1 noble 2 so 2 the 1 the 2 told 2 you 2 was 1 was 2 with 2 构造无词语位置信息倒排索引的简单示例：
  • 8. 3. 倒排索引的构造方法 硬件基础回顾 : 2007 年系统的典型参数规格指标 （寻道时间指磁头重一个位置到另一个位置的时间。每字节传输时间指数据从外存到内存的时间比例） symbol statistic value s 平均寻道时间 5 ms = 5 x 10?3 s b 每字节传输时间 0.02 μs = 2 x10?8 s 处理器的时钟频率 109 s?1 p 低层次处理时间 0.01 μs = 10?8 s (e.g., compare & swap a word) 主要内存大小 several GB 外存空间大小 1 TB or more
  • 9. 3. 倒排索引的构造方法 ? 基于分块排序索引 (BSBI:Blocked sort-based Indexing) ? 一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing)
  • 10. 基于分块排序索引 (BSBI) 该方法主要包含以下步骤 : （ 1 ）将全部文档集合划分为若干相同大小的块，这 个块的大小一般和内存分配的大小正好相同。 （ 2 ）在内存中对每个块的所有词语号和文档号构成 的值对 (termID － docID) 进行排序。 （ 3 ）将这些排好序的中间结果存储到外存中。 （ 4 ）对全部的中间结果进行合并，生成最终的倒 排索引。 基于分块排序索引 (BSBI:Blocked sort-based Indexing)
  • 13. 基于分块排序索引 (BSBI:Blocked sort-based Indexing) Merging in blocked sort-based indexing (2 个块文件（待合并的记录表（ postings list ））从外存加载到内存中。在内存中合并（合并好的记录 表）然后写回外存。为了方便理解，用词语 (term) 代替词语号（ termID ） ).
  • 14. 一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing) ? 基于分块排序索引方法虽然具有较好的可缩放性 (scaling properties) ，但是它要求一个数据结构存储 所有的词语和映射的词语号 (map term to termID) 。 对于大规模的文档集合而言，这个数据结构往往无 法存储在内存中。 ? 相对而言，一遍式内存排序（ Single-pass in- memory indexing ， SPIMI ）方法既有较高的可缩 放性，同时无需使用词语号，直接将每个字典数据 块信息写到外存，在开始新的字典数据块的生成。 所以，该方法可以索引任何大小规模的文档集合， 只要外存空间足够。
  • 15. 一遍式内存排序索引 (SPIMI: Single-pass in-memory indexing) Merging of blocks is analogous to BSBI. Inversion of a block in single-pass in-memory indexing algorithm
  • 17. 基于分块排序索引与一遍式内存排序索引比 较（ BSBI vs SPIMI ） BSBI 的时间复杂度为 O （ T×logT ），其中消 耗时间最多的是对块的排 序过程， T 是所要排序的 数量上限，也就是所有值 对的数量总和。这些时间 是基本稳定的，实际索引 的时间往往更易于受解析 文档和最终的合并过程所 影响。 SPIMI 的时间复杂度为 O(T) ， 因为没有值对的排序要求，对 于文档集的大小全部操作都是 一遍式的处理 ；直接将记录添 加到记录列表中。 该方法不去首先获取全部的词语 文档号的值对并对其排序，而把 记录列表做成动态形式，也就是 说，它的大小是可以动态调整的 ，并可以直接收集词语的记录信 息。这样做有两个优点： 一是由于没有额外的排序，所以 速度很快； 二是直接利用词语来得到相应的 记录信息，无需使用词语号。所 以该方法一次处理的数据块所包 含的信息更多，相应的索引构造 效率也就更高。
  • 20. 相关资料： 1. Efficient Single-Pass Index Construction for Text Databases Steen Heinz ， Justin Zobel ， 2003 。 2. Chapter 5 of 《 Managing Gigabytes: Compressing and Indexing Documents and Images 》 2nd Morgan Kaufmann, San Francisco, California ， 1999 。
  • 23. 4. 索引的压缩 分为字典压缩 (Dictionary Compress) 和记 录压缩 (Posting Compress) 。以及 Heaps’ law 和 Zipf’s law 。
  • 24. 字典压缩 (Dictionary Compress) 主要介绍 Heaps’ law 以及几种字典压缩的 编码方法。这部分由何泉昊介绍。
  • 25. 记录压缩 (Posting Compress) 主要介绍 Zipf’s law 以及几种记录压缩的编 码方法。这部分由刘影介绍。

Editor's Notes

  • #5: 字典（dictionary)常用的数据结构：hash 和 B-tree。 记录表（posting list)的数据结构：动态数组（Dynamically resizable arrays）和链表（linked lists),需要额外的指针空间。 记录文件根据不同的文档类型解析（parser)得到的不同记录，取决于信息检索的方式。这里主要是针对简单的文本的信息记录。如果对网页的检索，则记录（posting)中包括该网页的超链接以及其它的东东。 记录（posting)中加入位置信息，主要是按其中的位置数据来验证term之间的短语关系。
  • #7: Token: an instance of a sequence of characters, Each such token is now a candidate for an index entry, after further processing Term: a (normalized) word type, which is an entry in our IR system dictionary
  • #8: 构建无词语位置信息索引（文档水平(Document-level index)反向索引）的方法，该方法首先遍历全部文档，构造全部的词语文档对（term－docID），然后再以词语为主键、文档号为辅键，对词语文档对进行排序，最后利用文档号对每个词语构建相关的记录表（postings list），同时还要计算词语频率和文档频率等统计指标值。对于小规模的数据而言，这些操作都可以在内存中直接进行。但是对于大规模的数据而言，就必须要使用外存。
  • #9: （1）对内存的访问速度快于对外存的访问速度。读取内存一个字节只需几个时钟周期（约5 × 10-9秒），但是读取外存一个字节却需要更长的时间（约2 × 10-8秒）。所以，一般情况下，我们应当尽可能的在内存存储所有数据，特别对于那些需要频繁访问的数据，它们相应的存储空间被称为缓存（cache）。 （2）当进行外存读写时，磁盘磁头定位到相关数据存储地方也需要一定的时间，被称为寻道时间（seek time），对于典型的硬盘而言，平均为5毫秒。在寻道期间，没法传输任何数据。为了使得传输速度最大化，需要被连续读取的数据一般要连续存储在外存上。按照上述硬件标准，假设要传输外存的10M数据到内存，如果这些数据都连续存储在一个数据单元（chunk）中，则需要时间要少于0.2秒，但是如果这些数据被分开存放在不连续的100个数据单元中，由于需要频繁移动磁头近100次，所以需要的时间可达到0.2＋100×（5×10－3）＝0.7秒。 （3）操作系统一般以数据块（block）为单位来读写外存，所以读取1个字节和读取整个数据块所花费的时间差不多是一样的。数据块的大小一般为8KB，16KB，32KB和64KB等。通常把即将读写近外存的内存数据单元称为数据缓冲（buffer）。 （4）外存和内存之间的数据传输一般是利用系统总线来进行的，而非处理器。这就意味着在进行IO操作时处理器完全可以用于对其他数据的处理工作。有效利用这种特征可以加快读写外存数据的速度，如对这些数据启用压缩。在使用一种高效解压算法的时候，读取和解压这些数据的总时间要少于读取未压缩数据的总时间。 （5）信息检索系统所在的服务器一般都有几个GB大小的内存。可用的外存空间更高个级别。
  • #10: Sort-based indexing Na?ve in-memory inversion Blocked Sort-Based Indexing Merge sort is effective for disk-based sorting (avoid seeks!) Single-Pass In-Memory Indexing No global dictionary Generate separate dictionary for each block Don’t sort postings Accumulate postings in postings lists as they occur Distributed indexing using MapReduce Dynamic indexing: Multiple indices, logarithmic merge
  • #11: 对于大型文件，由于内存的限制，需要对文档集collection进行分块(block)处理。 为了使得构建索引更为高效(便于字典压缩dictionary compress)，需要使用词语号（termID）代替词语（term）来作为区分不同词语的唯一标记符 排序有利于压缩compress，以及中间文件的合并merge。
  • #12: ParseNextBlock函数：在内存把文档解析成词语号和文档号值对（termID-docID），累计这些值对直到固定大小的块满了为止。 BSBI-Invert函数：首先，对词语号和文档号值对（termID-docID）排序，然后，收集具有相同词语号（termID）的值对到对应的记录表（postings list）中，这里这些记录表（postings list）是由简单的文档号（docID）表示 。 WriteBlockToDisk函数：把一个倒排好的索引结果最后写入外存中 。 MergeBlocks函数：全部的块文件同时合并，对10个块文件读需要一些小的读缓冲区和对于最终合并好的索引写入外存需要一个写缓存区。
  • #14: (2个块文件（待合并的记录表（postings list））从外存加载到内存中。在内存中合并（合并好的记录表）然后写回外存。为了方便理解，用词语(term)代替词语号（termID）). 图中用di来表示第i个文档。全部的块文件同时合并，对10个块文件读需要一些小的读缓冲区和对于最终合并好的索引写入外存需要一个写缓存区。在每次迭代中，选择最小的词语号（termID），这些词语号没有被处理以及没有使用优先队列或类似的数据结构。词语号（termID）所对应的全部的记录表（postings list）被读取和合并。合并好的记录表写回外存中。必要时每一个读缓存区被文件所重新填满。 But it is more efficient to do a n-way merge, where you are reading from all blocks simultaneously Providing you read decent-sized chunks of each block into memory and then write out a decent-sized output chunk, then you’re not killed by disk seeks
  • #16: 该方法首先解析文档，得到词语文档号的值对（term－docID pairs）序列，SPIMI方法会反复不断的对整个序列进行操作，直至处理完全部集合。 每一次调用函数SPIMI-INVERT期间，词语文档号的值对（这里用token表示）是一个接着一个被处理(4行)。 当这个词语(term)是首次出现，则将其添加进字典(dictionary)中，采用哈希(hash)的方式存储，并生成新的记录列表(postings list)（6行）。 如果不是首次出现，则返回已有词语对应的记录列表（7行）。 由于一开始不可能知道一个词语所对应的记录列表有多长，所以首次分配的空间不会很大，一旦塞满就扩展成原先的二倍（8-9行） 直接将记录添加到记录列表中（10行） 需要按照词语进行排序，以便于以后的合并操作（11行）。否则，以后的合并操作就不可能一次遍历即可做完。 一旦内存塞满，将需要将已经得到的字典及其记录信息全部写回外存（12行）。 每一次调用SPIMI方法都会向外存写回一个数据块，所以SPIMI方法的最后一步就是合并所有的数据块形成最终的倒排索引，这和BSBI一样
  • #18: SPIMI与BSBI的方法有一个明显的区别，那就是该方法直接将记录添加到记录列表中（10行）。该方法首先不去获取全部的词语文档号的值对并对其排序，而把记录列表做成动态形式，也就是说，它的大小是可以动态调整的，并可以直接收集词语的记录信息。这样做有两个优点： 一是由于没有额外的排序，所以速度很快； 二是直接利用词语来得到相应的记录信息，无需使用词语号。所以该方法一次处理的数据块所包含的信息更多，相应的索引构造效率也就更高。