1. 简介
在本教程中，我们将深入讲解 字符串相似性度量 中提到的基于 Token 的相似性度量方法。
属于这一类别的算法本质上是集合相似性算法，其中集合由字符串的 Token 构成。我们将重点探讨以下几种算法：
- Q-Grams
- 重叠系数（Overlap Coefficient）
- Jaccard 相似度
- Dice 系数
后三种度量方法基于集合相似性。
2. Token 方法概述
基于 Token 的字符串相似性度量通常包括以下三个步骤：
- Token 提取：分析待比较的文本字符串，定义一组 Token（即字符字符串的集合）
- 计数：统计每组 Token 在各自字符串中出现的次数
- 度量计算：利用这些计数来计算相似性或距离度量
一些方法（如 Q-Grams）对 Token 的生成方式有特定要求，而其他方法则允许我们自定义 Token。例如，在普通文本中，可以将单个单词作为 Token。
Token 的计数方式也多种多样。一种方式是统计每个 Token 在文本中的出现次数，文本的相似性就通过这些差异来体现。
我们也可以使用集合论的方法来衡量 Token 的使用情况。这类方法属于集合相似性度量，它们通过比较两个集合之间的相似性来进行判断。在我们的场景中，这些集合由 Token 构成。
Token 计数如何组合成最终的相似性度量是区分不同方法的关键。所有方法最终都会输出一个介于 0 和 1 之间的数值。
3. 文本的近似表示
所有 Token 方法共有的一个特性是：我们将文本视为 Token 的集合，而不关心这些 Token 在文本中的具体位置。
例如，假设我们有两个文本：
- “Hello World”
- “World Hello”
如果我们以 “Hello” 和 “World” 作为 Token，这两个文本将获得相同的评分。虽然 Token 的顺序不同，但它们的内容相同。这是为实现高效文本比较所付出的代价。
4. Q-Grams 方法
Q-Grams 是一种 Token 生成方式非常明确的方法。我们通过统计这些 Token 的出现次数，并计算它们在不同文本中的差异来衡量相似性。
Q-Gram 是一个长度为 q 的连续字符序列。我们通过统计两个字符串中每个长度为 q 的子串的出现次数，然后计算它们之间的绝对差值之和来衡量相似性。数值越小，字符串越相似。
如果两个字符串完全相同，则 Token 计数相同，差值为零；如果它们没有共同的 Token，则差值会很大（即每个字符串中所有 Token 出现次数之和）。
更形式化地，设 $ P_q(A)[i] $ 表示字符串 A 中第 i 个 q-Gram 的出现次数，字符串 A 和 B 的距离度量为：
$$ dist_{q-gram}(A,B) = \sum_{i_1}^{\sigma^{q}}\left|P_q(A)[i] - P_q(B)[i]\right| $$
5. 集合相似性度量
集合相似性度量方法基于 Token 的集合进行比较。它们并不指定 Token 的具体生成方式，因此我们可以自由选择，比如使用 n-Grams。
5.1 集合运算
一旦定义了 Token，我们就可以用集合论的方式统计它们的差异。以下是几个关键的集合运算：
- 集合 A 的大小：$|A|$
- 集合 A 与 B 的交集大小：$|A \cap B|$
- 集合 A 与 B 的并集大小：$|A \cup B|$
这些运算是集合相似性度量的基础。
5.2 集合相似性指标
集合相似性度量的核心在于计算两个集合的交集大小，然后通过不同的方式归一化，使其落在 0 到 1 的范围内。
常见指标如下：
✅ 重叠系数（Overlap Coefficient）
$$ overlap(A,B) = \frac{|A \cap B|}{\min(|A|, |B|)} $$
✅ Jaccard 相似度（Jaccard Index）
$$ J(A,B) = \frac{|A \cap B|}{|A \cup B|} = \frac{|A \cap B|}{|A| + |B| - |A \cap B|} $$
对应的 Jaccard 距离（Jaccard Distance） 为：
$$ distance(A,B) = 1 - J(A,B) $$
✅ Dice 系数（Dice Coefficient）
$$ DSC(A,B) = \frac{2|A \cap B|}{|A| + |B|} $$
三者的区别主要在于归一化方式不同。
6. 示例
我们以以下三段文本为例：
- A: “brave new world”
- B: “hello world”
- C: “hello new world”
我们分别使用两种 Token 方法进行比较：
方法一：单词 Token
Token 列表为：
$$ brave,\ new,\ world,\ hello $$
统计结果如下：
| 文本 | brave | new | world | hello |
|---|---|---|---|---|
| A | 1 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 1 |
| C | 0 | 1 | 1 | 1 |
方法二：2-Gram Token
Token 列表为：
$$ br,\ ra,\ av,\ ve,\ ne,\ ew,\ wo,\ or,\ rl,\ ld,\ he,\ el,\ ll,\ lo $$
统计结果如下：
| 文本 | br | ra | av | ve | ne | ew | wo | or | rl | ld | he | el | ll | lo |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| C | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
计算结果对比
| 指标 | A vs B | A vs C | B vs C |
|---|---|---|---|
| Q-Grams 距离（单词） | 3 | 4 | 2 |
| Q-Grams 距离（n-Grams） | 10 | 7 | 3 |
| 重叠系数（单词） | 0.5 | 0.66 | 1.0 |
| 重叠系数（n-Grams） | 0.5 | 0.60 | 1.0 |
| Jaccard 相似度（单词） | 0.25 | 0.5 | 0.66 |
| Jaccard 相似度（n-Grams） | 0.28 | 0.42 | 0.80 |
| Dice 系数（单词） | 0.25 | 0.66 | 0.80 |
| Dice 系数（n-Grams） | 0.44 | 0.60 | 0.89 |
从结果可以看出，尽管数值不同，但所有方法都一致认为 “brave new world” 和 “hello new world” 最相似，而 “hello world” 差异最大。
7. 小结
基于 Token 的字符串相似性度量是字符串相似性方法的一个子集。它通过将字符串拆分为 Token 并进行统计来实现比较。
我们探讨了以下几种方法：
- Q-Grams：提供了一种特定的 Token 生成方式和度量方法
- 重叠系数、Jaccard 相似度、Dice 系数：基于集合相似性，区别在于归一化方式
虽然这些方法在具体数值上有所不同，但都能有效反映字符串之间的相似性趋势。
✅ 踩坑提醒：
- Token 顺序不影响结果，可能导致误判语义
- 不同归一化方式对结果影响较大，需根据场景选择合适的度量方法
⚠️ 建议：
- 对于结构化文本，建议使用单词 Token
- 对于非结构化或部分结构化文本，推荐使用 n-Grams
最终，选择哪种方法取决于具体应用场景以及对性能和精度的权衡。