现代信息检索 Modern Information Retrieval

Presentation on theme: "现代信息检索 Modern Information Retrieval"— Presentation transcript:

1 现代信息检索 Modern Information Retrieval
第五章　文本处理与索引 (Text Processing & Index Construction) based on the lectures of Manning and Raghavan, Jian-Yun Nie, 王斌等)

2 About text operations 不论是文档还是查询，都要变成index term的某种形式(布尔表达式、向量、概率、统计语言模型参数) 选择什么作为index term? 如何构建索引？

3 主要内容 文档预处理 索引构建 词法分析 停用词消除 (stop list) 词干还原(morphological stemming)
Term选择 statistics (counting words) part-of-speech tagging compound splitting partial parsing: noun phrase extraction other: use of thesaurus, named entity recognition, ... 索引构建

4 主要内容 文档预处理 词法分析 停用词消除 词干还原 Term选择 索引构建

5 词法分析(Lexical Analysis)
将文档的字符串序列变成词序列 英文词法分析：书写时英文词之间通常通过空格或者标点进行区分，因此从英文字符串变成英文词是相对比较容易的。 中文词法分析：书写时通常没有空格，需要分词。

6 英文词法分析(1) 数字的考虑： 某人想查询1978到1989年间车祸的死亡人数，可能查出来的结果有很多这两年本身的死亡人数，因此，上面的查询中，数字不是一个很好的index term。 但是，一些和字符组合的数字，如“510B.C”，还有一些长数字，如身份证号、手机号、错误代码，可能是非常好的index term。（一种思路是n-grams） 最简单的做法就是所有数字都去掉，复杂的方法需要引入规则来分析，包括对时间的识别和归一化，如：October 1978，Oct. 1978都要归一化成某个统一表示。

7 英文词法分析(2) 对连字号的考虑： 有些词不易分开： 进行词法分析时需要考虑引入一些规则方法
有些连字号中的词可以分开，如state-of-the-art变成state of the art 有些连字号中的词不宜分开，如B-49(一款分机型号) 有些词不易分开： 如：San Francisco 进行词法分析时需要考虑引入一些规则方法

8 英文词法分析(3) 英文句点的考虑： 对大小写的考虑： 通常的情况下可以去掉
但是当句点是词的一部分的时候，需要保留，如：510B.C 和x.name 对大小写的考虑： 通常情况下，不考虑大小写，词法分析程序会将所有字母全部变成大写或者小写。 但是，某些情况下，同一个单词的大小写含义不一样，如: China和china

9 中文词法分析(1) 中文分词是很多中文文本处理的第一步 分词方法 我国科学家近日研制出一套水下反恐监控系统
我国　科学家　近日　研制　出　一　套　水下　反恐　监控　系统 分词方法 基于词典的方法：给出一部词典，根据这部词典进行匹配 无词典的方法：不需要词典，根据某种人工构词规则或者统计规则从字生成词。 ＊参考：GB-T (信息处理用分词规范)

10 中文词法分析(2) 正向最大匹配(基于词典的方法)(与之相对的还有逆向最大匹配）

11 中文词法分析(3) 分词中遇到的两大难题： 未登录词问题(Out of Vocabulary,OOV)：出现词典中没有的词，如：人名、地名、机构名、一些新词等等 歧义问题(Ambiguition)：同一句子有多种可能的分词结果 交叉性歧义：我们小组合成氢气􀃎我们/小组/合成/氢气或我们/小/组合/成/氢气 组合性歧义：他/从/马/上/下/来；我/马上/就/来/了

12 中文词法分析(4) 解决歧义和未登录词识别的基本方法: 分词对于中文信息检索而言不是绝对重要的，2-gram字符索引在中文中效果就比较好。
规则方法：分词过程中或者分词结束后根据规则进行处理； 统计方法：分词过程中或者分词结束后根据统计训练信息进行处理。 规则+统计 分词对于中文信息检索而言不是绝对重要的，2-gram字符索引在中文中效果就比较好。

13 中英文词法分析 词性标注(part-of-speech tagging) 通常的方法：
They/pron are/prep boys/noun and/conj girls/noun. 通常的方法： 规则方法：普通规则方法，基于错误转换驱动的方法 统计方法：HMM 规则+统计

14 主要内容 文档预处理 词法分析 停用词消除 词干还原 Term选择 索引构建

15 停用词消除(1) 停用词(stop words) ：那些在文档中出现过于频繁(如超过80%以上的文档均出现该词)而对于检索没有区分意义的词，常见的停用词包括冠词、介词、连词 优点：停用词消除可以减少term的个数，降低存储空间 缺点：有时消除的停用词对检索是有意义的，如：“的士”中的“的”“to be or not to be”，因此有些搜索引擎直接采用全文索引(full index)

16 停用词消除(2) 消除方法： 查表法：建立一个停用词表，通过查表的方式去掉停用词
基于DF的方法：统计每个词的DF，如果超过总文档数目的某个百分比(如80%)，则作为停用词去掉。

17

18 主要内容 文档预处理 词法分析 停用词消除 词干还原 Term选择 索引构建

19 英文词干还原(1) 很多英文词源于同一词根，但是在文章中出出现多种形式，名词单复数、动词时态、形容词和副词的比较级与最高级等等。
词干还原就是将来自同一词根的不同词还原成词根 faces  face connection  connect

20 英文词干还原(2) Porter 算法(由Martin Porter创建)—使用一系列后缀变换规则(rewrite rules)对单词进行变换 ed null ing  null ational  ate tional  tion pakken, pakt, pakte, gepakt → pak 不能正确处理不规则动词 Other stemmers exist, e.g., Lovins stemmer dictionaries (usually only inflection) paarden → paren Verb+3p+past+plural | paard Noun+plural Snowball: 支持十多种欧洲语言的词干提取器(由Martin Porter创建)

21 Porter algorithm (Porter, M. F
Porter algorithm (Porter, M.F., 1980, An algorithm for suffix stripping, Program, 14(3) : ) Step 1: plurals and past participles SSES -> SS caresses -> caress (*v*) ING -> motoring -> motor Step 2: adj->n, n->v, n->adj, … (m>0) OUSNESS -> OUS callousness -> callous (m>0) ATIONAL -> ATE relational -> relate Step 3: (m>0) ICATE -> IC triplicate -> triplic Step 4: (m>1) AL -> revival -> reviv (m>1) ANCE -> allowance -> allow Step 5: (m>1) E -> probate -> probat (m > 1 and *d and *L) -> single letter controll -> control

22 英文词干还原(3) Hull(1996)证明了词干提取能显著提高检索的有效性。但，他警告说，过度的词干提取在显著提高平均有效性并大大提高少数查询的性能的同时，会降低其它多数查询的性能。

23 中文重叠词还原(1) 汉语的某些形容词有重叠式用法。这些重叠式用法是词典里所没有的，所以必须通过还原算法从重叠式用法变回到基本形式上
也可以看成是一种“词干”还原

24 中文重叠词还原(2) 双字形容词的重叠用法共有三种：ABAB式，AABB式、A里AB式。请看下表示例：

25 中文重叠词还原(3) 单字形容词的重叠用法共有两种：ABB式和ABCD式。请看示例：

26 Normalization Need to “normalize” terms in indexed text as well as query terms into the same form We want to match U.S.A. and USA 7月30日 vs. 7/30 We most commonly implicitly define equivalence classes of terms e.g., by deleting periods in a term Alternative is to do asymmetric expansion: Enter: window Search: window, windows Enter: windows Search: Windows, windows Enter: Windows Search: Windows Potentially more powerful, but less efficient

27 Do stemming and other normalizations help?
Often very mixed results: really help recall for some queries but harm precision on others

28 主要内容 文档预处理 词法分析 停用词消除 词干还原 Term选择 索引构建

29 Document indexing Goal = Find the important meanings and create an internal representation Factors to consider: Accuracy to represent meanings (semantics) Exhaustiveness (cover all the contents) Facility for computer to manipulate What is the best representation of contents? Char. string (char trigrams): not precise enough Word: good coverage, not precise Phrase: poor coverage, more precise Concept: poor coverage, precise Accuracy (Precision) Coverage (Recall) String Word Phrase Concept

30 Keyword selection and weighting
How to select important keywords? Simple method: using middle-frequency words

31 Index term的选择 选择更有意义的词或者概念来表示文档 方法一：选择名词
方法二：选择名词和名词短语(computer science) 方法三：选择一组组的名词(每个组内的名词比较相似，一个组可以称为一个概念)

32 主要内容 文档预处理 词法分析 停用词消除 词干还原 Term选择 索引构建

33 Document Representation
Bag of words model Document-term incidence matrix （关联矩阵） 中国 文化 日本 留学生 教育 北京 … D1 1 D2 D3 D4 D5 D6 1 if page contains word, 0 otherwise incidence matrix 关联矩阵

34 Incidence Vector Transpose the Document-term incidence matrix D1 D2 D3
We get term-document incidence matrix we have a 0/1 vector for each term, incidence vector D1 D2 D3 D4 D5 D6 … 中国 1 文化 日本 留学生 教育 北京

35 Retrieval Search inside this news site for articles talks about Culture between China and Japan, and doesn’t talk about students abroad. To answer query: take the vectors for “中国” ,“文化”,“日本” , “留学生”(complemented) bitwise AND AND AND AND (不含留学生) =

36 Boolean queries: Exact match
Queries using AND, OR and NOT together with query terms Views each document as a set of words Is precise: document matches condition or not. Primary commercial retrieval tool for 3 decades. Professional searchers (e.g., Lawyers) still like Boolean queries: You know exactly what you’re getting.

37 Example: WestLaw http://www.westlaw.com/
Largest commercial (paying subscribers) legal search service (started 1975; ranking added 1992)，About 7 terabytes of data; 700,000 users Majority of users still use boolean queries Example query: What is the statute of limitations in cases involving the federal tort claims act? LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM Long, precise queries; proximity operators; incrementally developed; not like web search & is AND and /s, /p, and /k ask for matches in the same sentence, same paragraph or within k words respectively. Double quotes give a phrase search (consecutive words);

38 Beyond Boolean term search
What about phrases? Find “Bill Gates” , not “Bill and Gates” Proximity : Find Gates NEAR Microsoft. Zones in documents: Find documents with (author = Ullman) AND (text contains automata). Solution： Need capture field property of terms Need index to capture position information in docs.

39 Let’s build a search system!
Consider N = 1million documents, each with about 1K terms. Avg 6 bytes/term include spaces/punctuation 6GB of data in the documents. Say there are M = 500K distinct terms among these.

40 Can’t build the matrix 500K x 1M matrix has half-a-trillion 0’s and 1’s. But it has no more than one billion 1’s. matrix is extremely sparse. What’s a better representation? We only record the 1 positions. Why?

41 Goals of Index Recognize the contents of a document
What are the main topics of the document? What are the basic units (indexing units) to represent them? How to weight their importance? Support fast search given a query Given a query, find the documents that contain the words.

42 Goals of Index A computer cannot (yet) understand meaning as a human being, but can quickly process symbols (strings, words, …). Indexing process: Let a computer “read” a text Select the symbols to represent what it believes to be important Create a representation (index) in order to support fast search

43 Inverted index construction
Documents to be indexed. Friends, Romans, countrymen. Tokenizer Token stream. Friends Romans Countrymen Linguistic modules Modified tokens. friend roman countryman How to build inverted index, 1M*1K terms document collection, There are 1G postings, can’t do it in memory. 讨论 Indexer Inverted index. friend roman countryman 2 4 13 16 1

44 Inverted index For each term T: store a list of all documents that contain T. Do we use an array or a list for this? 中国 文化 留学生 1 2 3 5 8 13 21 34 4 16 32 64 128 What happens if the word 中国 is added to document 14?

45 Query processing How do we process a Boolean query?
Consider processing the query: 中国 AND 文化 Locate 中国 in the Dictionary; Retrieve its postings. Locate 文化 in the Dictionary; “Merge” the two postings: 128 34 2 4 8 16 32 64 1 3 5 13 21 中国 文化

46 Boolean queries: Exact match
Boolean Queries are queries using AND, OR and NOT together with query terms Views each document as a set of words Is precise: document matches condition or not. Primary commercial retrieval tool for 3 decades. Professional searchers (e.g., lawyers) still like Boolean queries: You know exactly what you’re getting.

47 The merge Walk through the two postings simultaneously, in time linear in the total number of postings entries 34 128 2 4 8 16 32 64 1 3 5 13 21 2 4 8 16 32 64 中国 文化 2 8 1 2 3 5 8 13 21 34 If the list lengths are x and y, the merge takes O(x+y) operations. Crucial: postings sorted by docID. Can we do better? Yes, if index isn’t changing too fast.

48

49

50

51 Inverted index Linked lists generally preferred to arrays
Dynamic space allocation Insertion of terms into documents easy Space overhead of pointers 中国 文化 留学生 2 4 8 16 32 64 128 3 5 13 21 34 1 Dictionary Postings Sorted by docID (more later on why).

52 位置索引 Is a document contain “to be or not to be”?
1: 7, 18, 33, 72, 86, 231; 2: 3, 149; 4: 17, 191, 291, 430, 434; 5: 363, 367, …> Merge their doc:position lists to enumerate all positions with “to be or not to be”. to: 2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ... be: 1:17,19; 4:17,191,291,430,434; 5:14,19,101; ...

53 Rules of thumb A positional index is 2-4 as large as a non-positional index Positional index size 35-50% of volume of original text Caveat: all of this holds for “English-like” languages

54 在单个文本上的索引(位置索引) 莎士比亚戏剧集上的一个索引 … first witch witcing …
2205,2268,…, ,… ,… 1598, 27555, …, , , , ,… 265197

55 在单个文本上的索引 几个函数 First(t) 返回t在文档集中出现第一次出现的位置 Last (t)返回t在文档集中出现最后一次出现的位置
Next (t,current)返回在位置current后，t第一次出现的位置 Prev(t,current)返回在位置current 前 ，t最后一次出现的位置

56 在单个文本上的索引 词组查找算法 复杂度：O(n.l)次调用next, prev Nextphrase(t1t2…tn, position)
vposition For i1 to n do vnext(ti,v) If v= then return[, ] uv For in-1 down to 1 do uprev(ti,u) If v-u = n-1 then return [u,v] Else return nextphrase(t1t2…tn, u) 复杂度：O(n.l)次调用next, prev l=min(lti), 1=<i=<n 当词组中同时包含非频繁词项时，性能很好；当词组中各词项频率相近时，反复二分查找非常耗时，此时可顺序访问各词项位置信息列表数组并进行比较。

57 在单个文本上的索引 例：查“first witch”
… first witch witcing … 2205,2268,…, ,… ,… 1598, 27555, …, , , , ,… 265197 例：查“first witch” 先“顺序”定位到词组的最后一个词的位置，再“倒序”回来找第一个词的位置，如果两词长度与位置差符合，则找到. Nextphrase(“first”,”witch”, 1) v=1, v=2205，v= (1-3行) u = 27555,u=2268 (5-7行) Nextphrase(“first”,”witch”, 2268) Nextphrase(“first”,”witch”, 2268) v=2268, v=745406，v=745407 u = ,u= return [745406, ]

58 在单个文本上的索引 算法的自适应性(adaptive)
例：在“hello…hello…hello…hello…hello world …world… world… world…world”中搜索”hello world”, 上述算法只要4次调用 prev 或 next

59 在单个文本上的索引 Next(t,current) 二分法 线性扫描法(记录上次用该方法返回的结果，本次扫描时可从上次的结果开始)
跳跃式搜索：结合上面两种方法，先定位到上次的结果，再在该位置之后以指数级增加步长(“跳跃”)向前扫描，起到跳过答案，此时两步构成的区间就是答案可能的位置，再用二分法查找。

60 Indexer steps（基于排序的索引构建）
Sequence of (Modified token, Document ID) pairs. Doc 1 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Doc 2 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious

61 Core indexing step Sort by terms.

62 Multiple term entries in a single document are merged.
Frequency information is added.

63 The result is split into a Dictionary file and a Postings file.
Why split?

64 刘奕群等《搜索引擎技术基础》

65 基于排序的索引构建 Step1:从文件读入词条后，以（termID,position)对其记录，排序并写入磁盘（指定内存用完后）。
《信息检索-实现和评价搜索引擎》

66 基于合并的索引 一开始建立一个常驻内在索引，一旦内存不足，就将常驻内存索引数据传输到磁盘，建立一个磁盘的倒排文档，并删除内存中的索引。重复执行起到索引构建完毕 对上面得到的倒排文档集进行合并成为最终索引。

67 索引的内容 模式依赖索引：支持面向文档检索的结构优化后的索引
文档编号索引 词频索引 位置索引 模式独立索引：没有优化的索引。允许在查询阶段才指定文档的定义(但需要额外的时间)

68 Index size Stemming/case folding cut number of terms by ~40% number of pointers by 10-20% total space by ~30% Stop words Rule of 30: ~30 words account for ~30% of all term occurrences in written text Eliminating 150 commonest terms from indexing will cut almost 25% of space

69 词典(dictionary) 相对于整个索引所占空间比较小(根据齐夫定律Zipf’s Law，文档集越大，词典相对于索引所占的比率越小)。通常，词典完全存储在内存中 基于排序的词典 每个数组记录大小一致，方可用二分查找 GOV2中最长字符串(词项)有74147字节。如果为每个词项分配20个字节，仍然很浪费。 采用一个主词典数组，存放32指针，指向辅数组；一个辅数组，存放实际的词典记录(元素非定长)。 基于哈希的词典 长度要合适。通常比基于排序的词典快两部以上。 不能有效地支持前辍查询，如“inform*”

70 Fixed-width terms are wasteful
Most of the bytes in the Term column are wasted – we allot 20 bytes for 1 letter terms. And still can’t handle supercalifragilisticexpialidocious. Written English averages ~4.5 characters. Exercise: Why is/isn’t this the number to use for estimating the dictionary size? Short words dominate token counts

71

72 词典(dictionary) 索引建立阶段使用基于哈希的词典，索引建立后创建基于排序的词典。 建立索引阶段使用的哈希
C++标准模板库STL中的map或hash_map (将新数据插入到链表头，效果不佳） 对于冲突通过链表解决：频繁词应靠近链表的开头。 向后插入启发式方法(insert-at-back heuristic):如果一个词是频繁的，它在输入的词条流中出现会比较靠前。 前移启发式方法(move-to-front heuristic)：一次查找中，如果链表头部没有该词，将该词放在链表头。

73 位置信息列表(posting list) 存放在磁盘，每个词项的位置信息(文档编号、词频、在文档中的位置 列表等)列表都应该存储在磁盘的连续空间中。 随机列表访问：单项索引(per-term index) Next (t,current)，perv(t,current) 可用二分法。但磁盘并不是专门用于随机访问的设备，磁盘寻道是非常耗时的操作(当一个位置列表比较大时)。 每个列表都使用一个辅助数据结构，称为单项索引，该数据结构包含了列表中位置信息子集的一个副本。如，每5000个位置信息的一个副本，相当于二级索引。 查询时，先将T的单项索引调入内存，通过副本定位到可能的区域，再将相应区域调入内存，再在这些位置信息上进行随机访问。 独立的位置索引 以文档为中心的位置索引时，通常将索引分成两个独立的倒排索引文件：一个保存文档编号和词频，一个保存词项在文档中出现的具体位置。

74 交错词典和位置信息列表 词典可能无法全部存放在内存中
交错词典：所有记录都存储于磁盘上，每个记录入口恰好仅位于对应位置信息列表之前(即词典和位置混在一起)，这样可以一次顺序读操作将词典记录和位置列表信息取出。同时，将一些词典记录(不是所有)在内存中。找某个词项位置信息时，先在内存词典记录的有序列表上进行二分查找，然后 在得到的两个记录之间进行一次顺序描述(将磁盘上的位置信息读入内存) Shadow Shakespeare Shaking Shall shakespeare <56057,…> shakespearean <55944，…> … shaking <3032,…> 词典记录 位置信息列表

75 索引压缩 典型的英文文档集中，大约每6个字节的文本就有一个词条（包括标点和空格）。如果位置信息以64位整数存储，则每6个字节的文本就需要8个字节的位置信息。位置索引耗费的空间是原文本数据的130%－140% 压缩的目的 减少存储空间 减少查询阶段的磁盘IO开销 直观的方法：对于n个词条的原始文档集，用log2(n)对位置编码。但这还不够！

76 词典压缩 给出现概率大的词条更短的编码： 词典分组
哈夫曼编码：每个词条用整数位编码。压缩率接近最优，操作起来比算术编码更高效。（英文文档的0阶熵大概是每字符5位） 算术编码：多个符号（词条）一起编码，每个词条的编码倍数不一定是整数 gzip (Ziv和Lempel,1977) bzip (Burrows和Wheeler,1994)：更高的压缩率。英文文档的熵每字符1~1.5位 词典分组 对于基于排序的词典，为每个词项单独分配一个指针浪费空间，可以将词项分组，只为每组中的第一个词项（组头）维护一个指针。组头用二分查找，组内顺序查找

77 位置信息列表压缩 编码 例： 具体用什么方法压缩取决于索引的类型：文档编号索引、频率索引、位置索引 编码（Elias, 1975)
L=<3,7,11,23,29,37,41,…> L=<3,4,4,12,6,8,4,…> 具体用什么方法压缩取决于索引的类型：文档编号索引、频率索引、位置索引 编码（Elias, 1975) 正整数k的码字包含两个部分，选择器（正文长度的一无码，如3表示为001, 5表示为00001等）和正文。保证仅用较短的位数表示相应的整数。如 例，右表中1,5，7,17表示为 编码 对编码中的选择器再用编码方式编码 31：001　01　11111　 　　5的编码 k selector(k) body(k) 1 5 001 101 7 111 31 00001 11111

78 索引压缩方法的选择 考虑的因素 高查询性能的索引压缩 索引的内容；压缩率；存储索引的介质的读取性能；解码的开销 字节对齐编码 字对齐编码
对L中的每个值x,用可变字节编码，即多个字节（视x的大小而定），每个字节的最高位用来表示是否还有后续字节。 不是为最大压缩而设计的，而是为优化解码速度而设计的 如：<1624,26,226,…>表示为： … 字对齐编码 将多个值用一个字来表示（例如32位），其中前4位描述后28共平均分配给了几个值（共有9种分法，也叫simple-9）。

79 文档重排 某一词项的文档编号如果能尽可能靠近，则有利于压缩。例如用编码时，如果两文档编号的差值小，则所用的编码位数也会少。
为文档重新编号并不影响检索，因为编号本身并没任何词义信息。 启发式规则 根据每个文档所含的不同词的个数对文档集中的文档重新排序（同时包含大量不同词项的两个文档可能具有相同的词项） 按URL字母顺序对文档编号（来自同一web服务器的两个文档可能具有相同的词项）

80 Word-aligned compression
Simple example: fix a word-width (say 16 bits) Dedicate one bit to be a continuation bit c. If the gap fits within 15 bits, binary-encode it in the 15 available bits and set c=0. Else set c=1 and use additional words until you have enough bits for encoding the gap. More practical caveat: In practice, simpler word-aligned compression better

81 动态倒排索引 批量更新：索引不立刻对文档集的更新做出反应 Rebuild: 重建新的索引
Remerge：根据新插入的文档建一个索引，并与原始索引合并。其本质是基于合并的索引。在此过程中还要考虑删除文档。如果删除的比例不够大，Remerge更有优势，因为对大部分文档，不需要再解析。

82 动态倒排索引 增量式更新：文档集有变化，立即更新
No Merge：查询时读出某词项的多个位置列表，然后连接这些位置列表（同一词项的位置列表分散，需要大量的磁盘寻道）。 对于连续的倒排列表：不允许为一个列表已在索引中的词项建新的列表。 合并更新：当索引器耗尽内存时，就合并内存中累积的数据和磁盘上已有的索引。（每次更新时都要将磁盘上已有索引加载到内存，顺序读） 就地更新：索引更新时，只要有位置信息列表写到磁盘，就在这个位置信息列表末端预留一些空间（如INPLACE：按比例分配，）。随后，同一词项的位置信息要写入磁盘时就利用该空间。如果空间用完，将整个列表重新装到一个新的闲置。（哪个词项有更新就访问该词项的位置列表，随机读，磁盘寻道比较耗时） 混合索引：位置列表短时，用合并更新，长时，用就地更新。

83 动态倒排索引 对于非连续的倒排列表：位置信息列表在磁盘空间上不连续
索引分割，LOGARITHMIC MERGE　(Lucene 和 Wumpus采用）：每个分区（分割的索引）有一个标识g，标识这个分区是第几代。每当搜索引擎索引过程耗尽内存时，就为内存索引中的数据创新一个索引分区，标识g=1。然后检查已创建的分区标识，如果有相同的标识g’，就合并它们，合并后的标签为g’+1

84 动态倒排索引 文档删除 文档修改 无效列表：通过该列表来过滤作废的位置信息。 垃圾回收：当删除文档较多时，需要释放其占用的索引位置。
视为删除后又插入的过程

85 邻近度排名 其中[ui,vi]为查询词向量在d中的一覆盖(cover)，即，包含了所有的查询词项，且不存在一个属于[ui,vi]的更小的区域包含所有词项。

86 查询处理 Document-at-a-time查询处理 枚举所有匹配的文档，逐个计算它们的得分，最后根据得分排序
rankBM25_DocumentAtATime(<t0,…,tn-1>,k) m0 dmin0<=i<=n-1{nextDoc(ti,-) # 需要扫描每个t对应的文档列表的首个元素，共n次 While d<  do results[m].docidd results[m].score0<=i<=n-1 BM25(ti,d) mm+1 dmin0<=i<=n-1{nextDoc(ti,d)} 按score降序排列results Return results中前k个结果 复杂度：O(Nqn+Nqlog(Nq)) Nq为所有查询词项出现文档数的和(每个文档中只有一个查询词时)。Nqlog(Nq)是排序时间

87 查询处理 最小二叉堆(binary min-heap) 空的二叉树是一个堆 满足下面条件的非空二叉树是一个堆
除了最底层外，其中的每一层都是完全填充的 最底层从左往右顺序进行填充 对每一个节点v，存储在v中的值要比存储在它的孩子节点中的值小 在实现中，一般采用数组形式而不是树形式

88 查询处理 rankBM25_DocumentAtATime_WithHeaps(<t0,…,tn-1>,k) For i0 to k-1 do results[i].score0 for i0 to n-1 do terms[i].termti terms[i].nextDocnextDoc(ti, -) 按nextDoc的升序建立terms堆 while terms[0].nextDoc<  do dterms[0].nextDoc score0 while terms[0].nextDoc =d do tterms[0].term scorescore+BM25(t,d) terms[0].nextDocnextDoc(t,d) reheap(terms)//重排terms if score > results[0].score then results[0].docidd results[0].scorescore reheap(results) 从results中删除分值为0的项 按降序排列reutls并输出 使用堆进行高效的查询处理 使用两个堆，一个用于管理查询词项，跟踪记录包含t的下一个文档；一个用于维护目前找到的前k（得分最高的文档）个搜索结果 复杂度：O(Nqlog(n)+Nqlog(k))

89 查询处理 rankBM25_DocumentAtATime_WithHeaps(<t1,…,tn>,k) 例：
t1: d1,d3,d7,d9 t2: d2,d3,d4 t3: d1,d2,d5 t4: d2,d3,d4,d5 K=3,term堆以文档编号排序，results堆以分值排序 初始： results terms results terms t1,d1 t3,d1 t3,d1 t2,d2 t4,d2 t2,d2 t4,d2 d=d1 score=1 t1,d3 Step1-2 Step3-6 Step8-14

90 查询处理 t1: d1,d3,d7,d9 t2: d2,d3,d4 t3: d1,d2,d5 t4: d2,d3,d4,d5 results
把堆中同一文档含的多个term全部处理完(或者多个term所出现在的某一文档全部处理完)，再处理下一个文档 每处理完某term链上的一个文档，就需要读取该链上的下一文档 t1: d1,d3,d7,d9 t2: d2,d3,d4 t3: d1,d2,d5 t4: d2,d3,d4,d5 查询处理 results terms results terms t3,d1 t3,d2 t4,d2 t2,d2 d1,2 t4,d2 t2,d2 d=d1 score=1 t1,d3 d=d1 score=2 t1,d3 同上页 Step15-18 results terms results terms d1,2 t2,d4 t1,d3 d3,3 d2,3 t4,d4 t3,d5 d1,2 d2,3 t2,d3 t4,d3 d=d3 score=3 t1,d7 d=d2 score=3 t3,d5

91 查询处理 最大得分 当知道result[0].score>maxScore(t)时，就知道仅含t的文档不可能进入前k，相应的文档就可不评分了。可将其从terms堆中移出（但仍需要用它计算文档的得分）。此时用两个堆，一个用来保存还在terms中的词项，一个用来保存已经移出的词项。

92 查询处理 term-at-a-time查询处理 document-at-a-time会赞成访问磁盘上不连续的空间
rankBM25_TermAtATime_WithHeaps(<t0,…,tn-1>,k) 按Nti的升序排列<t0,…,tn-1> acc{},acc’{}, acc[0].docid for i0 to n-1 do inpos0 outpos0 foreach ti位置信息列表中的文档d do while acc[inpos].docid<d do acc’[outpos++]acc[inpos++] acc’[outpos].docidd acc’[outpos].scoreBF25(ti,d) if acc[inpos].docid=d then acc’[outpos].scoreacc’[outpos].score +acc[inpos++].score dnextDoc(ti, acc’[outpos].docid) outpos++ while acc[inpos].docid< do acc’[outpos].docid swap acc and acc’ retun acc的前k个项//利用堆排序选择。 term-at-a-time查询处理 document-at-a-time会赞成访问磁盘上不连续的空间 term-at-a-time实现不需要任何不连续的磁盘访问模式。 score(q,d)=quality(d)+tqscore(t,d) O(Nqn+Nqlog(k)

93 查询处理 当词项位置列表较多时，acc可能不能全部放在内存中。一种有效的方法是为acc设置上限amax，并采用裁剪策略保证acc中的元素个数不大于上限。 越不频繁的词项越先处理（位置信息列表越短的） 具体策略（不保证返回与穷举算法一样的结果集，这是个近似） 假设处理完前i-1个查询词项后，搜索引擎共有acurrent个累加器，然后继续处理ti，则： acurrent ＋Nti  amax , 还有足够的空间，不用裁剪 acurrent = amax,累加器已达上限，不为ti的位置信息创建新的累加器 acurrent  amaxacurrent ＋Nti ，需要裁剪。为得分高的位置信息创建累加器。

94 查询处理 也可根据一定策略在索引时就进行裁剪（静态索引裁剪） 基于词项的裁剪 基于文档的裁剪
一个词项对应的位置（文档）列表中，只保留得分较高的文档 TREC　TB　2006数据上实验显示，裁剪率50%时，检索结果质量没有显著下降（P＠10由0.503降为0.500，MAP由0.260降为0.238），查询的平均时间下降了37% 基于文档的裁剪 计算t在文档d中的分布与在文档集C中的分布之间的KL距离，将文档d中该距离较小的t删除掉 TREC　TB　2006数据上实验显示，裁剪率70%时，检索结果质量没有显著下降（P＠10由0.508降为0.503，MAP由0.260降为0.238），查询的平均时间下降了37% 裁剪后得到的结果与不裁剪时可能不一致，如何保证正确性？对基于词项的裁剪，是将文档得分小于某阈值的文档裁剪了，利用该阈值可算出文档对某查询得分的“上限”，对文档排序时利用该上限，如果排序结果不正确，可再用一个未裁剪的索引。

95 查询处理 预计算得分 在BM25等模型中，可将t在文档中的分值（而不是出现的次数，TF值较小，通常用2－3位二进制即可）直接存储在索引中，加快查询处理过程（主要是从磁盘中读索引的过程）。但分值的保存用浮点数需要24－32位。 可对评分进行离散化，然后再存储

96 查询处理 前面提到的通常是按文档及位置的编号对位置列表进行排序的 也可基于影响力对位置列表进行排序，但对前面的算法及复杂度影响很大。

97 小结 文档预处理 索引构建 词法分析 停用词消除 (stop list) 词干还原(morphological stemming)
Term选择 statistics (counting words) part-of-speech tagging compound splitting partial parsing: noun phrase extraction other: use of thesaurus, named entity recognition, ... 索引构建 Motivation Inverted index Steps

98 作业 练习使用分词系统 练习使用英语词干化工具 设计一个简单的索引系统和查询处理系统(每个词在文档中的分值用其词频表示)