每日算法 — 使用java实现拼写检查：Levenshtein动态规划与BK树快速检索

拼写检查是现代软件系统的标配功能，从搜索引擎的”您是不是要找”到IDE的自动纠错，其底层依赖的是高效的字符串相似度算法。本文将用Java实现一个完整的拼写检查系统，核心讲解Levenshtein编辑距离的动态规划解法，以及BK树（Burkhard-Keller Tree）如何在大规模词典中实现亚线性时间的模糊检索。

一、Levenshtein 编辑距离

编辑距离定义：将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。

1.1 动态规划状态定义

设 dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最小编辑距离。

状态转移方程：
– 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
– 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
– dp[i-1][j] + 1：删除 word1[i-1]
– dp[i][j-1] + 1：插入 word2[j-1]
– dp[i-1][j-1] + 1：替换 word1[i-1] 为 word2[j-1]

1.2 Java 实现

public class LevenshteinDistance {

    public static int calculate(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // 空间优化：只保留两行
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        // 初始化第一行：将空字符串转为 word2[0..j-1] 需要 j 次插入
        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            curr[0] = i; // 将 word1[0..i-1] 转为空字符串需要 i 次删除

            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = prev[j - 1]; // 字符相同，无需操作
                } else {
                    curr[j] = Math.min(Math.min(
                        prev[j] + 1,      // 删除
                        curr[j - 1] + 1), // 插入
                        prev[j - 1] + 1   // 替换
                    );
                }
            }

            // 交换两行
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }

        return prev[n];
    }
}

1.3 时间复杂度分析

• 时间复杂度：O(m × n)，其中 m、n 为两个字符串长度
• 空间复杂度：O(min(m, n))，通过滚动数组优化

二、BK树： metric tree 加速模糊检索

当词典包含数十万词汇时，对每个输入词都计算与所有词条的编辑距离是不可接受的。BK树利用编辑距离的三角不等式性质，将检索复杂度从 O(N) 降至 O(log N) 级别。

2.1 三角不等式

编辑距离满足度量空间的三角不等式：
d(a, b) ≤ d(a, c) + d(c, b)

推论：若查询词 q 与词条 t 的距离为 d，则任何与 t 距离不在 [d - maxDist, d + maxDist] 范围内的词条都不可能与 q 的距离 ≤ maxDist。

2.2 BK树节点结构

public class BKNode {
    private final String word;
    // 子节点：key 为该子节点与当前节点的编辑距离
    private final Map<Integer, BKNode> children;

    public BKNode(String word) {
        this.word = word;
        this.children = new HashMap<>();
    }

    public void addChild(int distance, BKNode child) {
        children.put(distance, child);
    }

    public BKNode getChild(int distance) {
        return children.get(distance);
    }

    public String getWord() { return word; }
    public Map<Integer, BKNode> getChildren() { return children; }
}

2.3 BK树构建

public class BKTree {
    private BKNode root;

    public void insert(String word) {
        if (root == null) {
            root = new BKNode(word);
            return;
        }
        insertNode(root, word);
    }

    private void insertNode(BKNode node, String word) {
        int dist = LevenshteinDistance.calculate(node.getWord(), word);

        if (dist == 0) return; // 已存在

        BKNode child = node.getChild(dist);
        if (child == null) {
            node.addChild(dist, new BKNode(word));
        } else {
            insertNode(child, word);
        }
    }
}

2.4 BK树检索

public List<String> search(String query, int maxDistance) {
    List<String> results = new ArrayList<>();
    if (root == null) return results;

    searchNode(root, query, maxDistance, results);
    return results;
}

private void searchNode(BKNode node, String query, int maxDist, List<String> results) {
    int dist = LevenshteinDistance.calculate(node.getWord(), query);

    if (dist <= maxDist) {
        results.add(node.getWord());
    }

    // 利用三角不等式剪枝：只搜索距离在 [dist - maxDist, dist + maxDist] 范围内的子树
    int start = Math.max(1, dist - maxDist);
    int end = dist + maxDist;

    for (Map.Entry<Integer, BKNode> entry : node.getChildren().entrySet()) {
        int childDist = entry.getKey();
        if (childDist >= start && childDist <= end) {
            searchNode(entry.getValue(), query, maxDist, results);
        }
    }
}

三、完整拼写检查系统

public class SpellChecker {
    private final BKTree dictionary;
    private static final int DEFAULT_MAX_DIST = 2;

    public SpellChecker(List<String> words) {
        this.dictionary = new BKTree();
        for (String word : words) {
            dictionary.insert(word.toLowerCase());
        }
    }

    public boolean isCorrect(String word) {
        List<String> exact = dictionary.search(word.toLowerCase(), 0);
        return !exact.isEmpty();
    }

    public List<Suggestion> getSuggestions(String word, int maxSuggestions) {
        String target = word.toLowerCase();

        // 分层搜索：先搜索距离1，再搜索距离2
        List<Suggestion> results = new ArrayList<>();

        for (int dist = 1; dist <= DEFAULT_MAX_DIST && results.size() < maxSuggestions; dist++) {
            List<String> matches = dictionary.search(target, dist);
            for (String match : matches) {
                results.add(new Suggestion(match, dist));
                if (results.size() >= maxSuggestions) break;
            }
        }

        // 按编辑距离排序
        results.sort(Comparator.comparingInt(Suggestion::getDistance));
        return results;
    }
}

public class Suggestion {
    private final String word;
    private final int distance;

    public Suggestion(String word, int distance) {
        this.word = word;
        this.distance = distance;
    }

    public String getWord() { return word; }
    public int getDistance() { return distance; }

    @Override
    public String toString() {
        return word + " (distance=" + distance + ")";
    }
}

四、使用示例

public class Main {
    public static void main(String[] args) {
        List<String> dictionary = Arrays.asList(
            "algorithm", "algorithmic", "rhythm", "logarithm",
            "java", "javascript", "python", "programming",
            "dynamic", "programming", "distance", "edit"
        );

        SpellChecker checker = new SpellChecker(dictionary);

        String misspelled = "algoritm";
        System.out.println("Input: " + misspelled);

        if (!checker.isCorrect(misspelled)) {
            System.out.println("Did you mean:");
            checker.getSuggestions(misspelled, 5).forEach(System.out::println);
        }
        // Output: algorithm (distance=1)
    }
}

五、进阶优化

5.1 Damerau-Levenshtein 距离

支持相邻字符交换（transposition）操作，更符合人类拼写错误模式：

// 当 s1[i-1] == s2[j-2] 且 s1[i-2] == s2[j-1] 时
// dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) // 交换

5.2 加权编辑距离

根据键盘布局给不同编辑操作赋予不同权重（如将 ‘a’ 错打成 ‘s’ 的代价低于 ‘a’ 错打成 ‘z’）。

六、总结

拼写检查系统串联了动态规划（编辑距离计算）与度量空间索引（BK树检索）两大算法思想。Levenshtein距离的 O(mn) 解法是最经典的DP入门题之一，而BK树则展示了如何利用数学性质（三角不等式）在搜索空间中进行高效剪枝，这一思想在近似最近邻搜索（ANN）领域有着广泛的应用。