布尔检索
建立索引的主要步骤:
-
收集要索引的文档
-
词条化(tokenization)
-
语言学预处理,产生归一化的词条作为词项(等价类划分)
-
对所有文档按照其出现的词项建立倒排索引,包括一部词典(一般放在内存中)和一个全体倒排记录表(key-value pairs,存储在硬盘中)
形成
(词项, 文档ID)
或(词项, 文档ID, 次数)
的列表。次数称为文档频率(document frequency) -
合并文档ID,形成
(词项, [倒排记录表])
内存中的倒排记录表可以是:
- 单链表,可以搭配更高级的索引策略,如跳表(skip list)
- 变长数组,更好地利用 cache, 省空间
1.3 布尔查询的处理
方案:
-
使用求交集的方法,在 的时间合并倒排记录表
-
跳表信息检索领域诞生于二十世纪五十年代,经过了四十多年的发展,该领域已十分成熟。
优化:
-
对于中间结果表,可以就地对失效元素进行破坏性修改或只添加标记
-
通过在长倒排记录表中对表中的各元素二分查找实现合并
-
使用哈希存储长倒排索引表
但这些优化不适合压缩后的倒排记录表。
1.4 扩展操作:邻近操作符
第二章 词项词典及倒排记录表
2.1 文档分析及编码
文本编码;线性字符序列;文档单位;
文档单位:句子?段落?文章?章节?书?
索引粒度小:正确率高、召回率低
索引粒度大:正确率低、召回率高
2.2 词项集合的确定 p17
词条、词条类、词项
IP、号码、邮件地址、URL 作为单独的词项,是否需要索引?
专有名词 如C++
连字符和空格的处理:lowercase
与 lower-case
、lower case
,New York University
与 York University
。
汉语分词:
-
最大匹配法(启发式规则)
-
基于机器学习序列(隐马尔可夫模型,条件随机场模型)
-
短字符序列方法(k-gram)
停用词:
大型系统不使用;开销;按词频降序排列后人工选择
2.3 词条归一化、同义词的处理
去除字符、维护同义词关联关系
实际问题:
-
重音及变音符号
-
大小写转换 (启发式、机器学习序列模型),实际中全转为小写
-
英式美式写法,日期格式的习惯,ne’er <-> never
-
其他语言中各种奇奇怪怪的问题
-
不同语言文本的引用
2.3 词干还原(stemming)与词型归并(lemmatization)
词条 saw
,n. 句子;v. 看见. 如何分析其为动词、名词?
词干还原工具,正确率低
跳表
每个 处均匀放置跳表指针
短语的处理