Adam Chow's Life Journals

Appearance

倒排索引是一种数据结构，广泛应用于全文搜索系统中，它将文档中的单词映射到包含该单词的文档列表。

1. 基本概念 ​

假设我们有以下三个文档:

文档1: "The quick brown fox"
文档2: "Quick brown foxes leap"
文档3: "Lazy dogs sleep"

2. 构建过程 ​

  • 步骤1: 分词 首先，我们需要将每个文档分解为单词。
文档1: [The, quick, brown, fox]
文档2: [Quick, brown, foxes, leap]
文档3: [Lazy, dogs, sleep]
  • 步骤2: 规范化 接下来，我们可能会进行一些规范化处理，如将所有单词转为小写，去除停用词等。
文档1: [quick, brown, fox]
文档2: [quick, brown, fox, leap]
文档3: [lazy, dog, sleep]
  • 步骤3: 创建倒排索引 现在，我们为每个唯一的词创建一个列表，其中包含该词出现的所有文档。
   词       |    文档列表
-----------+------------------
  quick    |    1, 2
  brown    |    1, 2
  fox      |    1, 2
  leap     |    2
  lazy     |    3
  dog      |    3
  sleep    |    3

3. 搜索过程 ​

当我们搜索某个词时，比如 "brown"，我们可以直接查找索引:

搜索 "brown"
  |
  v
[brown] --> 文档1, 文档2

如果搜索多个词，如 "quick brown":

搜索 "quick brown"
  |
  v
[quick] --> 文档1, 文档2
[brown] --> 文档1, 文档2
  |
  v
结果: 文档1, 文档2 (两个词都出现的文档)

4. 复杂查询 ​

对于更复杂的查询，如 "quick OR dog":

        搜索 "quick OR dog"
              |
      +-------+-------+
      |               |
   [quick]          [dog]
      |               |
 文档1, 文档2        文档3
      |               |
      +-------+-------+
              |
        结果: 文档1, 文档2, 文档3

5. 优化: 添加词频和位置信息 ​

为了支持更高级的搜索功能，我们可以在索引中添加更多信息:

   词       |    文档列表 (文档ID: 频率 [位置])
-----------+----------------------------------------
  quick    |    1: 1 [1], 2: 1 [0]
  brown    |    1: 1 [2], 2: 1 [1]
  fox      |    1: 1 [3], 2: 1 [2]
  leap     |    2: 1 [3]
  lazy     |    3: 1 [0]
  dog      |    3: 1 [1]
  sleep    |    3: 1 [2]

这种扩展的索引结构允许我们执行更复杂的查询，如短语搜索或基于词频的相关性排序。

6. 总结 ​

倒排索引的主要优势在于它能够快速定位包含特定词的文档，而不需要扫描每个文档的全文。这使得它在处理大规模文本数据时特别高效。

7. 搜索引擎的查询结果的排序依据 ​

1. TF-IDF (词频-逆文档频率) ​

这是最基本也是最常用的排序方法之一：

  • TF (词频): 词在文档中出现的次数
  • IDF (逆文档频率): log(总文档数 / 包含该词的文档数)
  • TF-IDF = TF * IDF

示例计算:

假设 "apple" 在文档A中出现3次，文档B中出现2次
总文档数为1000，包含 "apple" 的文档有10个

TF(A) = 3, TF(B) = 2
IDF = log(1000/10) = 2

TF-IDF(A) = 3 * 2 = 6
TF-IDF(B) = 2 * 2 = 4

文档A的排序会高于文档B

2. BM25 (Best Matching 25) ​

BM25是TF-IDF的改进版，考虑了文档长度的影响。

BM25公式:
score(D, Q) = Σ IDF(qi) * (f(qi, D) * (k1 + 1)) / (f(qi, D) + k1 * (1 - b + b * |D| / avgdl))

其中:
qi: 查询中的词
f(qi, D): 词qi在文档D中的频率
|D|: 文档D的长度
avgdl: 平均文档长度
k1, b: 可调参数

总结 ​

实际应用中，搜索引擎通常会综合使用多个因素，并通过机器学习模型（如LambdaMART、RankNet等）来学习最优的排序策略。

最终排序分数 = ML_Model(TF-IDF, BM25, 语义相似度, PageRank, 用户行为, 时效性, 个性化因素, ...)

这种多因素结合的方法能够在各种复杂的搜索场景中提供更准确和相关的结果排序。