词项词典及倒排记录表

 

本章内容

收集词项词典的预处理

1. 收集文档
2. 词条化
3. 应该把哪些词放入索引？

倒排记录表

1. 快速处理：跳表
2. 含位置信息的倒排记录表和短语查询

 

 

 

 

分析文档

1. 需要处理每一个文档的格式及语言
2. 格式：PDF/excel/word/HTML...
3. 语言
4. 字符集：utf-8/gbk/gb2312....

 

索引粒度

可取的做法是将每章或每段看成一个微型文档来建立索引，匹配单位的粒度越小，用户就越容易在文档中找到相关的段落。

• 索引粒度太小，正确率高  召回率低
• 索引粒度太大，召回率高  正确率低

 

 

 

词条与词项

词条：从原文 中切出来的，一模一样

词项：词条经过若干处理，再进行同义词归类后成为了词项

 

词条预处理

 

 

 

 

 

早期做法：去掉停用词

现在做法：保留停用词

 

停用词占空间：压缩一下，

去掉停用词，使得用户原来的一些限制也被 去掉

 

Note9.16√

 

 

 

 

词条归一化

 

 

 

文档预处理/词条处理：

词形归并（不常用、优点：变换，准确/正规，缺点：太慢）、

词干还原（常用，优点：快，缺点：不准确）

词干还原：不需要分析，纯 删除，处理后，这个词都不存在

 

 

 

 

 

倒排记录表快速合并：跳表

跳表指针：提供捷径来跳过那些不可能出现在检索结果中的纪录项

两个问题：

1. 在什么位置设置跳表？
2. 如何利用跳表指针进行倒排记录表的快速合并？

 

参数p1和p2，两个要合并的倒排表

1. answer放中间结果和最终结果
2. 当两个指针指向的倒排表都不为空时继续求交集
3. 如果p1指向的文档编号与p2指向的文档编号相等

4~6文档编号相等的做法

4.把文档编号添加到结果answer中

5.p1后移

6.p2后移

7~11 p1指向文档编号小于p2指向文档编号，有两种情况

P1有跳表，比较一下能不能跳，能跳就跳，不能跳就跳回来

P1没跳表，按第一章的方法往后移

8.p1有跳表，且p1跳表指向的文档编号比P2还小

9.如果一直满足条件，可以跳很多次

10.能跳，p1跳到跳表指针指向的元素

11.p1比较小且没有跳表——p1后移

12~15.p1指向的文档编号大于p2指向的文档编号，只要把7~11行的p1改成p2，p2改成p1

做法与7~11一致，只需要把指针对象换掉。

16.返回最终结果。

 

 

 

 

 

 

不是带有跳表就能提升效率，因为跳表增加了比较的次数

 

在什么位置设置跳表指针？

一般在每个根号下L（倒排记录表的长度）的位置均匀放置跳表指针

 

跳表指针越多——步长越短——跳表指针越多——存储空间越大

 

跳表指针越少——步长越长——跳表指针越少——存储空间越小

 

 

 

 

 

 

 

 

 

短语查询和含位置信息的倒排记录表

扩展倒排索引的两种方式：

1. 二元接续词对
2. 位置信息索引

 

二元接续词对

 

缺点：大大增加词汇表的大小

可能导致错误结果

满足布尔查询但不满足用户需求

 

 

位置信息索引

 

缺点：

位置索引，包含了词在文档的什么 位置出现。

索引占的空间也变大了，查询也变慢。

非位置索引的倒排表：只含有文档ID

位置索引的倒排表：文档ID及位置列表

 

位置索引：短语查询 邻近查询

短语查询

 

邻近查询

 

 

 

 

位置索引：占空间大，可以完美的解决了短语查询，结果是对的，

二元接续词对：占空间大，可能出现错误结果。

如果是频繁出现/被用户检索的专有名词，采用二元接续词对，可以提高效率。

剩下的情况，由位置索引解决。

有些常 用的专有名词，最好是直接进词条（二元接续词条）

 

 

混合索引

二元接续词对和位置索引的有效合并

将频繁出现的二元接续词对也作为索引中的词项，其他类型的短语使用位置索引

 

Note9.23√ PPT2√