《这就是搜索引擎》读书笔记

3.1.2 倒排索引基本概念
  • 文档（Document）: 代表以文本形式存在的存储对象
  • 文档集合（Document Collection） : 由若干文档构成的集合
  • 文档编号（Document ID）: 每个文档的唯一标识
  • 单词编号（Word ID）: 每个单词的唯一标识
  • 倒排索引（Inverted Index）: 单词——文档矩阵的一种具体存储形式。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表

    由两部分组成 : 单词词典和倒排文件

  • 单词词典（Lexicon） : 文档集合中出现过的所有单词构成的字符串集合

    单词词典内每条索引项记录单词本身的一些信息以及指向倒排列表的指针

  • 倒排列表（PostingList） : 记录出现过某个单词的所有文档的文档列表以及单词在这些文档中出现的位置信息，每条记录称为一个倒排项（Posting）

    根据倒排列表可以知道哪些文档包含某个单词

  • 倒排文件（Inverted File） : 将所有单词的倒排列表顺序地存储在磁盘上

    倒排文件是存储倒排索引的物理文件

  • 单词频率（TF） : 某个单词的某个文档中出现的次数
  • 文档频率（Doc Freq - DF） : 在文档集合中有多少个文档包含某个单词
3.2 单词词典

用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息

常用的数据结构 : 哈希加链表结构 和 树形词典结构

3.4 建立索引
  1. 两遍文档遍历法（2-Pass In-Memory Inversion）
  2. 排序法（Sort-based Inversion）
  3. 归并法（Merge-based Inversion）
3.5 动态索引
  1. 倒排索引
  2. 临时索引
  3. 已删除文档列表
5.2.3 特征权重计算

词频因子(TF) 变体计算公式一 : \(W_{TF} = 1 + \log(TF)\) 变体计算公式二 : \(a + (1 - a) \times \frac {TF} {Max(TF)}\)

TF : 代表词频，表示一个单词在文档中出现的次数 Max(TF) : 表示一个文档中所有单词出现次数最多的那个单词所对应的词频数

逆文档频率因子(IDF) 计算公式 : \(IDF_k = \log \frac {N} {n_k}\)

IDF : 代表全局文档集合范围内的一种全局因子，给定一个文档集合，那么每个单词的 IDF 值就唯一确定，跟具体的文档无关 IDF 考虑的不是文档本身的特征，而是特征单词之间的相对重要性 N 表示文档集合中总共有多少个文档
$n_k$ 表示特征单词 k 在其中多少个文档中出现过，即 文档频率(DF)

TF * IDF 框架 \(Weight_{word} = TF \times IDF\)