Coding 的痕迹

一位互联网奔跑者的网上日记

0%

布尔检索

建立索引的主要步骤:

  1. 收集要索引的文档

  2. 词条化(tokenization

  3. 语言学预处理,产生归一化的词条作为词项(等价类划分)

  4. 对所有文档按照其出现的词项建立倒排索引,包括一部词典(一般放在内存中)和一个全体倒排记录表(key-value pairs,存储在硬盘中)

    形成 (词项, 文档ID)(词项, 文档ID, 次数) 的列表。次数称为文档频率(document frequency

  5. 合并文档ID,形成 (词项, [倒排记录表])

内存中的倒排记录表可以是:

  • 单链表,可以搭配更高级的索引策略,如跳表(skip list
  • 变长数组,更好地利用 cache, 省空间

1.3 布尔查询的处理

方案:

  1. 使用求交集的方法,在 O(m+n)O(m + n) 的时间合并倒排记录表

  2. 跳表信息检索领域诞生于二十世纪五十年代,经过了四十多年的发展,该领域已十分成熟。

优化:

  1. 对于中间结果表,可以就地对失效元素进行破坏性修改或只添加标记

  2. 通过在长倒排记录表中对表中的各元素二分查找实现合并

  3. 使用哈希存储长倒排索引表

但这些优化不适合压缩后的倒排记录表。

1.4 扩展操作:邻近操作符

第二章 词项词典及倒排记录表

2.1 文档分析及编码

文本编码;线性字符序列;文档单位;

文档单位:句子?段落?文章?章节?书?

索引粒度小:正确率高、召回率低

索引粒度大:正确率低、召回率高

2.2 词项集合的确定 p17

词条、词条类、词项

IP、号码、邮件地址、URL 作为单独的词项,是否需要索引?

专有名词 如C++

连字符和空格的处理:lowercaselower-caselower caseNew York UniversityYork University

汉语分词:

  1. 最大匹配法(启发式规则)

  2. 基于机器学习序列(隐马尔可夫模型,条件随机场模型)

  3. 短字符序列方法(k-gram)

停用词:

大型系统不使用;开销;按词频降序排列后人工选择

2.3 词条归一化、同义词的处理

去除字符、维护同义词关联关系

实际问题:

  1. 重音及变音符号

  2. 大小写转换 (启发式、机器学习序列模型),实际中全转为小写

  3. 英式美式写法,日期格式的习惯,ne’er <-> never

  4. 其他语言中各种奇奇怪怪的问题

  5. 不同语言文本的引用

2.3 词干还原(stemming)与词型归并(lemmatization)

词条 saw,n. 句子;v. 看见. 如何分析其为动词、名词?

词干还原工具,正确率低

跳表

每个 P\sqrt{P} 处均匀放置跳表指针

短语的处理

欢迎关注我的其它发布渠道