一、倒排索引：把翻文档变成查表

十二篇小文档，一共 62 个不同的词。正排索引是「文档 → 词」，倒排反过来：「词 → 文档」。

二、TF-IDF：让结果有先后

命中往往不止一篇，得排序。两个信号：

三、布尔检索：说得准，可它只会回答是或否

布尔查询「机器学习 AND 数据」，命中第 1 篇和第 11 篇，两篇。看着很准——两篇都真的相关。 可四篇真正相关的文档里，它只给出了两篇。 准确率 1.0000，召回率只有 0.5000。 同一句话交给排序，前三是 1、11、6。 第 6 篇在布尔里直接出局（它没提「数据」），可在排序里排第三。 布尔没有「多命中一点」这种说法，只有命中和不命中。 这就是搜索引擎一律用排序、不用布尔的主要原因。 顺便说清两个指标。准确率是「给你的里面有多少对」。召回率是「对的里面你给了多少」。 它们天生互相拉扯——多给结果召回上去，准确率就下来。

四、求交的代价：一千万次对八千次

布尔查询要算交集。两万篇文档、两个词各命中五千篇，两种做法：

五、动手 Demo：先建一张词到文档的表

五段：建倒排索引、TF-IDF 排序、布尔与排序对撞、求交代价、准确率与召回率。 全部手写，没有用检索库。 语料只有十二篇，刚好够看清每一步在干什么。

POST = {}                         # 倒排索引：词 -> 文档编号列表
for i, d in enumerate(DOCS):
    for w in d.split():
        POST.setdefault(w, []).append(i)

IDF = np.log(len(DOCS) / (X > 0).sum(0))    # 越稀有的词越有区分度
W = X * IDF                                 # tf 乘 idf


def rank(q):
    qv = np.zeros(len(VOC))
    for w in q.split():
        if w in IDX:
            qv[IDX[w]] += 1.0
    qv = qv * IDF
    return W @ qv / (NRM * np.sqrt((qv ** 2).sum()))   # 余弦

实跑输出：

--------------------------------------------------------------------
先建一张「词 → 文档」的表
--------------------------------------------------------------------
==============================================================

[1] 倒排索引：不问「这篇文档有什么词」，问「这个词在哪几篇」

  12 篇文档，一共 62 个不同的词。
  建一张表：每个词对应一串文档编号（这叫 postings 列表）。

    词          出现在哪几篇        篇数
    数据        1、4、5、9、11      5
    索引        3、7、10            3
    查询        3、4                2
    网络        2、5、9             3
    知识        6、8                2
    模型        1、11               2

  查「数据」：不用读十二篇文档，直接看这一行，5 篇。
  **倒排索引的全部意义就在这儿：把「翻文档」变成「查表」。**

  平均每个词的 postings 长度 1.50 篇，最长的词是「数据」（5 篇）。

[2] TF-IDF：光看有没有不够，还要排个先后

  一个查询常常命中好几篇，得给它们排序。两个信号：
  **TF（这篇里出现几次，越多越相关）和 IDF（整个库里越稀有越有区分度）。**
  权重取 tf × log(N/df)，再用余弦比相似度。

  查询「数据 训练 模型」：
    第 1  篇  相似度 0.7556  机器学习 需要 大量 数据 训练 模型
    第 11 篇  相似度 0.2501  机器学习 模型 的 效果 取决于 数据 质量
    第 9  篇  相似度 0.0516  神经 网络 需要 大量 数据 和 算力

  查询「索引 查询」：
    第 3  篇  相似度 0.4890  数据库 用 索引 加快 查询 速度
    第 4  篇  相似度 0.2521  关系 数据库 把 数据 存成 表 用 SQL 查询
    第 10 篇  相似度 0.1359  搜索引擎 先 建 索引 再 排序 结果

  查询「知识 表示」：
    第 6  篇  相似度 0.5262  人工智能 包括 机器学习 和 知识 表示
    第 8  篇  相似度 0.4206  知识 图谱 用 三元组 表示 实体 之间 的 关系
    第 1  篇  相似度 0.0000  机器学习 需要 大量 数据 训练 模型

  **同一个词在不同文档里权重不同，靠的就是 IDF。**
  **「的」「和」这种词 IDF 接近 0，几乎不影响排序。**

[3] 布尔检索：说得准，可它只会回答「是」或「否」

  布尔查询「机器学习 AND 数据」——两篇都含这两个词才算命中：
    命中文档：1、11（2 篇）

  同一句话交给排序：前三是 1、11、6

    只被排序选中的      6
    布尔选中的          1、11

  **布尔只有「命中」和「不命中」，没有「多命中一点」这种说法。**
  一篇只提了「机器学习」没提「数据」的文档，在布尔里直接出局，
  可在排序里它可能排第二。**这就是搜索引擎一律用排序、不用布尔的主要原因。**

[4] 索引有多大：词典、postings 和跳表

    项目                数量
    词典里的词          62
    postings 总长       93
    平均每篇几个词      7.8

  两词求交（A AND B）要按编号往后跳着比。真实规模下差别很大：

    办法          比较次数      耗时（毫秒）  结果
    逐个比        12604315      2043.84       1244 篇
    归并求交      8753          5.98          1244 篇

  两万篇文档、两个词各命中五千篇：逐个比要 1260 万次，归并只要 8753 次。

  **逐个比做了 1260 万次比较，归并只做了 8753 次——差 1440 倍。**
  这还没算跳表。真实搜索引擎的词典有几千万个词、postings 有几亿条。
  **所以压缩和跳过不是优化，是能不能跑起来的问题。**

[5] 怎么知道排得好不好：准确率和召回率

  手工标了四篇真正相关的文档：1、2、9、11。
  拿查询「机器学习 数据」看前三条：
    前 3 条：命中 2 篇，准确率 0.6667，召回率 0.5000
    前 5 条：命中 4 篇，准确率 0.8000，召回率 1.0000

  **准确率是「给你的里面有多少是对的」，召回率是「对的里面你给了多少」。**
  两个数一起涨很难——多给结果召回上去，准确率就下来。
  **前面那个布尔查询命中的 2 篇全都相关，准确率是 1.0000。**
  **可四篇相关的它只给出两篇，召回率只有 0.5000。**

  五段连起来：**倒排索引把「翻文档」变成「查表」**；
  **TF-IDF 让结果有先后**；**布尔只能回答有没有，所以搜索必须排序**；
  **真实索引大到必须压缩**；**而好不好用，得靠准确率和召回率一起量。**

第 1 段那张表要横着看：「数据」出现在五篇里，「查询」只出现在两篇。 篇数少说明这个词有区分度，这正是 IDF 要用的信息。 第 2 段三个查询的分数衰减得很快。 这不是模型不好，是余弦的常态——只有第一篇真的三个词全中。 第 3 段是这一节的转折：布尔命中两篇全对，可它漏了两篇。 「准确率 1.0000、召回率 0.5000」这句话，比任何解释都清楚。 第 4 段那两个数（1260 万对 8753）差 1440 倍，原因只有一个： postings 是有序的，而归并利用了这一点。

30 秒实验

1. 把第 1 段的语料加五篇讲「数据库」的文档，重跑第 2 段查询「索引 查询」。 前几名会变——IDF 跟着库变了，同样的查询在更大的库里排名不同。
2. 把第 3 段的布尔查询换成「机器学习 OR 数据」，重跑。 召回率会冲到 1.0000，准确率会掉下来——OR 就是拿准确率换召回率的开关。
3. 把第 4 段的两个 postings 长度从 5000 改成 500，重跑。 差距会从 1440 倍缩小到一百多倍——嵌套比是平方，归并是线性，规模越小差别越小。

常见误区

1. 以为「检索就是数据库加个 like」。like 是全表扫描加字符串匹配， 而且它不能排序。真正让它变成检索的，是倒排索引和相关性打分。
2. 以为「TF-IDF 里的 IDF 越极端越好」。IDF 高只说明稀有。 一个错别字也很稀有，可它不该排在第一位。
3. 以为「准确率和召回率能一起涨」。在不换模型的前提下， 它们就是一条曲线上的两端。想同时涨只有一个办法：换个更好的模型。
4. 以为「相关就是包含关键词」。第 3 段那篇没提「数据」的文档， 在排序里排第三，而且它确实相关——语义相关不等于字面包含。

检索解决的是「找得到」，下一节往上一层：让机器不只是找到，还能「懂关系」。 把知识拆成一句一句的主谓宾，再让规则把没写下的事实推出来。

• ☐ （本节完，下一节 12.3 语义网络和语义网）

相关笔记

• 知识获取和统计语义学
• 数据库
• 语义网络和语义网
• 📘 图解人工智能 · 索引