最小编辑距离算法

算法理论

1. 问题定义：
   给定“老字符串”和“新字符串”，最小编辑距离是将老字符串变成新字符串所需的最少编辑操作次数。
2. 允许的操作：
   
   • 插入（Insert）：在任意位置插入一个字符
   • 删除（Delete）：删除任意一个字符
   • 替换（Replace）：将一个字符替换为另一个字符
3. 动态规划思想：
   用 dp[i][j] 表示老字符串的前i个字符变成新字符串的前j个字符的最小编辑距离。
   其中 i 和 j 都是从 0 开始计数的，i=0、j=0 对应空串，i 和 j 表示“前i/前j个字符”。
   初始条件：
   dp[0][j] = j（老字符串为空，需插入j次）
   dp[i][0] = i（新字符串为空，需删除i次）
4. 状态转移方程：
   
   \[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1], & \text{如果 } \text{老字符串}[i-1]=\text{新字符串}[j-1] \\ 1+\min\{\text{dp}[i-1][j],\ \text{dp}[i][j-1],\ \text{dp}[i-1][j-1]\}, & \text{否则} \end{cases} \]
   
   注意：i 和 j 都是从 0 开始的，dp[i][j] 表示老字符串的前 i 个字符和新字符串的前 j 个字符。
   详细解释：
   
   • 1. 如果老字符串的第 i 个字符和新字符串的第 j 个字符相同：
     不需要任何操作，直接继承左上角（dp[i-1][j-1]）的值。
   • 2. 如果不同：
     需要在三种操作中选择最优（最少步数）：
     • 删除（dp[i-1][j] + 1）：把老字符串的第 i 个字符删掉，问题变成前 i-1 个字符和新字符串的前 j 个字符的编辑距离，再加 1 步删除操作。
     • 插入（dp[i][j-1] + 1）：在老字符串末尾插入新字符串的第 j 个字符，问题变成老字符串的前 i 个字符和新字符串的前 j-1 个字符的编辑距离，再加 1 步插入操作。
     • 替换（dp[i-1][j-1] + 1）：把老字符串的第 i 个字符替换成新字符串的第 j 个字符，问题变成前 i-1 个字符和前 j-1 个字符的编辑距离，再加 1 步替换操作。
     取这三种操作中步数最少的那一个。
   • 举例说明：
     假设老字符串是“bus”，新字符串是“cats”，现在计算 dp[2][3]，即“bu”变成“cat”的最小编辑距离：
     
     • 如果“u”和“t”不同，可以选择：
       删除“u”（看“b”变“cat”）、插入“t”（看“bu”变“ca”）、替换“u”为“t”（看“b”变“ca”），三者取最小值+1。
5. 复杂度分析：
   时间复杂度：O(mn)，空间复杂度：O(mn)，其中m和n分别为老字符串和新字符串的长度。
6. 典型应用场景：
   
   • 拼写纠错（如输入法、搜索引擎）
   • DNA/蛋白质序列比对
   • 自然语言处理中的文本相似度计算
   • 版本控制中的差异比较