1. 简介
本文是关于字符串相似性度量概述文章的延续，重点介绍以下三种基于序列的相似性度量方法：
- 最长公共子串（Longest Common Substring）
- 最长公共子序列（Longest Common Subsequence）
- Gestalt 模式匹配（Gestalt Pattern Matching）
其中，最长公共子串（LCS） 与 最长公共子序列（LCSQ） 的主要区别在于：前者要求字符是连续的（即子串），而后者允许字符之间存在间隔（即子序列）。这两种方法都通过“公共长度”来衡量字符串的相似性。
而 Gestalt 模式匹配 则是基于最长公共子串递归地进行匹配，构建出一个更贴近人类认知的相似性度量。
2. 最长公共子串（Longest Common Substring）
在字符串相似性分析中，一种常用工具是找出两个字符串的最长公共子串（LCS）。公共子串越长，说明两个字符串越相似。
2.1. 动态规划实现
使用动态规划可以将时间复杂度优化到 **O(m × n)**，其中 m 和 n 分别是两个字符串的长度。该方法的核心是一个 (m+1) × (n+1) 的二维数组 dp，其中 dp[i][j] 表示以 X[i-1] 和 Y[j-1] 结尾的最长公共子串长度。
✅ 动态规划状态转移：
if (X[i-1] == Y[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
示例：
设两个字符串为：
- X = "ABABC"
- Y = "BABCA"
构造出的 DP 矩阵如下：
| B | A | B | C | A | ||
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 1 | 0 | 0 | 1 |
| B | 0 | 1 | 0 | 2 | 0 | 0 |
| A | 0 | 0 | 2 | 0 | 0 | 1 |
| B | 0 | 1 | 0 | 3 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 4 | 0 |
最大值为 4，对应的最长公共子串是 "ABCA"。
3. 最长公共子序列（Longest Common Subsequence）
与最长公共子串不同，最长公共子序列（LCSQ） 不要求字符连续。例如：
- 句子 1：The fox jumped over the high fence
- 句子 2：The quick brown fox jumped over the fence
最长公共子串是：
fox jumped over the
而最长公共子序列是：
The fox jumped over the fence
✅ 动态规划实现：
同样使用一个二维数组 dp[i][j] 表示 X 的前 i 个字符与 Y 的前 j 个字符的 LCSQ 长度。
if (X[i-1] == Y[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
时间复杂度同样是 **O(m × n)**。
4. Gestalt 模式匹配（Ratcliff/Obershelp）
Gestalt 模式匹配，也称 Ratcliff/Obershelp 相似性算法，是一种基于递归查找最长公共子串的字符串相似性度量方法。其核心公式如下：
$$ \text{Similarity} = \frac{2 \times K_m}{|S_1| + |S_2|} $$
其中：
- $ K_m $ 是匹配字符的总数
- $ |S_1| $ 和 $ |S_2| $ 分别是两个字符串的长度
✅ 匹配流程：
- 找出两个字符串的最长公共子串（LCS）
- 将字符串划分为左右两部分，在非匹配区域递归查找 LCS
- 累加所有匹配字符数 $ K_m $
- 套用公式计算相似度
示例：
比较两个字符串：
- S1 = "Pennsylvania"
- S2 = "Pencilvaneya"
- 初始 LCS 是 "lvan" → $ K_m = 2 × 4 = 8 $
- 左边匹配 "Pen" → $ K_m = 8 + 2 × 3 = 14 $
- 右边匹配 "a" → $ K_m = 14 + 2 × 1 = 16 $
最终相似度：
$$ \frac{2 \times 16}{12 + 12} = \frac{32}{24} = 0.66 $$
⚠️ 复杂度分析：
Gestalt 的时间复杂度依赖于 LCS 的实现，最坏情况下为 **O(n²)**，最好为 **O(n)**。
5. 小结
本文介绍了三种基于序列的字符串相似性度量方法：
| 方法 | 是否要求连续 | 时间复杂度 | 应用场景 |
|---|---|---|---|
| 最长公共子串（LCS） | ✅ 是 | O(m × n) | 精确匹配、局部相似性 |
| 最长公共子序列（LCSQ） | ❌ 否 | O(m × n) | 文本比较、模糊匹配 |
| Gestalt 模式匹配 | ❌ 否（递归 LCS） | O(n²) | 自然语言处理、模糊搜索 |
✅ 这些方法各有优劣，选择时应根据实际需求权衡：
- 要求精确匹配 → 用 LCS
- 允许字符间隔 → 用 LCSQ
- 需要更贴近人类感知的相似度 → 用 Gestalt
这些算法在文本比对、拼写检查、模糊搜索等领域有广泛应用。