本文介绍最小编辑距离（Edit Distance）的原理、标准算法实现，并进一步探讨在处理中文字符串时的特殊处理方法。

一、最小编辑距离简介

最小编辑距离（Minimum Edit Distance）是衡量两个字符串相似度的经典算法之一，其核心思想是：将一个字符串转换成另一个字符串所需的最少操作数。

典型的允许操作包括：

  • 插入（Insert）
  • 删除（Delete）
  • 替换（Replace）

该算法常用于拼写纠错、字符串模糊匹配、自然语言处理等领域。

二、经典动态规划算法

leetcode题目链接

72. 编辑距离

设 dp[i][j] 表示将字符串 A[0...i-1] 转换成字符串 B[0...j-1] 所需的最小操作数。

转移方程为：

1
2
3
4
5
dp[i][j] = min(
    dp[i-1][j] + 1,         // 删除 A[i-1]
    dp[i][j-1] + 1,         // 插入 B[j-1]
    dp[i-1][j-1] + cost     // 替换 A[i-1] 为 B[j-1]（若不同）
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n + 1 , vector<int>(m +1, 0));
        for (int i  = 0; i <= n; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= m; j++){
            dp[0][j] = j;
        }
        for(int i =1; i <= n; i++){
            for (int j = 1; j<= m; j++){
                if (word1[i - 1] == word2[j -1]){
                    dp[i][j] =dp[i -1][j -1];
                }else 
                {
                    dp[i][j] = min({dp[i - 1][j - 1] , dp[i][j -1] , dp[i -1][j] }) + 1;
                }
            }
        }

        return dp[n][m];
    }
};

三、中文字符串的挑战

中文字符串使用 UTF-8 编码，一个汉字通常占用 3 个字节，不能直接用英文的处理方式。

四、中文处理方法：按 UTF-8 字符划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::vector<std::string> splitUtf8String(const std::string& str) {
    std::vector<std::string> result;
    size_t i = 0;
    while (i < str.size()) {
        unsigned char c = str[i];
        size_t len = 1;
        if ((c & 0x80) == 0x00) len = 1;
        else if ((c & 0xE0) == 0xC0) len = 2;
        else if ((c & 0xF0) == 0xE0) len = 3;
        else if ((c & 0xF8) == 0xF0) len = 4;
        result.emplace_back(str.substr(i, len));
        i += len;
    }
    return result;
}

或者使用 utf8cpp 项目 中的utf8.h头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <utf8.h>         // 使用 utf8cpp 库
#include <string>
#include <vector>

std::vector<std::string> splitUtf8String(const std::string& str) {
    std::vector<std::string> result;
    auto it = str.begin();
    auto end = str.end();

    while (it != end) {
        auto next_it = it;
        utf8::next(next_it, end); // 移动一个 UTF-8 字符的长度
        result.emplace_back(it, next_it); // [it, next_it) 是一个完整字符
        it = next_it;
    }

    return result;
}

五、中文支持下的最小编辑距离实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int editDistanceUtf8(const std::string& a, const std::string& b) {
    auto va = splitUtf8String(a);
    auto vb = splitUtf8String(b);
    int n = va.size(), m = vb.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = (va[i - 1] == vb[j - 1]) ? 0 : 1;
            dp[i][j] = std::min({
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + cost
            });
        }
    }
    return dp[n][m];
}

六、实际应用：拼写纠错 & 相似词推荐

  • 用户输入“计算姬”，推荐“计算机”
  • 输入“人共”，推荐“人工”、“人工智能”
  • 用于搜索引擎的容错查询、模糊匹配等

七、小结

项目 英文字符串 中文字符串（UTF-8）
字符单位 char utf-8 字符串（最多 4 字节）
拆分方式 按 char 用 splitUtf8String()
算法核心 动态规划 相同，只是输入类型变了
实际应用 拼写纠错、模糊匹配 中文搜索、拼音误输入修复

八、参考资料