1. 先聊聊caveman这个项目要解决什么问题1.1 拼写纠错远比查字典复杂很多人第一次听到caveman这个名字第一反应是原始人第二反应是这项目是不是和石器时代有关。其实这名字纯属自嘲项目最早的雏形就是把Peter Norvig那篇经典的《How to Write a Spelling Corrector》用Java重写了一遍代码风格极其粗暴像原始人抡石头一样——不讲究设计模式不考虑扩展性能用就行。没想到跑起来之后效果出奇地好后来迭代着迭代着就成了一个真正能用的拼写纠错框架。先说清楚拼写纠错和查字典是两回事。字典只能回答这个词存不存在而纠错要回答的是用户输入了一个不存在的词时他大概率想输入的是哪个词。举个例子用户敲了recieve字典只会告诉你查无此词但纠错系统需要推断出用户想写的是receive并且给出一组候选receive优先级最高relieve次之而不是把recieve标注为错误就完事。这个场景在真实业务里到处都是搜索引擎的搜索词纠错、电商平台的商品名匹配、客服系统的工单分类、IDE的自动修复、聊天机器人的意图识别前置处理。只要是文本输入的地方拼写错误就会稳定出现比例通常在2%到8%之间。我接过不少项目排查线上日志的时候发现光是因为用户拼错关键词导致搜索召回失败的比例就能占到整体无结果查询的三成以上。caveman的目标很直接给定一个错误词在亿级词库中快速找出正确的候选词并排序。快速到什么程度单次纠错延迟控制在毫秒级内存占用尽量可控支持自定义词典和训练语料不依赖外部服务。这套东西做出来之后既可以作为Java库嵌进业务系统也可以单独封装成服务对外提供接口。1.2 选择自研而不是调库的三个理由可能有人问拼写纠错这玩意儿不是有很多现成方案吗Elasticsearch有fuzzy查询各种拼写检查库也很多为什么还要自己造轮子我的理由有三个。第一通用库对业务场景的理解是不够的。搜索引擎的fuzzy查询做的是词项层面的模糊匹配它不关心recieve和receive在真实语言使用中的概率差异也不关心用户是手滑打错了还是真的不会拼。这导致的结果是召回了一堆语义上八竿子打不着的候选排序更是没法看。第二定制化能力。业务场景里往往有自己积累的语料比如电商平台的商品名、医疗系统的药品名、游戏社区的装备名词。这些专有名词在通用词典里根本不存在你需要一套能自己喂数据的机制。现成库的词典格式通常封闭扩展起来极其痛苦。第三性能不可控。亿级词库规模下很多现成方案的查询延迟会飙到几十毫秒甚至上百毫秒这还不算内存占用。caveman从一开始就奔着大词库、低延迟去设计索引结构、存储布局、候选召回算法全部围绕这个目标展开。1.3 项目整体架构与数据流caveman的完整数据流大概是这样的用户输入一个词先走一遍预处理去空格、统一大小写、过滤符号标记。然后查主词典如果命中说明这个词本身合法直接返回如果没命中进入纠错链路。纠错链路分三步候选召回、候选评分、结果排序。候选召回负责从亿级词库里捞出一批长得像的词候选评分负责给每个候选打分最后按分数排序输出Top N。整个链路的耗时分配很有讲究。预处理是纳秒级词典命中查询是微秒级候选召回是毫秒级候选评分反而不能太重——因为要对召回的每个候选都跑一遍这部分必须控制在纳秒级。很多人做纠错系统把大量算力花在召回阶段搞了一堆复杂的相似度计算结果召回了十万个候选评分阶段直接卡死。这是典型的架构倒挂。caveman的架构选择是召回阶段用BK树做粗筛保证查全率评分阶段用词频加错误模式权重做精排保证查准率。这两个阶段的索引结构相互独立互不干扰。下面我分别拆开讲。2. 词典从哪来、怎么存词频库与双数组Trie2.1 训练语料清洗与分词任何拼写纠错系统地基都是词典和词频。没有词频你就无法回答哪个候选更常见这个问题没有词典你连什么词是合法的都判断不了。caveman的词典来源有三类一是公开的词频表比如Google的Web Trillion Word Corpus统计、官方语料库的词汇表这些作为基础盘二是业务方提供的领域词典比如商品类目词、药品名、地名这些作为专用盘三是从搜索日志里挖掘出来的高频查询词这些作为动态盘。三类合流之后清洗规则要非常严格。我踩过的清洗坑主要有三个。第一个是HTML实体爬下来的语料里全是amp;、lt;这类东西不清理干净会污染词频统计。第二个是过长的词语料里经常有连续几十个字母的乱串这些多半是URL或者编码错误直接过滤掉长度大于64的token。第三个是纯数字和混合数字串比如2024、3.1415926这些词在纠错场景里没有意义保留它们只会让候选召回出现一堆数字噪音。清洗完语料之后要做分词和词频统计。英文场景直接按空白切分就行但要注意缩写词和标点粘连的情况比如dont不能拆成don和t。统计词频时我推荐用滑窗式统计加平滑处理直接拿原始频次作为先验概率会让高频词和低频词的差距过大排序时低频候选几乎没有出头之日。caveman的做法是对词频做对数变换score log(1 freq)把百万级和个位数的差距压缩到可比较的范围。2.2 为什么HashMap扛不住亿级词库第一版caveman很天真直接用Java的HashMap把所有词和词频装进去。当时想的是两百万词条也就几百MB内存能接受。结果数据一上量就傻眼了当词条数到五千万HashMap的内存占用接近6GB查询虽然还是O(1)但GC压力大到直接影响线上延迟。HashMap的问题在于Java对象有头信息每个String对象除了字符数组还有对象头、hash缓存、length字段每个Entry又有一堆指针。算下来一条词条约占120字节一亿条就是12GB这还没算扩容时的临时内存。而且HashMap的键是String对象每次查询都要new一个String做equals比较短生命周期对象一多Young GC频繁触发延迟抖动非常明显。正确的做法是把词典做成紧凑的、面向只读查询的结构。caveman最终选了双数组Trie。双数组Trie本质上是一种用两个整数数组base和check实现的确定性有限自动机它把树结构压平成了两个数组查询路径直接通过下标跳转完成全程没有对象创建没有指针追逐缓存命中率极高。2.3 双数组Trie构建与查询流程双数组Trie的原理说穿了就一句话每个节点用base数组记录子节点的起始下标用check数组记录父节点的信息。插入一个词时从根节点出发每读一个字符c就跳到下标base[当前节点] c的位置检查check[目标位置]是否等于当前节点等于说明这条边存在不等于说明没有这个词。构建过程要处理的主要问题是冲突插入新词时如果目标位置已经被占用需要调整base值把整棵子树搬到新的位置。这个过程如果实现得不好构建时间会爆炸。我的做法是借鉴了darts-clone的思路用双数组Trie之前先构建一棵普通Trie然后用BFS逐层分配base值遇到冲突就整体迁移同一层的兄弟节点。查询逻辑极简Java代码长这样public boolean lookup(String word) { int node 1; // 根节点 for (int i 0; i word.length(); i) { char c word.charAt(i); int next base[node] c; if (check[next] ! node) { return false; } node next; } return leafCheck[node]; // 标记是否为词尾 }这个查询没有递归没有函数调用栈没有对象分配单次查询的耗时基本取决于数组访问和缓存命中。实测下来一亿条词库的Trie数组大小约800MB单次精确查询耗时约200到400纳秒比HashMap快一个数量级。2.4 与普通Trie及双数组的取舍可能有同学问为什么不用压缩Trie或者普通的Array Trie普通Trie的每个节点需要存储子节点指针数组如果每个节点都开256个指针的数组稀疏度极高内存浪费严重。压缩Trie把单分支路径合并查询速度提升但构建复杂度高而且对字符集变化不友好。双数组Trie正好在两者之间内存紧凑查询快构建可以接受。不过双数组Trie也有两个痛点需要提前知道。第一插入和删除非常昂贵所以它本质上更适合构建一次、长期只读的场景。如果你需要频繁更新词典得想别的办法比如定期重建或者增量索引叠加。第二构建时base数组的分配策略直接影响空间利用率darts-clone里用了多层数组打包加上各种启发式但纯手写版本很容易出现空间膨胀。caveman最终选择构建完成后将base和check数组直接映射成散文件用FileChannel.map做内存映射启动时不用加载查询时由操作系统按页载入。这个设计的另一个好处是多个JVM实例可以共享同一份词典文件内存占用不随进程数线性增长。3. 候选召回不靠遍历BK树的剪枝艺术3.1 编辑距离的朴素计算与代价模型词典建好了接下来就是召回。最简单粗暴的想法是用户输错一个词我遍历整个词典算一遍编辑距离把距离小于等于2的词都捞出来。这个方案在十万词库的时候勉强能跑但到了亿级词库就是灾难——遍历一亿次每次算编辑距离O(n*m)单次请求的CPU开销直接爆表。编辑距离Levenshtein距离定义本身不难把一个字符串变成另一个字符串允许插入、删除、替换三种操作每种操作代价为1求最小操作次数。标准的解法是动态规划开一个二维数组逐格填充。caveman最初的实现也是这么干的后来发现这里可以优化不少字符串长度通常很短可以用滚动数组把空间压到O(n)但这还没到关键。关键问题是很多候选词跟错误词之间的真实距离远大于阈值这些词根本不需要参与计算。打个比方用户输入appel你不需要去跟banana算一遍编辑距离因为一眼就看出来这俩不可能是同一个单词的失误。问题的核心变成如何快速排除那些不可能成为候选的词。3.2 BK树的基本思路与构建BK树就是为这个场景设计的。它利用编辑距离满足三角不等式这个性质构建一棵度约束的树。三角不等式说的是dist(A, C) dist(A, B) dist(B, C)。反过来用如果已知词典里某个词word和错误词query之间的距离是d那么对于word的某个子节点child如果child和word的距离是k那么dist(child, query)一定落在区间[|d - k|, d k]内。这个性质的意义在于给定一个查询词和一个最大距离阈值T遍历BK树时如果当前节点与查询词的距离是d那么只需要访问那些与当前节点距离在[d - T, d T]区间内的子节点其他子树可以直接剪掉不用遍历。这就像查地图时你已经知道自己离目标大概三公里那就没必要往反方向开十公里去找。构建BK树的规则很简单每插入一个新词从根节点开始计算它与当前节点的编辑距离k如果当前节点没有k这个距离的子节点就把新词挂上去如果有就顺着这个子节点继续往下走重复这个过程。这样每个节点的子节点都按距离值分类存储。3.3 查询剪枝与距离阈值选择查询时从根节点开始计算根节点与query的距离d。如果d T根节点本身就是一个候选记录它。然后遍历根节点的所有子节点对于每个子节点先看它与根节点的距离k如果k落在[d - T, d T]区间内就递归进入这个子节点否则跳过整棵子树。这里引入一个容易踩的坑T的取值。我做过对比实验T1时召回率严重不足因为真实世界里的拼写错误经常是距离2的漏了一个字母加上打错一个字母T2时召回率明显上升但候选量也上来了T3时候选量爆炸而且纠错正确率不升反降——因为距离3的词根本不像同一个词。caveman的默认策略是T2允许用户对特定词条配置T3。另外我用了一个动态阈值的小技巧当错误词本身长度超过8个字符时自动把T加到3。原因是长词拼错时通常只有一个局部片段出错整体距离可能达到3但对短词来说距离3基本就意味着完全不相关。3.4 召回结果的内存与质量平衡BK树查询还有个副产品就是召回数量不稳定。同样是T2短词召回的候选可能只有几个而某些生僻词可能召回到上千个。上线初期我在线上看到过最夸张的例子一个5个字符的错误词召回了2600多个候选排序阶段全跑一遍单次请求耗时冲到50毫秒。解决方案是给召回加上限。caveman的做法是BK树查询过程中用一个容量为K的最小堆保存当前最优的候选超过K就直接丢弃距离更大的候选K默认取32。这样排序阶段最多处理32个候选单次请求耗时立刻降下来了。实测下来K取32这个值在质量和性能之间取得了一个很好的平衡绝大多数场景Top10已经完全够用。4. 纠错排序才是真正的核心逻辑4.1 从Norvig的错误模型说起候选召回解决的是有哪些可能排序解决的是哪个最像正确答案。Peter Norvig在他的经典文章里提出过一个非常朴素的贝叶斯模型P(c|w) ∝ P(w|c) * P(c)。翻译成人话就是用户想写正确词c、但打成错误词w的概率等于从c错误地生成w的可能性乘以c本身在语言里出现的可能性。caveman第一版直接照抄了这个模型用词频估计P(c)用一个固定规则表估计P(w|c)——比如一次替换、一次插入、一次删除、两次错误这种错误类型分别给不同的概率。效果能跑但很快发现两个问题一是只有词频作为先验高频词碾压一切冷门的专业术语永远排不上号二是固定规则表完全不区分这种错误到底有多常见比如把m打成n和把a打成s本质上的产生机制完全不同概率应该差异很大。4.2 词频先验与平滑策略先解决P(c)的问题。词频先验不能直接用原始频次因为原始频次的长尾分布太离谱。高频词the出现几十亿次生僻术语可能只有几次。如果不做平滑生僻词永远排不上号哪怕它跟错误词的距离更近。caveman的处理是先对全部词频取对数然后做线性插值平滑。具体公式是score(c) λ * log(freq(c)) (1 - λ) * baseScore其中baseScore是词典中所有词频的中位数。lambda取0.7。这个平滑的作用是压低高频词的绝对优势同时抬升中低频词的竞争力。实际效果我对比过在recieve这个错误词的纠错结果里如果不做平滑receive和relieve的词频差距是20倍排序结果还算稳定。但遇到拼写更模糊的词比如teh正确答案是the候选里却有tea、ten、tech这些词频差异巨大的词不做平滑的话the反而可能输给tea。4.3 错误模式权重键盘距离、形近字与音近字P(w|c)部分才是真正拉开差距的地方。caveman构建了一套错误模式权重体系按照错误的物理成因分类第一类是键盘误触。用户在QWERTY键盘上打字时手指跳动导致按键偏移最常见的是把s打成a或者d。这类错误的概率跟键盘按键之间的物理距离强相关。caveman内置了一张按键邻接表能算出任意两个按键之间的曼哈顿距离距离越近的替换代价越低。第二类是形近字混淆。这在英文里集中在某些视觉相似的对子比如rn和m、(cl和d、il和uOCR场景特别常见。caveman把这类混淆拆成子序列级别的替换单独计算一个损失分量。第三类是音近字。比如ph和f、c和k、tion和sion。搜索日志里这类错误特别多因为用户是听写而不是打字。caveman维护了一张发音规则映射表做发音相似度的局部替换加分。每个错误模式都有一个权重权重不是拍脑袋定的而是从训练语料里统计出来的我准备了一批标注好的错误-正确词对比如从搜索引擎日志里扒出来的用户纠错行为数据统计每种错误模式的出现占比再映射成权重。4.4 上下文特征与候选加分词频和错误模式组合起来已经能解决80%的问题但还剩一类棘手情况两个候选词在词频和距离上都很接近必须靠上下文才能区分。典型例子是their和there单独看tehir这个错误两个候选的距离完全一样没有上下文信息人类也没法判断用户想写哪一个。caveman提供了一个上下文评分的扩展接口如果调用方传入前后文纠错系统会对每个候选计算一个上下文匹配分比如候选词与左边词和右边词构成二元组的概率。用简单的bigram统计就能做出很好的效果。举个实际例子在tehir car这句话里there car的概率极低而their car的概率很高上下文特征直接帮their胜出。当然上下文评分不能依赖一个隐式模型埋头跑caveman把它设计成可插拔的默认内置bigram统计模型业务方也可以提供自己的embedding模型给候选打分只要实现同一个接口。4.5 排序公式与调参经验最终caveman的评分函数长这样finalScore α * logFreqScore β * errorModelScore γ * contextScore三个权重α、β、γ不是固定值而是通过一份人工标注的纠错评测集调出来的。我的调参经验是先固定α1、β1、γ0用网格搜索把α和β调到最优再加入上下文特征通过网格搜索确定γ相对前两者的比例。最终在caveman的默认参数里α0.6、β0.3、γ0.1。调参时最容易翻车的点是千万别在评测集上过度拟合。评测集一定要分成训练集和验证集调参只用训练集验证集留到最后跑一次。我第一版迭代时在评测集上跑出98%的准确率上线后真实数据准确率只有75%就是因为把评测集背下来了真实数据里大量没见过的错误模式直接暴露出来。5. 工程落地的几个硬骨头5.1 亿级词库的内存布局前面提到过caveman的词典用双数组Trie存原则是能只读绝不全量加载。真正落地上线时还需要考虑几个额外的问题这里逐个说一下。第一词频不应该跟着Trie走。双数组Trie的查询结果只是一个布尔值这个词存在还是不存在。词频是评分阶段的输入放在另外一个紧凑的哈希表里更合理。caveman的做法是词频表用open addressing的int数组实现键是词在Trie中的终止节点下标值是平滑后的log频次。这样查询一次Trie得到下标直接查int数组得到频次全程没有对象分配。第二错误模型权重表要预计算成整型数组。公开的错误模式表如果在运行时逐个匹配字符串性能完全不可接受。caveman把键盘邻接距离、形近字规则、音近字规则全部预编译成int[key][value]的二维数组查询时直接下标取数耗时忽略不计。第三候选召回阶段的BK树也是一个只读结构。BK树的每个节点对应一个词边上挂距离值同样用数组序列化存储。构建完后整体写入散文件查询时按页映射。这三块加起来一亿条词库的总内存占用能控制在1.2GB左右远低于第一版HashMap方案的12GB。这个数字在不同机器上实测略有差异但整体量级是可预期的。5.2 并发查询与只读优化caveman的查询链路整体是只读的这带来一个很大的福利完全不需要加锁。因为所有数据结构都是构建期写死、查询期只读并发查询不会产生任何写竞争。理论上你开多少个线程同时查性能都能线性扩展。不过有一个细节需要注意虽然数据结构是只读的但查询过程中如果产生了临时对象依然会造成GC压力。caveman在查询方法里尽量复用局部变量用栈上分配的原始类型数组替代List还有一个小技巧是给每个线程配置一个独立的临时缓冲池避免ThreadLocal带来的伪共享问题。压测数据很能说明问题。单机8核机器上十万次纠错请求的QPS大约能到8000P99延迟稳定在3毫秒以内。如果把词库换成千万级QPS会略有下降但P99基本不变。主要原因在于双数组Trie和BK树的查询都是走数组下标访问词库大小对单次查询的时间复杂度影响很小。5.3 启动预热与灰度开关只读结构虽然好但也有个冷启动的问题。内存映射文件在第一次访问时会被操作系统按页载入如果线上刚发布完所有请求都堆积在首屏延迟会瞬间飙升到几十毫秒甚至几百毫秒这就是冷页缺失。caveman的做法是在启动时做一次预热用一个独立线程把所有词典的key跑一遍精确查询强制触发页面加载。这个过程根据词库大小通常需要十几秒到一分钟。预热完成后入口的流量再放进来P99就恢复稳定了。另外我强烈建议给纠错功能加一个灰度开关。不是所有业务都希望一上线就全量开纠错特别是那些对准确性要求极高、宁可漏纠错也不要错纠错的场景。caveman的配置中心里有一个返回策略的开关默认是有把握才纠错即最终评分低于阈值的直接返回原词灰度阶段可以调高阈值让更多纠错生效同时允许按用户ID或者按流量百分比抽部分请求接入。5.4 性能数字与瓶颈分析最后给一组真实压测数据供参考机器配置是8核16GB SSDJVM堆内存给了6GB场景词库规模平均延迟P99延迟QPS词典精确查询1亿0.3ms0.8ms6万拼写纠错召回排序1亿1.2ms3ms8000拼写纠错召回排序预热后1亿1.0ms2.5ms9000瓶颈分析下来主要在两方面。第一是BK树查询的递归遍历在大距离阈值下依然有一定开销后续可以考虑把BK树构建成多棵以不同首字符为根的森林进一步降低查询深度。第二是排序阶段的上下文bigram查询如果上下文词不在词频表里会触发一次Trie查询这部分可以加一层缓存优化。6. 我在caveman上踩过的坑和防御策略6.1 大小写和专有名词的误伤第一个大坑是大小写。英文里首字母大写的词通常是专有名词、地名、人名比如Apple、England但句子开头的词也会首字母大写比如The quick brown fox。如果不加区分地做纠错用户输入england时系统可能会把它纠成England以外的东西看起来非常蠢。caveman的处理办法是纠错之前保留输入词的原始大小写形态纠错完成之后如果原始输入是首字母大写那么候选词也强制首字母大写如果候选词本身就是专有名词即使输入是小写输出也保持专有名词形式。这个策略简单有效但要注意一个例外如果输入词全部是大写比如用户真的在喊HELP那候选词全部转小写再纠错输出再还原成全大写。6.2 数字、URL、版本号千万别动第二个坑是我被线上业务方投诉最多的地方错误词里带着数字比如iphone12系统死活要给人家纠成iphone。还有用户输入了一长串URL里面包含字母数字和符号系统把它切成几个片段分别纠错结果把好好的链接纠得稀碎。防御规则很明确如果输入词里包含数字默认不做纠错原样返回如果包含.或/或www字样默认判定为URL原样返回如果包含版本号特征数字加点加数字比如1.2.3原样返回。这三条规则优先级最高直接在预处理阶段拦截根本不进入纠错链路。6.3 中文场景的特殊适配caveman虽然是英文拼写纠错的底子但国内业务场景里很多输入其实是中英混排的比如手机iphone、qq邮箱。一开始我天真地以为对中文部分不处理就行后来发现中文和英文连在一起时会被当成一个token处理比如手机iphone被整体匹配结果永远匹配不上也没法触发纠错。后来我在分词阶段引入了一个简单的规则在英文字符和中文标点之间插入分隔符中文部分不参与纠错直接透传英文部分单独走纠错流程。中文内容还需要做一件额外的事情专有名词保护比如故宫、兵马俑这些词汇通过用户自定义词典的方式加进保护列表纠错时如果候选词跟保护列表里的词重合直接跳过。6.4 过度纠错的回滚机制最后一个坑是过度纠错。有些词本身拼写正确但看起来太像某个高频词的错误版本系统会好心地把它纠正掉结果是在用户根本没有犯错的时候改错了内容。典型案例是recieve和receive这种但还有更隐蔽的比如caveman本身在某个词频表里低频出现系统却把它当错词纠成cavemen。解决这个问题的思路是给纠错行为加一个置信度门槛。caveman引入了原词合法但低频时也允许纠错的开关默认关闭。开启后只有当候选词的评分比原词的评分高出至少50%时才会真正执行纠错否则就原样返回。这个50%的值不是拍脑袋定的而是根据线上反馈数据调整出来的我们当时用了一个简单的规则纠错错误率超过3%就提高门槛低于1%就降低门槛。还有个相关的防御机制是忽略列表。业务方可以把一批绝对不允许动的词直接配进去比如品牌名、用户昵称、特殊术语这些词即使看起来再像错误拼写系统也不会碰。这个列表在caveman里的实现优先级是最高的比预处理阶段的数字、URL规则还要靠前。7. 我的最终建议与一点补充想法写到这里caveman这个项目从核心原理到工程落地基本讲完了。最后说几个我自己在实际操作上的心得体会供准备动手做类似系统的同学参考。第一个体会是先想清楚你要的是高召回还是高精确这个方向比算法本身更影响架构。搜索引擎类场景追求高召回宁可多冒出来几个无关候选也不放过一个可能的修正输入法、IDE这类工具追求高精确纠错错了比不纠错更让用户烦。caveman默认往高精确偏但通过配置可以切换关键是设计时别把路堵死。第二个体会是数据永远是最大的瓶颈。算法模型再花哨如果词频库本身质量不行纠错效果一样糟糕。我在给caveman换数据源的时候经常出现换了一版词频库准确率上升3个百分点再下降2个百分点的情况。所以如果你要复刻类似项目先把训练数据这块做扎实比写任何优化代码都值。第三个体会是一定给自己留一个什么都不做的选项。很多拼写纠错系统上线后被骂不是因为纠错能力不行而是因为它在不该出手的地方出手了。caveman最后的准确率能达到90%以上很大程度上不是靠算法有多强而是靠层层防御规则把不该开车的场景全都拦住了。如果你打算在现有代码上继续扩展我个人觉得有三个方向比较有价值一是把BK树换成基于度量空间的更现代索引比如VP树或者GH树查询性能还有优化空间二是把词频模型从静态表换成根据用户行为实时更新的动态模型这能让系统逐渐适应特定群体的表达习惯三是把整个纠错链路做成可观测的每个候选的分数构成都要能解释这在业务方排查问题时能省掉大量沟通成本。这是caveman给他我带来的全部经验希望能帮到准备踏入拼写纠错领域的同学。
