Lesson 69: TF-IDF 文档相似度
练习任务
难度: 中
用纯 C 语言实现 TF-IDF 向量空间模型, 计算 3 篇文档的加权向量和两两余弦相似度。学员需要完成 7 个部分:
tokenize(doc, tokens, max)— 用strtok按空格分词compute_tf(tokens, n_tokens, tf)— 统计词频 (Term Frequency)compute_idf(tf_matrix, idf)— 计算逆文档频率 (Inverse Document Frequency)compute_tfidf(tf_matrix, idf, tfidf)— 计算 TF-IDF 加权矩阵cosine_sim(a, b)— 计算两个向量的余弦相似度print_matrix(...)— 通用矩阵打印 (支持 int/double, 带行列标签)main()— 主流程: 分词 -> TF -> IDF -> TF-IDF -> 相似度 -> 输出
三篇文档和词汇表已完整提供:
D0 = "the cat sat on mat"
D1 = "the dog sat on log"
D2 = "cat dog ate food"
词汇表 VOCAB: [the, cat, sat, on, mat, dog, log, ate, food]编译需链接数学库 (log() 和 sqrt() 在 libm 中):
bash
gcc -Wall -Wextra -std=c11 -o tfidf tfidf.c -lm提示: 核心挑战在于理解"文档 -> 向量"的思想转换——把自然语言变成可计算的空间点。向量空间模型背后的洞见是: 一篇文档的方向 (各词权重的比例关系) 比其长度 (向量模) 更重要。这也是为什么用余弦相似度而不是欧氏距离。
核心知识点
- TF-IDF 加权 — 词频乘以逆文档频率, 惩罚"the/a/is"等常见词, 奖励区分度高的稀有词
- 向量空间模型 (VSM) — 每篇文档 = N 维向量, 维度 = 词汇表大小, 值 = 词的 TF-IDF 权重
- strtok 分词机制 — 原地修改字符串, 在分隔符处插入
\0, 返回各段首指针; 必须先strcpy复制const数据 - 余弦相似度 — 用向量夹角度量文档相似性,
cos(a,b) = (a.b) / (|a|*|b|), 不受文档长度影响 - IDF 的数学直觉 —
log(N/df)反映了"这个词带了多少信息量": 出现在越多文档中 = 区分度越低 = idf 越小 - print_matrix 泛型设计 —
void*统一存储 int/double 矩阵,is_double标记决定printf格式; 一维索引i*n_cols+j - 搜索引擎范式 — 离线: 网页 -> 分词 -> TF-IDF 向量; 在线: 查询向量化 -> 与所有文档计算余弦 -> Top-K 返回
代码框架
c
#include <math.h>
#include <stdio.h>
#include <string.h>
#define N_DOCS 3
#define N_TERMS 9
#define MAX_TOKENS 5
static const char *DOCS[N_DOCS] = {
"the cat sat on mat",
"the dog sat on log",
"cat dog ate food"
};
static const char *VOCAB[N_TERMS] = {
"the", "cat", "sat", "on", "mat", "dog", "log", "ate", "food"
};
/* TODO 1: tokenize — 用 strtok 按空格拆分文档为单词数组 */
static int tokenize(char *doc, char *tokens[], int max) {
// 1) n = 0
// 2) 第一次: token = strtok(doc, " ")
// 3) while (token != NULL && n < max):
// tokens[n++] = token
// token = strtok(NULL, " ")
// 4) return n
}
/* TODO 2: compute_tf — 统计词频 (原始计数) */
static void compute_tf(char *tokens[], int n_tokens, int tf[]) {
// 1) memset(tf, 0, N_TERMS * sizeof(int))
// 2) for i in 0..n_tokens-1:
// for j in 0..N_TERMS-1:
// if strcmp(tokens[i], VOCAB[j]) == 0:
// tf[j]++; break
}
/* TODO 3: compute_idf — 逆文档频率
* idf[t] = log(N_DOCS / df[t]), df[t] = 包含词 t 的文档数
* 注意: N_DOCS/df 必须转为 double 避免整数除法! */
static void compute_idf(int tf_matrix[N_DOCS][N_TERMS], double idf[]) {
// 1) for t in 0..N_TERMS-1:
// df = 0
// for d in 0..N_DOCS-1:
// if tf_matrix[d][t] > 0: df++
// idf[t] = log((double)N_DOCS / df)
}
/* TODO 4: compute_tfidf — TF-IDF 加权
* tfidf[d][t] = tf_matrix[d][t] * idf[t] (逐元素相乘) */
static void compute_tfidf(int tf_matrix[N_DOCS][N_TERMS],
const double idf[],
double tfidf[N_DOCS][N_TERMS]) {
// 1) for d in 0..N_DOCS-1:
// for t in 0..N_TERMS-1:
// tfidf[d][t] = tf_matrix[d][t] * idf[t]
}
/* TODO 5: cosine_sim — 余弦相似度
* cos(a,b) = (a.b) / (|a| * |b|)
* 零向量保护: |a|==0 或 |b|==0 时返回 0.0 */
static double cosine_sim(const double a[], const double b[]) {
// 1) dot = 0.0, norm_a = 0.0, norm_b = 0.0
// 2) for k in 0..N_TERMS-1:
// dot += a[k] * b[k]
// norm_a += a[k] * a[k]
// norm_b += b[k] * b[k]
// 3) if (norm_a == 0.0 || norm_b == 0.0) return 0.0
// 4) return dot / (sqrt(norm_a) * sqrt(norm_b))
}
/* TODO 6: print_matrix — 泛型矩阵打印
* void* data 统一存放 int 或 double 矩阵
* 索引: ((double*)data)[i * n_cols + j] (一维扁平数组) */
static void print_matrix(const char *title,
const char *row_labels[],
const char *col_labels[],
const void *data,
int n_rows, int n_cols,
const char *fmt, int is_double) {
// 1) printf("%s\n", title)
// 2) if col_labels 非 NULL: printf("%-6s", ""); for j: printf(" %6s", col_labels[j])
// 3) for i in 0..n_rows-1:
// printf("%-6s", row_labels[i])
// for j in 0..n_cols-1:
// printf(" ")
// if is_double: printf(fmt, ((double*)data)[i*n_cols+j])
// else: printf(fmt, ((int*)data)[i*n_cols+j])
// printf("\n")
}
/* TODO 7: main — 完整流程
* tokenize -> TF -> IDF -> TF-IDF -> Cosine -> 输出
* 输出格式必须与 expected_output.txt 逐字符一致 */
int main(void) {
// 1) 打印标题与文档列表
// 2) 对每篇文档: strcpy -> tokenize -> compute_tf
// 3) compute_idf -> compute_tfidf
// 4) 对每对文档: cosine_sim 填充 sim[d1][d2]
// 5) 依次打印: TF矩阵 -> IDF向量 -> TF-IDF矩阵 -> 相似度矩阵 -> 解释
}TIP
先不要往下翻看参考解答。在纸上画出三篇文档的 9 维向量空间, 标注每篇文档在每个维度上的 TF-IDF 权重。观察 D0 和 D1 在"the/sat/on"三个维度上权重均为正——这正是它们余弦相似度较高 (0.2645) 的原因。D0 和 D2 仅在"cat"维度上有重叠——余弦相似度仅 0.0727。
深度讲解
1. TF-IDF 的历史与核心直觉——为什么需要加权?
1.1 Karen Sparck Jones 的洞见 (1972)
TF-IDF 由英国计算机科学家 Karen Sparck Jones 在 1972 年提出。她观察到: 并非所有词对检索同样有用。高频功能词 (the, a, is, of) 无处不在, 所携带的信息量几乎为零。
核心直觉 (用一句话概括):
TF * IDF = (这个词在本篇文档中的热度) * (这个词在整个语料库中的稀有度)
词频高 + 仅在此文档出现 -> 认定你是这篇文章的关键词! -> TF-IDF 权重高
词频高 + 到处都出现 -> 你是"背景噪音" -> TF-IDF 权重低
词频低 + 仅在此出现 -> 可能是拼写错误或边缘词 -> TF-IDF 权重中等Karen Sparck Jones 的工作奠定了现代信息检索的数学基础, 影响了从 AltaVista 到 Google 的每一代搜索引擎。
1.2 三种权重的直观对比
原始计数(TF): IDF 加权后(TF-IDF):
the cat mat the cat mat
D0 1 1 1 D0 0.41 0.41 1.10
D1 1 0 0 D1 0.41 0.00 0.00
D2 0 1 0 D2 0.00 0.41 0.00
观察: "the" 在 D0 和 D1 中 TF 都是 1, 但 IDF=0.41 (出现在 2 篇文档中)
"mat" 在 D0 中 TF 也是 1, 但 IDF=1.10 (仅出现在 1 篇文档中)
TF-IDF 将 "mat" 的权重提升为 "the" 的 2.7 倍——
这是 IDF 的"奖励区分词、惩罚常见词"效应好）1.3 BM25: TF-IDF 的演进
现代搜索引擎常用 BM25 (Okapi BM25) 替代经典 TF-IDF。BM25 引入了文档长度归一化和 TF 饱和因子, 解决了经典 TF-IDF 的两大问题:
| 经典 TF-IDF | BM25 | |
|---|---|---|
| TF 处理 | 线性增长 (tf) | 饱和增长 (tf / (k + tf)) |
| 文档长度 | 不处理 | 字符数归一化 |
| 参数可调 | 无 | k 控制 TF 饱和, b 控制长度惩罚 |
但经典 TF-IDF 仍然是理解所有这些变体的基石——理解了它, BM25、语言模型、词嵌入的直觉都可以顺势推导。
2. tokenize — strtok 分词与内存陷阱
2.1 strtok 的工作原理
strtok 是 C 标准库中最"有副作用"的函数之一——调用后原字符串会被修改。
c
/*
* strtok 的执行过程 (以 "the cat sat" 为例):
*
* 原始字符串: [t][h][e][ ][c][a][t][ ][s][a][t][\0]
* 0 1 2 3 4 5 6 7 8 9 10
*
* strtok(str, " ") 第1次: 在索引3(空格)处插入\0 -> 返回 &str[0] = "the"
* strtok(NULL, " ") 第2次: 从索引4开始 -> 在索引7处插入\0 -> 返回 &str[4] = "cat"
* strtok(NULL, " ") 第3次: 从索引8开始 -> 到末尾 -> 返回 &str[8] = "sat"
* strtok(NULL, " ") 第4次: 返回 NULL
*/IMPORTANT
strtok 修改原字符串意味着——不能对 const char* 直接调用 strtok。这也是为什么 main() 中必须用 strcpy 复制 DOCS[d] 到局部 buffer 再传入 tokenize。
2.2 tokenize 实现与调用链
c
static int tokenize(char *doc, char *tokens[], int max) {
int n = 0;
char *token = strtok(doc, " ");
while (token != NULL && n < max) {
tokens[n++] = token;
token = strtok(NULL, " ");
}
return n;
}调用方式 (注意必须先 copy):
c
char buf[64];
strcpy(buf, DOCS[d]); // 复制到可写 buffer
char *tokens[MAX_TOKENS];
int n = tokenize(buf, tokens, MAX_TOKENS);
// tokens[0] 指向 buf 内部的 "the"
// tokens[1] 指向 buf 内部的 "cat"CAUTION
常见错误: tokenize((char*)DOCS[d], tokens, MAX_TOKENS) — 强制去掉 const 不会消除 undefined behavior。DOCS 可能存放在只读内存段中 (如 .rodata), 写入会触发 segfault。
3. 词频 TF 计算——词袋模型与向量化
3.1 词袋模型 (Bag of Words)
词袋模型将文档视为"一个装了词的袋子"——忽略词序和语法, 只关心每个词出现了多少次。
D0 = "the cat sat on mat"
D1 = "mat on sat cat the" <- 词序完全不同
但词袋模型下:
D0 -> [1, 1, 1, 1, 1, 0, 0, 0, 0]
D1 -> [1, 1, 1, 1, 1, 0, 0, 0, 0] <- 完全相同的向量!
词袋模型的优缺点:
(ok) 简单、高效、维度固定
(ok) 对拼写错误和词序变化有一定鲁棒性
(fail) 完全丢失语义和语法
(fail) "dog bites man" 和 "man bites dog" 向量相同3.2 compute_tf 的实现
c
static void compute_tf(char *tokens[], int n_tokens, int tf[]) {
for (int t = 0; t < N_TERMS; t++) tf[t] = 0;
for (int i = 0; i < n_tokens; i++) {
for (int j = 0; j < N_TERMS; j++) {
if (strcmp(tokens[i], VOCAB[j]) == 0) {
tf[j]++;
break; // 找到就跳出, 避免重复匹配
}
}
}
}NOTE
strcmp 返回 0 表示相等——初学者常见的错误是写成 if (strcmp(...)) (非零为真, 逻辑反了)。正确写法是 if (strcmp(tokens[i], VOCAB[j]) == 0)。
3.3 为什么使用原始计数 (不归一化)?
经典 TF 有多种变体: 原始计数、对数归一化 log(1+tf)、L1 归一化 tf/sum(tf)、L2 归一化等。本题使用原始计数是因为:
- 文档长度相近 (都是 4-5 个词), 不需要长度归一化
- IDF 已经提供了跨词的归一化效应
- 简单直观, 便于理解核心流程
4. IDF 逆文档频率——稀有词的"信息价值"
4.1 IDF 的数学推导
idf(t) = log(N / df(t))
其中:
N = 文档总数 (本题 N=3)
df(t) = 包含词 t 的文档数 (Document Frequency)
极端情况分析:
df = 1 (仅出现在 1 篇文档):
idf = log(N) -> 最大权重, 稀有词, 区分度极高
例如: mat, log, ate, food -> idf = log(3) = 1.0986
df = N (出现在所有文档):
idf = log(N/N) = log(1) = 0 -> 完全忽略, 无区分度
本题中无此情况, 但若语料库够大, "的""是""了"等词 df~=N
df = 2 (出现在一半文档中):
idf = log(N/2) -> 中等权重
例如: the, cat, sat, on, dog -> idf = log(1.5) = 0.4055为什么是 log? 信息论视角: log(N/df) = 这个词的"惊喜度"。如果一个词出现在 100% 的文档中 (df=N), 它对检索毫无帮助——告诉查询系统"这篇文档有'the'", 等于什么也没说。log(1)=0 精确表达了"零信息量"。
4.2 整数除法陷阱
c
/* 错误示例: 整数除法导致 idf 全为 0 */
void compute_idf_wrong(int tf_matrix[N_DOCS][N_TERMS], double idf[]) {
for (int t = 0; t < N_TERMS; t++) {
int df = 0;
for (int d = 0; d < N_DOCS; d++)
if (tf_matrix[d][t] > 0) df++;
idf[t] = log(N_DOCS / df); // <-- BUG: 整数除法!
// N_DOCS=3, df=2 -> 3/2=1 -> log(1)=0
}
}
/* 正确写法 */
void compute_idf_correct(int tf_matrix[N_DOCS][N_TERMS], double idf[]) {
for (int t = 0; t < N_TERMS; t++) {
int df = 0;
for (int d = 0; d < N_DOCS; d++)
if (tf_matrix[d][t] > 0) df++;
idf[t] = log((double)N_DOCS / df); // <-- 显式转换
}
}WARNING
这个 bug 极具隐蔽性——代码编译通过, 运行不报错, 但 idf 值全是 0。最终 TF-IDF 矩阵退化为 TF 矩阵, 余弦相似度完全失准。
5. TF-IDF 加权矩阵——惩罚与奖励的平衡
c
static void compute_tfidf(int tf_matrix[N_DOCS][N_TERMS],
const double idf[],
double tfidf[N_DOCS][N_TERMS]) {
for (int d = 0; d < N_DOCS; d++)
for (int t = 0; t < N_TERMS; t++)
tfidf[d][t] = tf_matrix[d][t] * idf[t];
}完整 TF-IDF 矩阵可视化:
the cat sat on mat dog log ate food
D0 0.4055 0.4055 0.4055 0.4055 1.0986 0.0000 0.0000 0.0000 0.0000
D1 0.4055 0.0000 0.4055 0.4055 0.0000 0.4055 1.0986 0.0000 0.0000
D2 0.0000 0.4055 0.0000 0.0000 0.0000 0.4055 0.0000 1.0986 1.0986
关键观察:
- "the" 权重被 IDF 压制为 0.4055 (虽然 TF=1)
- "mat" 权重被 IDF 提升为 1.0986 (与"the"的 TF 相同但 idf 高 2.7 倍)
- D2 有两个高权重词 (ate+food=2.1972) -> D2 向量长度大
- 向量长度差异不影响余弦相似度! (余弦只看方向)三个核心性质:
性质 1: 词的重要性 = TF * IDF 的共同作用
TF 高但 df 也高 (如 "the") -> 权重低 -> 被 IDF 惩罚
TF 低但 df 低 (如 "mat") -> 权重高 -> 被 IDF 奖励
性质 2: IDF 是"跨文档归一化"
同一个词在所有文档中被乘以相同的 IDF 因子
这是一个全局调整——重新校准每个维度的重要性
性质 3: 零值分布反映文档差异
D0 非零维度: the, cat, sat, on, mat (5 个)
D1 非零维度: the, dog, sat, on, log (5 个)
D2 非零维度: cat, dog, ate, food (4 个)
共享维度数 = 余弦相似度的原始驱动力
D0-D1 共享 3 个维度 -> cos = 0.2645
D0-D2 共享 1 个维度 -> cos = 0.0727
D1-D2 共享 1 个维度 -> cos = 0.07276. 余弦相似度——几何直觉与代数推导
6.1 点积的几何含义
a . b = |a| * |b| * cos(theta)
改写: cos(theta) = (a . b) / (|a| * |b|)
这就是余弦相似度的来源——它直接度量了两向量夹角的余弦值。
当 theta=0 (完全同向): cos=1 -> 文档内容几乎相同
当 theta=90 (正交): cos=0 -> 无任何共同词
当 theta=180 (完全反向): cos=-1 -> TF-IDF 非负时不出现
对于 TF-IDF 向量 (所有分量非负), cos 范围是 [0, 1]6.2 实现与逐步追踪
c
static double cosine_sim(const double a[], const double b[]) {
double dot = 0.0, norm_a = 0.0, norm_b = 0.0;
/* 一次遍历完成三个累加 */
for (int k = 0; k < N_TERMS; k++) {
dot += a[k] * b[k]; // 点积分子
norm_a += a[k] * a[k]; // |a|^2
norm_b += b[k] * b[k]; // |b|^2
}
/* 零向量保护 */
if (norm_a == 0.0 || norm_b == 0.0) return 0.0;
return dot / (sqrt(norm_a) * sqrt(norm_b));
}计算 D0-D1 的余弦相似度 (实际数字追踪):
D0 = [0.41, 0.41, 0.41, 0.41, 1.10, 0, 0, 0, 0 ]
D1 = [0.41, 0, 0.41, 0.41, 0, 0.41, 1.10, 0, 0 ]
dot = 0.41*0.41 + 0 + 0.41*0.41 + 0.41*0.41 = 0.504 (approx)
|D0|^2 = 0.41^2 * 4 + 1.10^2 = 0.168*4 + 1.21 = 1.882
|D0| = sqrt(1.882) = 1.372
|D1|^2 = 同 D0 = 1.882
|D1| = 1.372
cos = 0.504 / (1.372 * 1.372) = 0.504 / 1.882 = 0.268 -> 四舍五入得 0.2645 (ok)6.3 欧氏距离 vs 余弦相似度的适用场景
为什么 NLP 用余弦而不是欧氏距离?
场景: 添加文档 D0' = D0 的 2 倍 (每个词都出现两次)
D0 (原始): TF = [1,1,1,1,1,0,0,0,0]
D0' (两倍): TF = [2,2,2,2,2,0,0,0,0]
欧氏距离: large <- 长度不同导致距离大
余弦相似度: 1.0 <- 方向完全相同, 余弦 = 1
结论: 余弦相似度"免疫"文档长度差异。
两篇内容相似但长度差异大的文档, 余弦接近 1。| 度量方式 | 公式 | 对长度的敏感度 | 适用场景 |
|---|---|---|---|
| 欧氏距离 | sqrt(Sigma(a_i - b_i)^2) | 高 | 图像像素比较、坐标距离 |
| 余弦相似度 | (Sigma a_i b_i)/( | a | |
| 曼哈顿距离 | Sigma | a_i - b_i |
7. print_matrix 泛型设计——void* 与一维索引
7.1 为什么用 void* 而不写两个函数?
矩阵数据可能是 int (TF 矩阵) 或 double (TF-IDF 矩阵、相似度矩阵)。用 void* + is_double 标记统一处理, 避免写 print_int_matrix 和 print_double_matrix 两个几乎相同的函数。
c
void print_matrix(const char *title,
const char *row_labels[], // 如 {"D0", "D1", "D2"}
const char *col_labels[], // 如 VOCAB 或 NULL
const void *data, // 一维扁平数组
int n_rows, int n_cols,
const char *fmt, // 如 "%6d" 或 "%6.4f"
int is_double); // 1=double, 0=int7.2 实现细节
c
void print_matrix(const char *title, const char *row_labels[],
const char *col_labels[], const void *data,
int n_rows, int n_cols, const char *fmt,
int is_double) {
printf("%s\n", title);
/* 列标签行 */
if (col_labels) {
printf("%-6s", ""); // 左上角空白
for (int j = 0; j < n_cols; j++)
printf(" %6s", col_labels[j]);
printf("\n");
}
/* 数据行 */
for (int i = 0; i < n_rows; i++) {
printf("%-6s", row_labels[i]); // 行标签左对齐
for (int j = 0; j < n_cols; j++) {
printf(" ");
if (is_double)
printf(fmt, ((double*)data)[i * n_cols + j]);
else
printf(fmt, ((int*)data)[i * n_cols + j]);
}
printf("\n");
}
}CAUTION
常见错误: ((double*)data)[i][j] — data 被声明为 const void*, 编译器不知道它是二维数组。写成 [i][j] 是未定义行为 (data 指向一维数组, [i][j] 需要编译器知道第二维的大小)。正确写法是手动计算一维索引 i * n_cols + j。
7.3 调用示例
c
// TF 矩阵 (int, 列标签用 VOCAB)
print_matrix("\n=== Term Frequency (TF) Matrix ===",
row_labels, VOCAB,
tf_matrix, N_DOCS, N_TERMS, "%6d", 0);
// TF-IDF 矩阵 (double, 列标签用 VOCAB)
print_matrix("\n=== TF-IDF Weighted Matrix ===",
row_labels, VOCAB,
tfidf, N_DOCS, N_TERMS, "%6.4f", 1);
// 相似度矩阵 (double, 行列标签相同)
print_matrix("\n=== Cosine Similarity Matrix (3x3) ===",
row_labels, row_labels, // 行列都 在 D0/D1/D2
sim, N_DOCS, N_DOCS, "%6.4f", 1);参考解答
练习1: tokenize — strtok 分词
c
static int tokenize(char *doc, char *tokens[], int max) {
int n = 0;
char *token = strtok(doc, " ");
while (token != NULL && n < max) {
tokens[n++] = token;
token = strtok(NULL, " ");
}
return n;
}要点: strtok 第一次传入字符串, 后续传入 NULL。tokens[] 存储的是 doc 内部的指针 (strtok 在空格处插入了 \0)。
练习2: compute_tf — 词频统计
c
static void compute_tf(char *tokens[], int n_tokens, int tf[]) {
for (int t = 0; t < N_TERMS; t++) tf[t] = 0;
for (int i = 0; i < n_tokens; i++) {
for (int j = 0; j < N_TERMS; j++) {
if (strcmp(tokens[i], VOCAB[j]) == 0) {
tf[j]++;
break;
}
}
}
}要点: strcmp 返回 0 表示相等。break 避免重复匹配——每个 token 在词汇表中匹配一次即可。
练习3: compute_idf — 逆文档频率
c
static void compute_idf(int tf_matrix[N_DOCS][N_TERMS], double idf[]) {
for (int t = 0; t < N_TERMS; t++) {
int df = 0;
for (int d = 0; d < N_DOCS; d++)
if (tf_matrix[d][t] > 0) df++;
idf[t] = log((double)N_DOCS / df);
}
}要点: df 统计包含词 t 的文档数 (TF > 0 即包含)。必须 (double)N_DOCS / df——整数除法会截断。log() 在 math.h 中, 需链接 -lm。
练习4: compute_tfidf — TF-IDF 加权
c
static void compute_tfidf(int tf_matrix[N_DOCS][N_TERMS],
const double idf[],
double tfidf[N_DOCS][N_TERMS]) {
for (int d = 0; d < N_DOCS; d++)
for (int t = 0; t < N_TERMS; t++)
tfidf[d][t] = tf_matrix[d][t] * idf[t];
}要点: 纯逐元素乘法——tfidf[d][t] = tf[d][t] * idf[t]。idf[t] 是全局因子 (同一个词在所有文档中乘以相同的 IDF)。
练习5: cosine_sim — 余弦相似度
c
static double cosine_sim(const double a[], const double b[]) {
double dot = 0.0, norm_a = 0.0, norm_b = 0.0;
for (int k = 0; k < N_TERMS; k++) {
dot += a[k] * b[k];
norm_a += a[k] * a[k];
norm_b += b[k] * b[k];
}
if (norm_a == 0.0 || norm_b == 0.0) return 0.0;
return dot / (sqrt(norm_a) * sqrt(norm_b));
}要点: 一次循环完成三个累加 (点积、两个 L2 范数平方)。零向量保护是关键——若某文档无词 (范数为 0), 除零会导致 NaN。
练习6: print_matrix — 泛型矩阵打印
c
static void print_matrix(const char *title,
const char *row_labels[],
const char *col_labels[],
const void *data,
int n_rows, int n_cols,
const char *fmt, int is_double) {
printf("%s\n", title);
if (col_labels) {
printf("%-6s", "");
for (int j = 0; j < n_cols; j++)
printf(" %6s", col_labels[j]);
printf("\n");
}
for (int i = 0; i < n_rows; i++) {
printf("%-6s", row_labels[i]);
for (int j = 0; j < n_cols; j++) {
printf(" ");
if (is_double)
printf(fmt, ((double*)data)[i * n_cols + j]);
else
printf(fmt, ((int*)data)[i * n_cols + j]);
}
printf("\n");
}
}要点: void* data 通过 (int*) 或 (double*) 转换后索引。一维索引公式 i * n_cols + j。col_labels 为 NULL 时跳过列标签行。
练习7: main — 完整主流程
c
int main(void) {
const char *row_labels[N_DOCS] = {"D0", "D1", "D2"};
int tf_matrix[N_DOCS][N_TERMS] = {0};
double idf[N_TERMS];
double tfidf[N_DOCS][N_TERMS];
double sim[N_DOCS][N_DOCS];
/* 1. 标题与文档列表 */
printf("=== TF-IDF Document Similarity ===\n\n");
printf("Documents:\n");
for (int d = 0; d < N_DOCS; d++)
printf(" D%d: \"%s\"\n", d, DOCS[d]);
/* 2. 分词 -> TF */
for (int d = 0; d < N_DOCS; d++) {
char buf[64];
char *tokens[MAX_TOKENS];
strcpy(buf, DOCS[d]);
int n = tokenize(buf, tokens, MAX_TOKENS);
compute_tf(tokens, n, tf_matrix[d]);
}
/* 3. IDF -> TF-IDF */
compute_idf(tf_matrix, idf);
compute_tfidf(tf_matrix, idf, tfidf);
/* 4. 余弦相似度矩阵 */
for (int d1 = 0; d1 < N_DOCS; d1++)
for (int d2 = 0; d2 < N_DOCS; d2++)
sim[d1][d2] = cosine_sim(tfidf[d1], tfidf[d2]);
/* 5. 输出 */
print_matrix("\n=== Term Frequency (TF) Matrix ===",
row_labels, VOCAB,
tf_matrix, N_DOCS, N_TERMS, "%6d", 0);
printf("\n=== Inverse Document Frequency (IDF) ===\n");
printf("N = %d documents\n", N_DOCS);
printf("Term ");
for (int j = 0; j < N_TERMS; j++) printf(" %6s", VOCAB[j]);
printf("\nIDF ");
for (int j = 0; j < N_TERMS; j++) printf(" %6.4f", idf[j]);
printf("\n");
print_matrix("\n=== TF-IDF Weighted Matrix ===",
row_labels, VOCAB,
tfidf, N_DOCS, N_TERMS, "%6.4f", 1);
print_matrix("\n=== Cosine Similarity Matrix (3x3) ===",
row_labels, row_labels,
sim, N_DOCS, N_DOCS, "%6.4f", 1);
printf("\nInterpretation:\n");
printf(" D0-D1: share common words (the, sat, on)"
" -> moderate similarity\n");
printf(" D0-D2: share only 'cat' -> low similarity\n");
printf(" D1-D2: share only 'dog' -> low similarity\n");
return 0;
}要点: strcpy(buf, DOCS[d]) 是必需的——strtok 会修改字符串。IDF 打印格式特殊 (有 "N = 3 documents" 行), 不能直接用 print_matrix。相似度矩阵行列标签相同 (都用 row_labels)。
对照检查:
compute_idf中用了(double)转换吗?cosine_sim中有零向量保护吗?print_matrix中索引是i * n_cols + j吗?main中strcpy复制了 DOCS 吗? IDF 的打印格式必须与expected_output.txt对齐了吗?
课堂讨论
- 为什么文本相似度用余弦而不用欧氏距离? 什么场景下欧氏距离反而更合适?
- 如果 "the" 出现在所有 3 篇文档中, idf 值是多少? 这个词对相似度有何贡献?
- 为什么 D0-D1 的相似度 (0.2645) 远大于 D0-D2 (0.0727)? 从向量空间角度解释。
- print_matrix 的
void* data为什么需要i * n_cols + j而不是[i][j]? C 语言的指针运算规则是什么? - 开放性讨论: 如果增加一篇中文文档 "猫 坐在 垫子上", TF-IDF 和余弦相似度还能直接计算吗? 需要做哪些前提工作?
课堂讨论解答 (Q1-Q5)
Q1: 余弦 vs 欧氏距离。 文本相似度关注"内容方向"而非"文档长度"。两篇内容相同但长度相差 10 倍的文档, 欧氏距离很远但余弦接近 1。欧氏距离适用于坐标距离、图像像素比较等"绝对位置"敏感的场景。
Q2: "the" 出现在所有文档中。 df=3, idf=log(3/3)=log(1)=0。该词在所有文档的 TF-IDF 权重为 0——对余余弦相似度零贡献。这正是 IDF 的核心价值: 完全屏蔽"在所有文档中都出现"的无区分力词。
Q3: D0-D1 vs D0-D2。 D0 和 D1 在 3 个维度上有正权重 (the, sat, on), 而 D0 和 D2 仅在 1 个维度上有正权重 (cat)。在 9 维空间中, 共享维度越多, 向量方向越接近——余弦值越大。
Q4: void 与一维索引。* C 语言中, void* 不携带类型信息。编译器不知道 data 是 double[3][9] 还是 int[3][9], 无法计算 [i][j] 的偏移 (知道第二维大小才能算 i*N + j)。手动计算 i * n_cols + j 将二维索引显式映射到一维位置, 对任何类型都正确。
Q5: 中文文档的挑战。 不能直接计算。中文分词需要专门的工具 (如 jieba、HanLP), 空格分隔法对中文无效 ("猫坐在垫子上"没有空格)。此外需要中英文共享词汇表或跨语言嵌入 (如 LASER、multilingual BERT)。这是跨语言信息检索 (CLIR) 的经典课题。
课后练习
处理词汇表外词 (OOV)。修改
compute_tf, 统计词汇表外词 (未在VOCAB中匹配到的) 的数量, 并在输出中报告。知识点提示: 在
compute_tf的break之前设置一个"已找到"标记。循环结束后若未找到, 累加 OOV 计数器。需传递额外的输出参数或使用全局变量。实现 BM25 简化版。在 TF-IDF 基础上实现简化的 BM25 分值:
score(d, t) = idf[t] * (tf[d][t] * (k+1)) / (tf[d][t] + k),k=1.5。用 BM25 替代 TF-IDF 重新计算余弦相似度, 比较差异。知识点提示: BM25 的 TF 饱和因子使高频词额外出现次数贡献递减。本题文档短 (每篇 4-5 词), BM25 效果不明显——需构造包含重复词的较长文档观察差异。
课后练习参考解答 (Exercise 1 & 2)
Exercise 1: OOV 追踪
c
static void compute_tf(char *tokens[], int n_tokens,
int tf[], int *oov_count) {
*oov_count = 0;
for (int t = 0; t < N_TERMS; t++) tf[t] = 0;
for (int i = 0; i < n_tokens; i++) {
int found = 0;
for (int j = 0; j < N_TERMS; j++) {
if (strcmp(tokens[i], VOCAB[j]) == 0) {
tf[j]++; found = 1; break;
}
}
if (!found) (*oov_count)++;
}
}Exercise 2: BM25 简化版
c
#define BM25_K 1.5
static void compute_bm25(int tf_matrix[N_DOCS][N_TERMS],
const double idf[],
double bm25[N_DOCS][N_TERMS]) {
for (int d = 0; d < N_DOCS; d++)
for (int t = 0; t < N_TERMS; t++) {
double tf = tf_matrix[d][t];
bm25[d][t] = idf[t] * (tf * (BM25_K + 1))
/ (tf + BM25_K);
}
}经典 TF-IDF 和 BM25 的主要差异出现在高 TF 词上——BM25 的 TF 增长是饱和的 (tf/(tf+k) 上界为 1)。本题所有 TF 值为 0 或 1, 两种方法结果相同。若要观察差异, 需构造包含重复词的更长文档。
参考资料
- Sparck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 11-21. — TF-IDF 的原始论文
- Salton, G., & Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing & Management, 24(5), 513-523. — 各种 TF 变体的系统比较
- Manning, C. D., Raghavan, P., & Schutze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. Chapter 6. — 向量空间模型与 TF-IDF 的完整教材
- Robertson, S., & Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4), 333-389. — BM25 的完整推6.
- Wikipedia: tf-idf, Cosine similarity, Vector space model
"The purpose of computing is insight, not numbers." — Richard Hamming