拼写检查器：让程序学会“纠错”

拼写检查器，说白了就是让计算机帮你检查单词有没有写错。你想想看，平时在Word里打字，底下出现红色波浪线，那就是拼写检查器在工作。今天我们就来亲手实现一个。

我个人习惯把这类项目分成三步走：词典加载 → 错误检测 → 纠错建议。嗯，咱们一步步来拆解。

核心思路：编辑距离

拼写检查的核心算法，叫做编辑距离（Levenshtein Distance）。它衡量的是两个字符串之间，通过插入、删除、替换操作，最少需要几步才能变成一样。

举个例子：

• "cat" → "cats"：插入一个's'，距离为1
• "cat" → "cut"：替换'a'为'u'，距离为1
• "cat" → "dog"：替换三个字符，距离为3

我在项目中遇到过用户输入"recieve"（正确拼写是"receive"），编辑距离就是1（交换'e'和'i'的位置）。这种错误非常常见。

数据结构设计

词典怎么存？我建议用std::unordered_set<std::string>。为什么？因为查找速度是O(1)，你想想看，几十万单词的词典，用线性查找就太慢了。

class SpellChecker {
private:
    std::unordered_set<std::string> dictionary;
    std::vector<std::string> wordList;  // 用于生成候选词
    
public:
    bool loadDictionary(const std::string& filename);
    bool check(const std::string& word);
    std::vector<std::string> suggest(const std::string& word, int maxDistance = 2);
};

这里我额外存了一份wordList，因为生成候选词时需要遍历所有单词。用set存一份用于快速检查，用vector存一份用于遍历，各司其职。

编辑距离算法实现

动态规划实现编辑距离，经典得不能再经典了。直接上代码：

int levenshteinDistance(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + std::min({
                    dp[i-1][j],    // 删除
                    dp[i][j-1],    // 插入
                    dp[i-1][j-1]   // 替换
                });
            }
        }
    }
    return dp[m][n];
}

这段代码我写过不下五十遍了。注意那个std::min({...})的写法，C++11之后才支持，老项目里得拆开写三个min嵌套。

生成候选词

检查一个词是否拼写错误很简单——查词典就行。关键是纠错建议怎么给。

我的做法是：

1. 先找编辑距离为1的候选词
2. 如果没找到，再找距离为2的
3. 按距离排序，距离相同的按词频排序（如果有词频数据）

std::vector<std::string> SpellChecker::suggest(const std::string& word, int maxDistance) {
    std::vector<std::pair<int, std::string>> candidates;
    
    for (const auto& dictWord : wordList) {
        int dist = levenshteinDistance(word, dictWord);
        if (dist <= maxDistance) {
            candidates.push_back({dist, dictWord});
        }
    }
    
    std::sort(candidates.begin(), candidates.end());
    
    std::vector<std::string> result;
    for (const auto& c : candidates) {
        result.push_back(c.second);
    }
    return result;
}

嗯，这里有个坑。如果词典有10万个单词，每次纠错都要遍历一遍，计算量可不小。我曾经在嵌入式设备上跑这个逻辑，卡得不行。后来加了前缀过滤——只计算首字母相同或相近的单词，速度就上来了。

知识体系总览

下面这张图把拼写检查器的核心逻辑串起来了：

完整示例：从文件加载词典

词典文件长什么样？每行一个单词，纯文本就行。我习惯用/usr/share/dict/words，Linux系统自带的词典，大概有10万个单词。

bool SpellChecker::loadDictionary(const std::string& filename) {
    std::ifstream file(filename);
    if (!file.is_open()) {
        std::cerr << "无法打开词典文件: " << filename << std::endl;
        return false;
    }
    
    std::string word;
    while (file >> word) {
        // 转小写，统一处理
        std::transform(word.begin(), word.end(), word.begin(), ::tolower);
        dictionary.insert(word);
        wordList.push_back(word);
    }
    
    std::cout << "加载了 " << dictionary.size() << " 个单词" << std::endl;
    return true;
}

注意那个::tolower，我一开始没加，结果用户输入"Apple"查不到"apple"，被测试骂了一顿。从此以后，所有文本处理我都先转小写。

实际使用效果

用户输入	检查结果	建议
hello	✅ 正确	-
helo	❌ 错误	hello, helot, helos
recieve	❌ 错误	receive, relieve, receipt
programing	❌ 错误	programming, programing

你看，"programing"少了一个'm'，编辑距离为1，能正确建议出"programming"。这种错误在程序员打字时特别常见，我自己就经常手滑。

拼写检查器这个项目，说难不难，说简单也不简单。核心就是编辑距离算法，但真正要做得又快又准，还得在数据结构和剪枝策略上下功夫。嗯，先动手写一个基础版本，跑通了再慢慢优化。

---

公众号:蓝海资料掘金营，微信deep3321