BM252023-01-12

符号定义BM25算法TF-IDFBM25代码参考文档

符号定义

$Q = [q_1, q_2, \cdots, q_n]$
- $Q$ ：输入的查询语句（query）
- $q_i$ $Q$ $i$ 个单词
- $n$ $Q$ 分词后得到单词的个数
$D = [d_1, d_2, \cdots, d_m]$
- $D$ ：文档集合
- $d_j$ $j$ 个文档
- $m$ ：文档的个数

BM25算法

TF-IDF

首先回顾TF-IDF的公式：

\begin{matrix} (1) & \begin{aligned} TF-IDF (Q, d_{j}) & = \sum_{i = 1}^{n} TF-IDF (q_{i}, d_{j}) \\ = \sum_{i = 1}^{n} TF (q_{i}, d_{j}) * IDF (q_{i}) \\ = \sum_{i = 1}^{n} \frac{q_{i} 在 d_{j} 中 出 现 的 次 数 + 1}{d_{j} 中 的 单 词 数 量} * \log \frac{m}{包 含 q_{i} 的 文 档 个 数 + 1} \end{aligned} \end{matrix}

简言之，用户query与某个文档的相似度，等于该query中每个词与该文档TF-IDF的和。

BM25

BM25算法是TF-IDF算法的优化版本，算法整体逻辑与之类似，计算公式如下：

\begin{matrix} (2) & \begin{aligned} Score (Q, d_{j}) & = \sum_{i = 1}^{n} W (q_{i}) * R (q_{i}, d) \\ W (q_{i}) & = \log \frac{m - d f_{i} + 0.5}{d f_{i} + 0.5} \\ R (q_{i}, d) & = \frac{f_{i} * (k_{1} + 1)}{f_{i} + K} \cdot \frac{q f_{i} * (k_{2} + 1)}{q f_{i} + k_{2}} \\ K & = k_{1} * (1 - b + b * \frac{d l}{a v g_d l}) \\ 其 中 ， & d f_{i} 为 D 中 包 含 单 词 q_{i} 的 文 档 数 量 \\ k_{1} 、 k_{2} 、 b 为 调 协 因 子 ， 默 认 k_{1} = 2 、 k_{2} = 1 、 b = 0.75 \\ f_{i} 为 单 词 q_{i} 在 d_{j} 中 出 现 的 次 数 \\ q f_{i} 为 单 词 q_{i} 在 Q 中 出 现 的 次 数 \\ d l 为 d_{j} 中 的 单 词 个 数 \\ a v g_d l 为 Q 中 各 个 文 档 的 平 均 单 词 个 数 \end{aligned} \end{matrix}

代码

参考文档

《这就是搜索引擎》 - 张俊林