拼写纠错：编辑距离与n-gram重叠

可视化演示

通过编辑距离DP表、n-gram重叠匹配和噪声信道模型，直观展示拼写纠错的核心算法流程。

纠错问题概述

你有没有过这种经历：搜“苹果手ji”，结果页第一屏全是手机壳，而你明明只打错了一个字母？食堂大妈的日常也是这样——每天都有客人把“西红柿”写成“西虹市”、把“宫保鸡丁”写成“工保鸡丁”。在搜索引擎的世界里，错别字查询的比例高达一成左右，如果不处理，用户要么看到一堆无关结果，要么干脆跳出页面，流量就白白流失了。

那么，拼写纠错到底是什么？简单说，就是系统先判断“这句话里有没有写错的词”，再从词典里召回一批“看起来可能是你想写的词”，最后给这些候选词打分排序，选出最合理的那一个展示给用户。整个过程可以拆成三步：检错、候选、评分，就像食堂大妈先发现“这道菜名不对劲”，然后翻出几道相近的菜，最后凭经验锁定最像的那一道。

围绕这三步，业界形成了两大主流方法。一类是从“字形改动”出发，计算两个词之间最少要变几个字，这就是编辑距离（Edit Distance）；另一类是从“局部片段”出发，把词切成小块再看重合度，这就是 n-gram 重叠。两者各有各的脾气，也常常配合使用——就像大妈既会逐字核对菜单，也会凭“这片菜叶子眼熟”来速记。

回到我们的比喻：编辑距离是“逐字抠”，n-gram 是“看片段”。理解了两者的分工与配合，拼写纠错这道菜，你就已经知道该从哪下筷子了。

编辑距离算法

食堂大妈拿到“西虹市炒旦”后，心里开始默算：“'西'对'西'没问题；'虹'得改成'红'；'市'得改成'柿'；至于'炒旦'嘛……'旦'要改'蛋'。”她数的不是哪个字像，而是一共需要动几次。这种思路落到计算机里，就是编辑距离：把一个字符串变成另一个字符串，最少需要多少次单字符操作，每次操作限定为插入、删除、替换之一。

为什么只允许这三种操作？因为这是人类手写和输入法出错的最小单元：漏打一个字是删除，多打一个字是插入，打错字形或读音相近的字就是替换。任何复杂的改动都能拆解成这三样的组合，所以把“最少操作次数”当作两个词的距离，既直观又统一。

直接暴力枚举所有改动方案是不可能的——“西红柿炒蛋”和“西虹市炒旦”之间可能的操作序列多到爆炸。聪明的做法是动态规划：把大问题拆成小问题，用一张表格记录“某前缀变成另一前缀”的最小代价。定义 $d_{i,j}$ 表示把字符串 $a$ 的前 $i$ 个字符变成字符串 $b$ 的前 $j$ 个字符所需的最少操作次数，那么递推关系如下：

从“西虹市”到“西红柿”，查表得到距离是 2，和食堂大妈的心算完全一致。动态规划表看似复杂，其实就像大妈在心里列了一张“菜名对照账本”，一格一格记下所有前缀的最优改法，最后只取最角落那个数字。

n-gram重叠

不过，大妈也有犯难的时候。比如客人把“哈根达斯”写成“哈跟达丝”，逐字改起来要动三处，算编辑距离也不算小；可要论“看起来像不像”，这两个词几乎一模一样。这时大妈换了思路：不数改动次数了，而是把菜名切成“哈跟、跟达、达丝”这样的小块，再和菜单上的“哈根、根达、达斯”摆在一起，看看两堆小片段有多少是重合的。切成小块看重合，就是 n-gram 重叠。

n-gram 里的 n 表示每次取几个字符连成一“片”。中文里最常用的是 n=2，也就是二元片段（bigram）：“西红柿”切成“西红、红柿”，“西红市”切成“西红、红市”。单个字太泛，三个字以上的片段又太苛刻——只要写错一个字，整片就对不上了。切成小片段后，怎么量化两堆片段的相似程度呢？最经典的是 Jaccard 相似度，它把片段当成集合，求“交集大小 ÷ 并集大小”：

回到比喻中，编辑距离像“数着算”，n-gram 重叠像“看着拼”。“哈跟达丝”虽然改字多，但片段重合度极高，n-gram 能轻松抓住这种“形近”的直觉，弥补编辑距离对局部相似不敏感的短板。

候选集生成

食堂后厨有一千道菜，大妈不可能把每道菜都拎出来跟客人的错字比一遍。她真正的底气在于后厨的分类架：每一种两字食材片（比如“西红”）都固定放在一个贴着标签的盒子里，盒子里放着所有包含“西红”的菜名。客人报出“西红”，她直接冲到“西红”盒子前，把里面的菜名全抓出来。这个“食材片 → 菜名列表”的对应关系，在计算机里就叫 n-gram 倒排索引——它是候选集生成的加速器。

为什么要专门做这一步？因为词典可能有几十万甚至上亿个词，逐词计算编辑距离或者 Jaccard，一次查询就要做百万次比较，绝对扛不住。倒排索引把“从词查片段”变成“从片段查词”，查询时只需三步：先把用户输入的错词切成 n-gram 片段；再拿每个片段去倒排索引里查对应的倒排列表（posting list）；最后把多个列表合并起来，就得到一份候选词集合。整个过程就像大妈报出“西红、红市”，分类架上两个盒子里的菜名一合并，候选名单立刻到手。

候选集不能来者不拒，否则又回到“百万比较”的老路。于是需要剪枝策略：只保留与查询至少有 1 个公共片段的词（通常要求更多），控制候选规模在几十到几百的量级；同时限制单个倒排列表的扫描长度，避免“西红柿”这种超热门片段拖垮性能。召回与效率之间是一对天平：剪枝太狠会漏掉正确答案，剪得太松则评分阶段变慢。实战中常把倒排列表按词频排序，优先处理高价值候选。

所以，倒排索引就是食堂后厨那面分类架——没有它，大妈只能一道菜一道菜地问；有了它，错词一出口，候选菜名已经在手里了。这也是为什么拼写纠错通常被安排在“倒排索引与查询处理”这个环节里：先靠索引快速召回，再靠精确打分定夺。

相似度评分

候选名单拉回来了，可能有三五道菜都沾边：西红柿、西红市、番茄……大妈得给它们一一打分，才能给出最靠谱的建议。打分需要两把尺子同时量：一把是“改动次数”（编辑距离），一把是“片段重合”（n-gram 重叠）。可两把尺子的刻度不一样——编辑距离是“越小越好”，n-gram 是“越大越好”，而且数值范围也完全不同，不能直接相加。

第一步，把编辑距离归一化到 0 到 1 之间，让它也变成“越大越像”。做法是用 1 减去“距离除以两个词中较长的长度”：距离为 0 时相似度为 1，距离占满整个长度时接近 0。第二步，给两把尺子各设一个权重，让系统决定更信“逐字抠”还是“看片段”。把两者加权融合，就得到一个综合评分：

打分这一步，相当于大妈在心里给候选菜逐一贴“靠谱指数”。只有把编辑距离和 n-gram 这两路信号都照顾到，再设好及格线，推荐出去的纠错结果才不会闹出“用户要西红市，你推了个红市炒蛋”的笑话。

工程优化

中午饭点一到，订单像雪片一样飞来，食堂大妈光靠手算肯定扛不住。真实搜索引擎的流量比食堂高峰还要恐怖：每秒有成千上万个查询涌进来，其中不少还带着错字。这时，纠错系统的工程优化就成了胜负手，后厨流水线必须做到三件事。

第一，离线构建索引。所有词典词的 n-gram 倒排索引是在服务启动前就构建好的，线上只做“查表”不做“建表”。构建时还能顺便统计每个词的热度（词频），把热门词放在倒排列表头部，这样合并候选时优先命中高价值词，既快又准。第二，缓存加速。绝大多数错词是重复的，比如“西虹市”每天被上千人搜索，把它的纠错结果缓存起来，命中缓存就直接返回，连查表都省了。缓存通常用 LRU（最近最少使用）策略，只留最热门的那些，避免内存被拖垮。

第三，性能分析与横向扩展。线上要监控两个核心指标：P99 延迟和候选集规模。如果发现某个 n-gram 的倒排列表特别长，说明它太“泛”了（比如单字“的”），需要剪枝或拆分；如果单机扛不住，就按 n-gram 的哈希值把索引分片到多台机器上，每个查询并行访问多个分片再合并结果。整个链路从“检错”到“打分”都要控制在毫秒级，才能保证搜索体验不被拖后腿。

后厨流水线的本质，就是把“现算”变成“预存 + 快查”：索引是准备好的食材架，缓存是热菜保温柜，分片是多个窗口同时出餐。拼写纠错做到这一步，才算真正从“能跑”进化到“能扛”。

实践与陷阱

再熟练的大妈也有失手的时候：客人点的是新菜，菜单上根本没有；或者客人故意写了个游戏里的“西红柿炒蛋”召唤梗，大妈却一本正经地改成了家常菜。拼写纠错的落地过程中，这类“好心办坏事”的陷阱比比皆是。

第一个要注意的是中英文差异。英文天然按空格分词，“appple“ 的编辑距离对着词典算就行；中文没有空格，直接拿整句和整篇词典比不现实，通常要把查询按字切分再做 n-gram，或者引入拼音、字形等额外的相似信号。第二个是热度信号不可或缺。编辑距离最小的词不一定是对的——用户搜”tb“，距离上最近的可能是某个生僻缩写，但 99% 的人想找的是”淘宝“。所以评分时一定要叠加词频、点击率等热度特征，让系统像大妈一样优先推荐”最常被点的菜”。

第三个大坑是误把纠错当成直接改写。很多搜索框会把“西虹市”悄悄改成“西红柿”再检索，但自动改写有风险：品牌词、人名、新词都可能被误伤。稳妥的做法是默认展示“您是不是想找：西红柿”的提示条，只有对高置信度、低风险的结果才自动改写。最后，效果好不好不能只看离线指标，还要看端到端评估：纠错是否真正提升了点击率、转化率？有没有伤害原本正确的长尾查询？这需要用真实搜索日志做 A/B 测试来回答。

要做好效果调优，最有效的武器就是搜索日志：把用户“输入错词 → 点击正确结果”的轨迹挖出来，就是一份天然的错词对照表，可以持续扩充词典和热度统计。大妈也会把每天“猜错”的订单记在小本本上——日志就是那个小本本，让系统越用越准，越用越懂人心。

AI 应用场景

Python 演示

# Spelling correction demo: edit distance + n-gram overlapdef edit_distance(a, b):    m, n = len(a), len(b)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(m + 1):        dp[i][0] = i    for j in range(n + 1):        dp[0][j] = j    for i in range(1, m + 1):        for j in range(1, n + 1):            cost = 0 if a[i - 1] == b[j - 1] else 1            dp[i][j] = min(                dp[i - 1][j] + 1,                dp[i][j - 1] + 1,                dp[i - 1][j - 1] + cost            )    return dp[m][n]  def ngrams(word, n=2):    return set(word[i:i + n] for i in range(len(word) - n + 1))  def jaccard(query, cand, n=2):    gq, gc = ngrams(query, n), ngrams(cand, n)    if not gq or not gc:        return 0.0    return len(gq & gc) / len(gq | gc)  def build_inverted_index(words, n=2):    index = {}    for w in words:        for g in ngrams(w, n):            index.setdefault(g, []).append(w)    return index  def generate_candidates(query, index, n=2, top_k=8):    scores = {}    for g in ngrams(query, n):        for w in index.get(g, []):            scores[w] = scores.get(w, 0) + 1    return sorted(scores, key=lambda x: -scores[x])[:top_k]  def correct(query, words, index, n=2, alpha=0.6, threshold=0.5):    candidates = generate_candidates(query, index, n)    results = []    for w in candidates:        norm_ed = 1.0 - edit_distance(query, w) / max(len(query), len(w))        score = alpha * norm_ed + (1 - alpha) * jaccard(query, w, n)        if score >= threshold:            results.append((w, round(score, 3)))    return sorted(results, key=lambda x: -x[1])  if __name__ == "__main__":    words = ["tomato", "potato", "tomorrow", "tobacco", "tonight"]    index = build_inverted_index(words)    print("edit_distance(tomato, tomoto):", edit_distance("tomato", "tomoto"))    print("jaccard(tomato, tomoto):", jaccard("tomato", "tomoto"))    print("candidates for 'tomot':", generate_candidates("tomot", index))    print("best correction:", correct("tomot", words, index))

1. dp = [[0] * (n + 1) for _ in range(m + 1)]创建一张 (m+1) 行 (n+1) 列的动态规划表，用于记录所有前缀变换的最小代价。
2. dp[i][0] = i边界初始化：把长度为 i 的串变成空串，只能逐个删除，代价是 i。
3. cost = 0 if a[i - 1] == b[j - 1] else 1当前两个字符相同则替换代价为 0，不同则为 1。
4. dp[i][j] = min(...)从删除、插入、替换三种方案里挑出代价最小的，这是编辑距离的核心递推。
5. set(word[i:i + n] for i in range(len(word) - n + 1))把词切成 n 个字符一组的连续片段，并用集合去重。
6. len(gq & gc) / len(gq | gc)交集大小除以并集大小，一行代码算出 Jaccard 相似度。
7. index.setdefault(g, []).append(w)每个 n-gram 片段后面挂上包含它的词，离线构建倒排索引。
8. for w in index.get(g, [])用查询切出的片段反查倒排索引，无需全词典扫描即可召回候选。
9. norm_ed = 1.0 - edit_distance(...) / max(len(query), len(w))把编辑距离归一化成 0-1 相似度，便于和 Jaccard 融合。
10. alpha * norm_ed + (1 - alpha) * jaccard(...)编辑距离与 n-gram 两路信号加权融合，得到综合评分。

常见误区

面试题