文本相似度计算指南：Levenshtein 编辑距离与 Jaccard 相似度

2026年7月12日 #文本相似度 #Levenshtein #Jaccard #LCS #动态规划 #工具矩阵

文本相似度的四种计算方法

文本相似度计算是自然语言处理、数据清洗、查重检测等领域的基础技术。不同的相似度算法侧重点不同——有的关注字符级精确差异，有的关注词汇集合重叠，有的关注结构序列相似性。

配套工具：文本相似度对比工具

四种指标对比

指标	计算粒度	范围	适用场景
Levenshtein 编辑距离	字符级	0~∞	拼写纠错、模糊匹配
相似度比率	字符级	0~100%	直观判断相似程度
Jaccard 相似度	词汇级	0~100%	文档查重、主题相似性
LCS 相似度	字符级	0~100%	版本对比、结构相似性

Levenshtein 编辑距离

算法原理

Levenshtein 编辑距离是指将字符串 A 转换为字符串 B 所需的最少单字符编辑操作次数。允许的三种操作：

插入（Insert）：添加一个字符
删除（Delete）：移除一个字符
替换（Substitute）：将一个字符替换为另一个

例如 “kitten” → “sitting” 的编辑距离为 3：

k → s（替换）
e → i（替换）
末尾插入 g

动态规划实现

使用 dp[i][j] 表示 A 的前 i 个字符与 B 的前 j 个字符的编辑距离：

dp[0][j] = j          // A 为空，需插入 j 个字符
dp[i][0] = i          // B 为空，需删除 i 个字符
dp[i][j] = min(
  dp[i-1][j] + 1,     // 删除 A[i]
  dp[i][j-1] + 1,     // 插入 B[j]
  dp[i-1][j-1] + cost // 替换（cost=0 若相同，否则 1）
)

空间优化

标准实现需要 O(m×n) 空间。使用滚动数组优化——只保留当前行和上一行，空间降至 O(min(m, n))：

let prev = new Array(bLen + 1);
let curr = new Array(bLen + 1);
// 每轮迭代交换 prev 和 curr
[prev, curr] = [curr, prev];

相似度比率 = 1 - distance / max(lenA, lenB)，范围 0~1，值越大越相似。

Jaccard 相似度与词汇比较

集合论基础

Jaccard 相似度衡量两个集合的重叠程度：

J(A, B) = |A ∩ B| / |A ∪ B|

值域 0~1：0 表示完全不相交，1 表示完全相同。

分词策略

文本相似度计算的第一步是分词。本工具使用 Unicode 属性转义 \p{L}\p{N} 匹配所有语言的字母和数字：

const tokens = text.match(/[\p{L}\p{N}]+/gu);

这种分词方式的优势：

中英文混合：中文按连续字符分组，英文按单词分组
标点过滤：标点符号自然被排除
Unicode 感知：正确处理日文、韩文、emoji 等

与编辑距离的区别

Jaccard 基于集合，忽略词序和重复次数：

“猫追狗” 和 “狗追猫” → Jaccard = 1.0（词汇完全相同）
“猫追狗” 和 “狗追猫” → 编辑距离 > 0（字符顺序不同）

查重场景建议同时参考两个指标：Jaccard 高但编辑距离大 = 主题相似但表述不同。

最长公共子序列（LCS）

子序列 vs 子串

子串（Substring）：连续的字符序列
子序列（Subsequence）：不要求连续，但保持相对顺序

例如 “ACE” 是 “ABCDE” 的子序列但不是子串。

动态规划算法

dp[i][j] = 0                           // 若 i=0 或 j=0
         = dp[i-1][j-1] + 1            // 若 A[i] = B[j]
         = max(dp[i-1][j], dp[i][j-1]) // 否则

差异高亮实现

LCS 的另一个用途是生成字符级差异高亮。通过回溯 DP 表，将两段文本切分为三类片段：

公共部分（equal）：LCS 中的字符
删除部分（removed）：A 中有但 B 中无
新增部分（added）：B 中有但 A 中无

相邻同类型片段自动合并，减少 DOM 渲染节点。这与 Git 的 diff 算法原理相同。

实际应用场景

1. 论文查重辅助

快速判断两段文本的相似程度。Jaccard 高 + 编辑距离小 → 可能存在抄袭；Jaccard 低 → 主题不同。

2. 数据清洗与去重

在大型数据集中查找相似记录。例如用户地址去重：编辑距离 ≤ 3 的记录可能是同一条地址的不同录入。

3. 模糊匹配

搜索引擎的”您是不是要找”功能。计算用户输入与候选词的编辑距离，距离最小的作为建议。

4. 代码版本对比

LCS 算法是 Git diff 的核心。通过比较两个版本的代码，高亮新增和删除的行。

5. SEO 内容原创度检查

判断新内容是否与已有文章过度相似。Jaccard 相似度 > 80% 可能被搜索引擎视为重复内容。

6. 翻译质量评估

对比机翻与人翻的文本。LCS 相似度高表示译文结构忠实原文，低表示译文做了较大调整。

性能考量与总结

时间复杂度

算法	时间复杂度	空间复杂度（优化后）
Levenshtein	O(m×n)	O(min(m,n))
Jaccard	O(m+n)	O(m+n)
LCS	O(m×n)	O(min(m,n))

对于超长文本（>10000 字符），Levenshtein 和 LCS 的 O(m×n) 复杂度可能影响性能。Jaccard 的 O(m+n) 复杂度更适合大规模文本比较。

预处理的重要性

预处理选项（大小写、空白、空行）对结果影响很大：

大小写不敏感：适合代码标识符、文件名比较
去除空白：适合缩进不规范的文本
忽略空行：适合段落结构不同的文本

所有预处理在计算前统一应用，确保各指标基于同一规范化文本。

工具推荐

文本相似度对比工具：四指标实时计算 + 差异高亮
文本对比工具（Diff）：行级差异对比，适合代码版本比较
文本去重工具：基于精确匹配的行级去重
文本统计分析：字数、词数、关键词频率分析

选择合适的相似度算法，关键在于理解各算法的侧重点：字符级精确性（Levenshtein）、词汇集合重叠（Jaccard）、结构序列相似（LCS）。根据实际场景选择最合适的指标。