基于编辑距离的文本相似度计算算法

字数 2613 2025-10-29 23:21:20

基于编辑距离的文本相似度计算算法

题目描述
编辑距离（Edit Distance），又称Levenshtein距离，是衡量两个字符串之间相似度的经典算法。它定义为将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。允许的编辑操作包括：插入一个字符、删除一个字符、替换一个字符。此算法在拼写检查、DNA序列比对、自然语言处理中的模糊匹配等场景有广泛应用。

解题过程

问题定义与目标
- 输入：两个字符串，记为 strA（长度为 m）和 strB（长度为 n）。
- 输出：一个整数，表示 strA 和 strB 之间的编辑距离。
- 核心思想：我们将通过动态规划来系统地解决这个问题。动态规划的核心是将大问题分解为相互关联的小问题（子问题），并存储子问题的解以避免重复计算。
定义动态规划状态
- 我们创建一个二维数组（或称为表格）dp，其维度为 (m+1) x (n+1)。dp[i][j] 表示子问题：字符串 strA 的前 i 个字符（即 strA[0:i]）与字符串 strB 的前 j 个字符（即 strB[0:j]）之间的编辑距离。
- 注意：i 和 j 的取值范围是从 0 到 m 和从 0 到 n。当 i=0 时，表示 strA 的前0个字符，即空字符串。
确定初始状态（边界条件）
- 这是动态规划的基石。我们需要考虑最简单的情况：
  - 情况1：当 strA 是空字符串时（i=0），要将空字符串转换为 strB 的前 j 个字符，唯一的方法就是连续插入 j 个字符。因此，dp[0][j] = j。
  - 情况2：当 strB 是空字符串时（j=0），要将 strA 的前 i 个字符转换为空字符串，唯一的方法就是连续删除 i 个字符。因此，dp[i][0] = i。
构建状态转移方程
- 这是算法的核心逻辑，用于填充 dp 表格中非边界的位置（i > 0 且 j > 0）。我们考虑如何从已知的更小的子问题的解，推导出当前子问题 dp[i][j] 的解。
- 对于 strA 的第 i 个字符（strA[i-1]，因为索引从0开始）和 strB 的第 j 个字符（strB[j-1]），我们有两种可能性：
  - 可能性A：两个字符相同。
    - 如果 strA[i-1] == strB[j-1]，那么最后一个字符不需要任何编辑操作。此时，dp[i][j] 的值完全等于去掉这最后一个相同字符后，两个子串的编辑距离，即 dp[i-1][j-1]。
  - 可能性B：两个字符不同。
    - 如果 strA[i-1] != strB[j-1]，我们必须执行一次编辑操作。这个操作有三种选择，我们选择代价最小的那种：
      1. 替换操作：将 strA[i-1] 替换为 strB[j-1]。这个操作的代价是1，然后问题就转化为求 strA[0:i-1] 和 strB[0:j-1] 的编辑距离，即 dp[i-1][j-1] + 1。
      2. 删除操作：从 strA 中删除字符 strA[i-1]。这个操作的代价是1，然后问题转化为求 strA[0:i-1] 和 strB[0:j] 的编辑距离，即 dp[i-1][j] + 1。
      3. 插入操作：在 strA 中插入字符 strB[j-1]。这个操作的代价是1，然后问题转化为求 strA[0:i] 和 strB[0:j-1] 的编辑距离，即 dp[i][j-1] + 1。
    - 我们取这三种操作可能的最小值：min(替换, 删除, 插入)
- 综合状态转移方程：
  dp[i][j] = {
  dp[i-1][j-1] if strA[i-1] == strB[j-1]
  min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) + 1 if strA[i-1] != strB[j-1]
  }
计算顺序与填表
- 为了计算 dp[i][j]，我们需要先知道它左方 dp[i][j-1]、上方 dp[i-1][j] 和左上方 dp[i-1][j-1] 的值。
- 因此，我们按行（i 从 0 到 m）和按列（j 从 0 到 n）的顺序来填充整个 dp 表格。这样能保证在计算每个单元格时，它所依赖的子问题的解都已经被计算出来了。
获取最终结果
- 当整个 dp 表格填充完毕后，表格最右下角的那个值 dp[m][n] 就是我们要求的最终结果：字符串 strA 和 strB 的整体编辑距离。

举例说明
以 strA = "kitten" 和 strB = "sitting" 为例（m=6, n=7）。

初始化：创建 dp[7][8] 表格。第一行 dp[0][j] = j，第一列 dp[i][0] = i。
填表（只展示关键步骤）：
- i=1, j=1: 比较 k 和 s，不同。dp[1][1] = min(dp[0][0], dp[0][1], dp[1][0]) + 1 = min(0, 1, 1) + 1 = 1。（用s替换k）
- i=2, j=2: 比较 i 和 i，相同。dp[2][2] = dp[1][1] = 1。
- i=3, j=3: 比较 t 和 t，相同。dp[3][3] = dp[2][2] = 1。
- i=4, j=4: 比较 t 和 i，不同。dp[4][4] = min(dp[3][3], dp[3][4], dp[4][3]) + 1。查表得 min(1, 2, 2) + 1 = 2。（在kitt后插入i，或将t替换为i）
- ... 继续此过程直到填满表格。
结果：最终 dp[6][7] = 3。转换过程为：kitten -> sitten (替换k为s) -> sittin (替换e为i) -> sitting (在末尾插入g)。

基于编辑距离的文本相似度计算算法题目描述编辑距离（Edit Distance），又称Levenshtein距离，是衡量两个字符串之间相似度的经典算法。它定义为将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。允许的编辑操作包括：插入一个字符、删除一个字符、替换一个字符。此算法在拼写检查、DNA序列比对、自然语言处理中的模糊匹配等场景有广泛应用。解题过程问题定义与目标输入：两个字符串，记为 strA （长度为 m ）和 strB （长度为 n ）。输出：一个整数，表示 strA 和 strB 之间的编辑距离。核心思想：我们将通过动态规划来系统地解决这个问题。动态规划的核心是将大问题分解为相互关联的小问题（子问题），并存储子问题的解以避免重复计算。定义动态规划状态我们创建一个二维数组（或称为表格） dp ，其维度为 (m+1) x (n+1) 。 dp[i][j] 表示子问题：字符串 strA 的前 i 个字符（即 strA[0:i] ）与字符串 strB 的前 j 个字符（即 strB[0:j] ）之间的编辑距离。注意： i 和 j 的取值范围是从 0 到 m 和从 0 到 n 。当 i=0 时，表示 strA 的前0个字符，即空字符串。确定初始状态（边界条件）这是动态规划的基石。我们需要考虑最简单的情况：情况1 ：当 strA 是空字符串时（ i=0 ），要将空字符串转换为 strB 的前 j 个字符，唯一的方法就是连续插入 j 个字符。因此， dp[0][j] = j 。情况2 ：当 strB 是空字符串时（ j=0 ），要将 strA 的前 i 个字符转换为空字符串，唯一的方法就是连续删除 i 个字符。因此， dp[i][0] = i 。构建状态转移方程这是算法的核心逻辑，用于填充 dp 表格中非边界的位置（ i > 0 且 j > 0 ）。我们考虑如何从已知的更小的子问题的解，推导出当前子问题 dp[i][j] 的解。对于 strA 的第 i 个字符（ strA[i-1] ，因为索引从0开始）和 strB 的第 j 个字符（ strB[j-1] ），我们有两种可能性：可能性A：两个字符相同。如果 strA[i-1] == strB[j-1] ，那么最后一个字符不需要任何编辑操作。此时， dp[i][j] 的值完全等于去掉这最后一个相同字符后，两个子串的编辑距离，即 dp[i-1][j-1] 。可能性B：两个字符不同。如果 strA[i-1] != strB[j-1] ，我们必须执行一次编辑操作。这个操作有三种选择，我们选择代价最小的那种：替换操作：将 strA[i-1] 替换为 strB[j-1] 。这个操作的代价是1，然后问题就转化为求 strA[0:i-1] 和 strB[0:j-1] 的编辑距离，即 dp[i-1][j-1] + 1 。删除操作：从 strA 中删除字符 strA[i-1] 。这个操作的代价是1，然后问题转化为求 strA[0:i-1] 和 strB[0:j] 的编辑距离，即 dp[i-1][j] + 1 。插入操作：在 strA 中插入字符 strB[j-1] 。这个操作的代价是1，然后问题转化为求 strA[0:i] 和 strB[0:j-1] 的编辑距离，即 dp[i][j-1] + 1 。我们取这三种操作可能的最小值： min(替换, 删除, 插入) 综合状态转移方程： dp[i][j] = { dp[i-1][j-1] if strA[i-1] == strB[j-1] min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) + 1 if strA[i-1] != strB[j-1] } 计算顺序与填表为了计算 dp[i][j] ，我们需要先知道它左方 dp[i][j-1] 、上方 dp[i-1][j] 和左上方 dp[i-1][j-1] 的值。因此，我们按行（ i 从 0 到 m ）和按列（ j 从 0 到 n ）的顺序来填充整个 dp 表格。这样能保证在计算每个单元格时，它所依赖的子问题的解都已经被计算出来了。获取最终结果当整个 dp 表格填充完毕后，表格最右下角的那个值 dp[m][n] 就是我们要求的最终结果：字符串 strA 和 strB 的整体编辑距离。举例说明以 strA = "kitten" 和 strB = "sitting" 为例（m=6, n=7）。初始化：创建 dp[7][8] 表格。第一行 dp[0][j] = j ，第一列 dp[i][0] = i 。填表（只展示关键步骤）： i=1, j=1 : 比较 k 和 s ，不同。 dp[1][1] = min(dp[0][0], dp[0][1], dp[1][0]) + 1 = min(0, 1, 1) + 1 = 1 。（用 s 替换 k ） i=2, j=2 : 比较 i 和 i ，相同。 dp[2][2] = dp[1][1] = 1 。 i=3, j=3 : 比较 t 和 t ，相同。 dp[3][3] = dp[2][2] = 1 。 i=4, j=4 : 比较 t 和 i ，不同。 dp[4][4] = min(dp[3][3], dp[3][4], dp[4][3]) + 1 。查表得 min(1, 2, 2) + 1 = 2 。（在 kitt 后插入 i ，或将 t 替换为 i ） ... 继续此过程直到填满表格。结果：最终 dp[6][7] = 3 。转换过程为：kitten -> sitten (替换k为s) -> sittin (替换e为i) -> sitting (在末尾插入g)。