The Levenshtein Distance Algorithm

The Levenshtein Distance（编辑距离）

  • 定义：仅仅使用 插入、删除、替换 一个字符的方式将一个字符串转换为另一个字符串所需要的最少的操作数。

  • 用途：DNA相似度测量、diff 命令、模糊搜索等

处理两个字符串的动态规划问题，一般是使用双指针分别指向字符串的末尾，然后向前缩小问题的规模

Algorithm

对于两个字符串 s、t的每一对字符s[i]、t[j]，共有如下四种操作：

  1. match s[i].cmp(t[j]) {
  2.     Equal => {
  3.         i += 1;
  4.         j += 1;
  5.     }
  6.     _ => 在 insert, delete, replace 中选取一种编辑距离最小的操作
  7. }

可以使用递归的方式进行解决：

  1. fn levenshtein_distance<'a>(s: &'a str, t: &'a str) -> usize {
  2.     fn dp(i: usize, j: usize) -> usize {
  3.         if i == -1 {
  4.             j + 1    // 若一个字符长度为0,那么另一个字符需要修改 j + 1 次
  5.         } else if j == -1 {
  6.             i + 1
  7.         } else {
  8.             match s[i].cmp(t[j]) {
  9.                 Equal => dp(i - 1, j - 1),    // 两个字符相同，不需要进行处理
  10.                 _ => min(
  11.                     dp(i, j - 1) + 1,    // 在 s 中插入 t[j]
  12.                     dp(i - 1, j) + 1,    // 在 s 中删除 s[i]
  13.                     dp(i - 1, j - 1) + 1,    // 将 s[i] 替换为 t[j]
  14.                 ),
  15.             }
  16.         }
  17.     }
  18.     dp(s.len() - 1, t.len() -1)    // 从字符串的末尾向前缩小规模
  19. }

以上算法存在 重叠子 问题：多个小问题被重复计算

上述算法的递归框架：

  1. fn dp(i, j):
  2.     dp(i - 1, j - 1)
  3.     dp(i, j - 1)
  4.     dp(i - 1, j)

对于子问题dp(i - 1, j - 1)，有多个不同的路径可以到达，因而存在重叠子问题

Optimize

共有两种优化方法：

  1. 备忘录方法（记忆化搜索）
  2. DP Table

备忘录方法

存储每一步运行的结果，若运行结果存在于存储列表中，则不进行计算直接返回

DP Table

DP Table 是一个二维数组——将递归转为二维数组进行运算

唯一的不同：DP Table 是自底向上求解，而递归是自顶向下求解

处理动态规划问题最好建立 DP Table（容易找出状态转移的关系）

  • 进一步优化：由于每一个新的状态都只与另外三个状态有关，因此，可以将二维数组优化为三个变量