★ FEATURED ARTICLE 做文本去重和内容审核的时候我经常遇到一个需求两段文字看上去不完全一样但很可能是同一条内容重复提交。这时候拿BERT算语义向量有点大炮打蚊子拿全文精确匹配又漏判真正顺手的就是N-Gram文本相似度算法。这个算法原理并不复杂核心就是把文本切成一串固定长度的连续片段再比较片段的交集和并集几十行代码就能落地。它解决的是“文本之间到底多像”这个基础问题适合文本去重、评论聚类、检索纠错、OCR结果校验这类场景。如果你正在做一个需要判断文本相似度的功能又不想一上来就引入复杂的模型N-Gram是特别值得先试的方案。哪怕你今天已经在用大模型做语义向量我也建议团队里保留一个N-Gram相似度模块。很多看似需要“语义”的判断其实字面重叠就能解决而字面重叠判断快、成本低、可解释出了问题能立刻指出是哪几个n-gram片段在起作用。下面我会从最朴素的定义讲起逐步带你写一个能用在生产环境的小工具再聊聊我实际使用中觉得最有价值的经验。1. 为什么N-Gram在相似度计算里一直没被淘汰1.1 它解决的是“字面重叠”这一类问题先看定义。N-Gram也叫n元语法就是把一段文本按固定长度N切分成连续子序列。以字符级为例“苹果手机”切分成2-gram就是“苹果”“果手”“手机”。两个文本之间的相似度可以看成这两个子序列集合的重合程度。这个定义没有任何“语义”参与完全是字面上的重叠计算但正是这种朴素的视角让它能处理很多自然语言处理的脏活累活。我在实际项目中常用它处理的第一类问题是“看起来不完全一样但内部高度雷同”的文本。比如用户提交的表单内容有人复制过来以后把“客服”改成“客 服”中间多了一个空格也有人把标题改成“【推荐】”加在原文本前面还有人只是把最后几个字删掉。这些情况用全文精确匹配完全失效用编辑距离又会被无意义的增删字符干扰。但换成2-gram集合就不一样了核心内容没变大部分连续两字片段仍然重合相似度照样能稳定算出来。另一个典型场景是OCR结果比对。扫描版PDF转出来的文字经常出现“东”变“车”、“0”变“O”这类单字错误。单字错误会让整句词向量发生变化但字串的2-gram或3-gram集合中错误字符周围的部分片段依然保留因此N-Gram对这类噪声的容忍度很高。可以说只要文本主体是“复制局部修改”N-Gram就是性价比最高的相似度度量。1.2 跟相邻算法比它便宜在哪儿N-Gram不是唯一能算文本相似度的方法。编辑距离、TF-IDF余弦、词向量甚至BERT都可以做但N-Gram在很多场景下有别人替代不了的优势。我把常用方案对比放在一起看。算法需要训练/字典对错字容忍计算成本可解释性编辑距离不需要中等O(m*n)很高字符N-Gram Jaccard/Dice不需要高O(mn)很高TF-IDF 余弦需要语料/分词低取决于词表低BERT/词向量需要预训练模型中高GPU低这里最容易被忽视的是“可解释性”。N-Gram算出两条文本相似度是0.8你可以把命中的片段列出来给人看比如“相似”“似度”“度算”这几个2-gram都重合业务方一眼就能明白为什么判重。换成向量相似度你解释半天“语义空间里的余弦夹角”对方还是将信将疑。另外一个容易被低估的点是语言无关。N-Gram可以不做分词、不加载任何词表字符级N-Gram在中文、英文、日文、代码片段上都能直接跑。这在中后台系统里太重要了因为团队不一定有NLP专家维护分词词典本身就是个持续投入。N-Gram几乎没有这种运维负担。1.3 不适合用N-Gram的场景它当然不是万能的。如果两句话意思一样但用了完全不同的词比如“苹果味道不错”和“这种水果口感挺好”N-Gram的重叠就可能很低。再比如长篇文章结构相似但段落内容不同N-Gram也可能因为公共片段太少而判成不相似。这些都需要靠语义模型或更高级的特征来补充。我个人的判断标准是如果业务目标是“找字面高度重叠的重复文本”N-Gram是首选如果业务目标是“找语义等价的表述”N-Gram只能作为召回阶段的第一层过滤器后面必须接向量模型或规则。把这一点想清楚后面就不会选错方案。2. N-Gram的核心原理与计算方式2.1 字符级还是词级N-Gram有两个常见的切分维度字符级和词级。字符级是把字符串直接按字符滑窗。比如“今天天气不错”按2-gram切分得到“今天”“天天”“天气”“气不”“不错”。词级则先做分词再把词序列滑窗比如“今天/天气/不错”得到“今天 天气”“天气 不错”。字符级的好处是省掉分词这一步对错字、拼写错误容错高因为哪怕一个字符错了前后其他字符仍然能组成合法片段。词级的好处是语义单元更完整但代价是分词结果一旦出错错误会被放大到后续每个gram里。对中文来说字符级N-Gram几乎是默认选择。中文没有天然空格用词级要先加载一个分词模型而在清洗、去重这类场景里分词错误反而会引入更多噪声。对英文来说字符级N-Gram也能用但通常词级更自然尤其当你要过滤冠词、介词这种停用词时词级N-Gram可控性更高。还有第三种玩法是混合使用同时算字符2-gram和词2-gram然后加权合并。比如字符级给0.7权重词级给0.3权重。这种混合方式在评论去重上效果不错因为有些用户会故意插入同义词字面上变了但词序列相似度更高反过来也有用户改变词序但相邻字符没变字符级更稳定。混合能在两种信号之间取平衡不过你要多保存一份特征工程上略重。2.2 相似度公式用什么有了N-Gram集合相似度计算方法就有几种。最常用的三个是Jaccard、Dice和余弦相似度。Jaccard就是交集元素数量除以并集元素数量。公式写出来就是|A∩B|/|A∪B|。它的特点是被“并集”归一化两边文本越长并集越大得分越保守。Dice系数则是2|A∩B|/(|A||B|)。分母从并集换成了两边gram数之和相当于对交集给了更高权重。对短文本来说Dice通常比Jaccard分数高也更不容易因为文本长度差异造成分母被拉大。余弦相似度则把每个N-Gram看成一个维度用频次做权重计算两个向量夹角的余弦值。它的好处是可以利用gram出现的次数而不是只当成0/1的集合。我实际使用中用的最多的是Dice系数。因为它对文本长度差异不那么敏感。比如一条评论是5个字另一条是50个字用Jaccard算分母被长文本的大量gram灌满哪怕短文本的所有字都被覆盖分数也会很低但Dice的分子和分母分别统计交集和两边集合大小这种长度差异的影响稍小。当然真要严格处理还是需要在算法之外统一截断或规则归一化光靠公式救不了所有场景。2.3 N到底取几这是每个第一次用N-Gram的人都会问的问题。先给结论中文短文本优先N2英文句子优先N2到3代码查重可以到N5甚至更高。为什么中文短文本用2-gram最多因为中文字与字之间没有空格单个字的信息量很低1-gram只看字符集合会把“事后”和“后事”认成完全相似因为字符组成完全相同。2-gram引入了相邻两个字的关系“事后”是“事”“后”“后事”是“后”“事”2-gram集合完全不重叠能区分顺序。3-gram则会让短文本的gram数量急剧减少5个字的文本只有3个3-gram一旦有1个字错可能丢掉一个3-gram影响很大。所以短文本用3-gram经常算不出稳定结果。长文本则相反如果文本长度足够长2-gram集合会非常大很多高频短词反复出现导致相似度虚高。这时用3-gram或4-gram反而能提高区分度因为连续三四个字相同的概率比连续两个字相同低得多得到的交集更“有含金量”。我有个粗略经验文本平均长度在50字以内用2-gram50到200字之间用3-gram200字以上考虑4-gram但要配合阈值调整。3. 从零实现一个N-Gram相似度工具3.1 预处理比你想的更关键写代码之前先把预处理想清楚。别小看这一步我见过太多上线之后才发现问题最后都出在预处理上。首先要统一大小写把英文全部转成小写不然“App”和“app”会被当成两个完全不同的gram。其次是统一全角半角尤其是中文用户输入里的全角字母和数字不归一化的话“”和“123”生成的gram也完全不同。再就是把连续空白压缩成单个空格去掉首尾空格避免“同样的文本因为多一个空格被判低相似度”。要不要去标点取决于应用场景。文本去重时通常建议保留标点因为标点也是内容的一部分去掉后“你好世界”和“你好世界”会变成完全一样可能产生误判但如果你本来就想忽略标点差异那就在预处理阶段把标点替换成空格或直接删除。代码查重则千万别统一去掉标点符号、分号、括号对代码结构至关重要去掉后重排会带来大量假相似。所以预处理策略要和业务预期完全对齐否则后面所有参数都白调。数据清洗之后别忘了处理空字符串和短字符串。如果一个文本去掉空白后不到N个字符它无法生成任何N-Gram。此时应该定义相似度为0还是做单字符回退。我的做法是如果两段文本都短于N先尝试全文精确匹配匹配则相似度为1否则为0不匹配时再对补充的uni-gram集合算一次。这个过程虽然简单但能避免很多边界问题。3.2 生成N-Gram集合的代码下面是一个能直接用的Python实现。我一般把预处理、生成、相似度计算拆成三个函数方便测试和复用。import re import unicodedata from collections import Counter def normalize(text): if not text: return # 全角转半角NFKC对全角字母/数字/空格都有帮助 text unicodedata.normalize(NFKC, text) # 统一小写 text text.lower() # 把任意连续空白压成一个空格 text re.sub(r\s, , text).strip() return text然后是生成ngram集合。以字符级为例def char_ngrams(text, n2): text normalize(text) if len(text) n: return set() return {text[i:in] for i in range(len(text) - n 1)}这段代码已经足够日常使用。如果你需要带频次信息就把set换成Counterdef char_ngram_counter(text, n2): text normalize(text) if len(text) n: return Counter() return Counter(text[i:in] for i in range(len(text) - n 1))3.3 相似度计算实现有了集合或Counter相似度就是几行公式的事。def jaccard(a, b): if not a or not b: return 0.0 return len(a b) / len(a | b) def dice(a, b): if not a or not b: return 0.0 return 2.0 * len(a b) / (len(a) len(b))如果是Counter版本需要做交集运算时注意Counter Counter得到的是共同key的最小计数它天然就可以用来算交集总量。余弦相似度可以这样写def cosine_from_counter(c1, c2): if not c1 or not c2: return 0.0 common c1 c2 if not common: return 0.0 dot sum(c1[k] * c2[k] for k in common) norm1 sum(v * v for v in c1.values()) ** 0.5 norm2 sum(v * v for v in c2.values()) ** 0.5 if norm1 0 or norm2 0: return 0.0 return dot / (norm1 * norm2)这里返回0.0的处理很关键因为空集是没有可比性的不能因为两个空集合数学上相等就返回1。我见过有人在这里写出空集合除以空集合得到1的bug结果所有短文本都判成重复。3.4 一个完整的计算流程举个例子。a文本相似度算法b文本相似度计算按字符2-gram切分。a的2-gram集合是{文本,本相,相似,似度,度算,算法}共6个。b的2-gram集合是{文本,本相,相似,似度,度计,计算}也是6个。交集是{文本,本相,相似,似度}共4个。Jaccard是4/80.5Dice是2*4/(66)0.667。如果你用re正则匹配整套代码跑一遍得到的阈值要按这个数值去校准。两条文本明显高度相关但Jaccard只有0.5所以很多场景下Jaccard阈值不宜设得太高0.5左右反而能召回更多重复项。这段计算也说明了一个容易被忽略的问题N-Gram相似度不是一个“绝对分数”它受文本长度、字符分布影响很大。不同业务场景不能共用同一套阈值必须靠带标注的样本去调。第一次使用的人常常把阈值拍脑袋定成0.8结果一轮召回率低得离谱这不是算法的问题是阈值没跟数据集本身对齐。4. 实战在真实系统里怎么用4.1 文本去重用倒排索引避免两两比较把N-Gram直接用在去重时新人最常犯的错误是写一个双重循环把所有文本两两比较一遍。10万条文本的2-gram集合平均20个gram两两组合就有10^10次集合运算再简单也会卡死。正确的做法是先建倒排索引再用候选集合并行。具体是这样把每条文本的N-Gram作为key文档ID列表作为value。处理新文本时先求出它的N-Gram集合再把这些gram对应的文档ID都拉下来去重后得到候选集。这些候选文档都是至少和当前文档共享一个gram的理论上相似度才有意义。最后只对候选文档计算Dice/Jaccard。如果数据里随机相似度很低候选集通常只有几百甚至几十计算量能下降几个数量级。我做过一个评论去重任务原始数据12万条用倒排索引加Dice过滤后相似对候选中真正重复的命中率能到30%以上配合人工规则最后上线。这个方案的亮点是可以用Spark或ClickHouse轻松并行同一个gram下的文档再按哈希分桶各自算重叠。整个过程不需要任何模型晚上跑个批处理第二天早上出报告。4.2 搜索纠错N-Gram怎么当主角搜索框里的纠错场景N-Gram也很有用。用户输入一个词如果库里有近义词或历史纠错词表可以用N-Gram算当前输入和历史词表的相似度取分数最高的作为候选。中文输入法打出“歌手”错成“哥手”2-gram里“哥手”和“歌手”的交集为0因为“哥手”的bigram是“哥手”“歌手”是“歌手”但1-gram交集很高。所以纠错场景不能只用一个N我会同时算1-gram和2-gram分别设不同权重避免单个字的错误彻底击穿特征。比单纯编辑距离好的一点是N-Gram对拼音输入法产生的移位错误有一定容忍。比如“因为”和“为因”编辑距离是2两次交换才能变回去但2-gram集合完全重合Dice为1N-Gram会认为它们相似。而这类“词序颠倒”在真实输入里并不少见。你可以根据业务侧重点把N-Gram得分和编辑距离得分做一个加权融合例如0.6乘Dice加0.4乘归一化编辑距离往往能同时照顾两种错误模式。4.3 短文本聚类客服对话和新闻标题短文本聚类也是N-Gram的主场。客服工单分类、新闻标题聚合、App评论打标这些任务里文本通常不超过几十个字语义模型容易欠拟合N-Gram反而是稳定特征。我常用的做法是把每条短文本转成N-Gram集合然后用Dice作为距离度量直接跑DBSCAN。因为DBSCAN不需要预设簇数量只要把epsilon参数调成相似度阈值就能把高度重复的文本聚到一起。聚类结果能帮业务发现很多问题。比如在一次客服日志聚类里N-Gram自动把“我要退款”和“我想退钱”分到了两个簇虽然语义相同但字面不重叠。这不算算法缺陷反而提醒业务可能需要在系统里给这类同义表达配置同义词表。这就是N-Gram的特点它不会自作聪明地认为两句不同的话相似业务看到聚类结果时能清楚地知道哪些是真正的字面重复哪些需要人工干预。可解释性在这个场景里比聚类效果本身更重要。4.4 OCR容错把错误字吃进去OCR文本的一个特点是字符级别的替换、插入、漏读层出不穷。比如“功效”被识别成“功放”两个词差一个字但2-gram和3-gram都会改变。如果直接拿原文本做关键词匹配一个错别字就会导致匹配失败。用N-Gram做关键词模糊匹配时我会把匹配目标也切到同样N然后计算目标文本与文档每个窗口的相似度峰值超过阈值就认为命中。这样即使个别字认错周围正确的字仍然能组成gram把相似度撑起来。这个思路还能用于知识库的OCR质量检查。把标准文本和OCR输出都切成3-gram计算两者集合的Jaccard如果分数低于0.8大概率这段OCR结果有问题需要回流重新识别。N-Gram在这里起到了一个质量门禁的作用比人工抽检效率高很多。4.5 混合策略N-Gram做召回模型做排序工程落地时我很少只用N-Gram一条路走到黑。推荐的做法是分层第一层用N-Gram配上宽松阈值尽可能把所有可能相似的候选都捞出来第二层用代价更高的方法精排。比如先用字符2-gram的Dice把分数超过0.4的文本捞出来再用微调后的BERT向量做二次确认或者用关键词规则过滤。这样既利用了N-Gram的速度和召回率又避开了它“只管字面不管语义”的短板。分层还有一个额外好处你可以随时用不同模型替换第二层而第一层的N-Gram模块基本不用动。我在一个新闻查重系统里就是这么搭的N-Gram层拦截了90%的样本剩下10%才进模型人力成本和机器成本都降到很低。如果你的系统里还没有相似度模块这个分层架构是非常好的起点。5. 性能优化与参数调优5.1 存储把N-Gram变成整数IDN-Gram的存储经常被忽略等内存暴涨才想起来优化。字符串形式的N-Gram占内存很大一个由两个汉字组成的2-gram比如“文本”在Python里作为set元素占好几十字节。10万文本、每条文均20个gram就有200万个字符串对象内存轻松上GB。常见优化是把每个N-Gram哈希成一个64位整数再存成整型集合。整数比字符串省很多内存而且set求交速度快得多。更进一步的优化是用位向量先对所有N-Gram做一个词表给每个gram分配一个从0开始的ID然后每条文本的集合转成一个变长的bitmap或RoaringBitmap。交集运算在RoaringBitmap上可以做到极快还支持压缩存储。哈希要注意碰撞。用Python内置hash()或者CRC64碰撞概率在百万级gram上不算高但为了严谨我会在碰撞后拿原始字符串做二次确认。这一步虽然多花一点时间但能避免因为一个哈希碰撞导致两条完全不相关的文本被当成相似。5.2 MinHash百万级去重的杠杆如果数据量到了千万级或者你需要做近似去重而不是精确找相似MinHash是N-Gram经典搭档。核心思路是对每条文本的N-Gram集合用k个随机哈希函数分别取最小值得到k维签名。两个集合的签名相同比例近似于它们的Jaccard相似度。这等于把大集合压缩成了固定长度的签名集合运算变成一次内存友好的签名比较速度有量级提升。我自己做过一个千万级图片文字库的去重用MinHash生成128维签名再配合LSH局部敏感哈希做候选查找。实际速度和准确率都很理想。要注意的是MinHash得到的相似度是估计值k越大越准但内存和计算量也越大。通常128到256个哈希函数已经能应付大多数场景影响精度最大的其实是N-Gram本身的N选择和预处理签名只负责压缩不负责提炼特征。先把特征做对再谈压缩。5.3 参数调优三板斧第一板斧是选N。前面说过短文本用2长文本用3或4但这不是唯一答案。你应该拿一小批带标签的样本分别用N1、2、3算一遍相似度画出PR曲线看哪个N在业务容忍的误判率下召回最高。这个验证过程必须做依赖拍脑袋的经验往往会翻车。第二板斧是调阈值。通常做法是收集1000条正样本确认重复和1000条负样本确认不重复用Dice算分后画出分布图找一个能让正样本分和负样本分重叠最少的切分点。这个切分点就是业务阈值。我见过很多项目把阈值设成0.6但正样本平均分0.65误判一堆调成0.5反而刚好。第三板斧是处理停用和噪声。词级N-Gram可以考虑去掉停用词字符级N-Gram则可考虑忽略纯数字串或URL因为这些片段对相似度判断没有区分度反而会把两条完全不相关的文本拉近。预处理阶段把这类模式替换成统一占位符比如把邮箱、手机号替换成EMAIL能防止个人数据干扰相似度。6. 常见问题排查与避坑手册6.1 为什么N-Gram在某些场景会失效先说说失效模式。最典型的是同义词替换比如“价格便宜”和“价钱实惠”字面上几乎没重叠N-Gram分数接近0。这不是算法问题而是这类需求本来就超出了字面相似度的范围。解决思路有两个要么在预处理阶段引入同义词词典把所有同义词先归一到一个标准词要么索性改用语义向量把N-Gram只作为辅助信号。第二个失效模式是文本长度差异过大。一个300字的文档和另一个10字的摘要即使摘要就是文档中心句它们的N-Gram集合交集也可能很小。因为长文档的gram集合包含大量和摘要无关的片段并集被撑大分数被稀释。遇到这种情况先对长文档做滑动窗口切段再用窗口和短文本算相似度取最高分而不是整篇直接比。第三个失效模式是高频词主导。如果数据集中“的”“了”“在”这类字出现极频繁2-gram集合会被这些高频片段占领导致所有文本之间的相似度都虚高。字符级N-Gram没有天然的TF-IDF权重解决办法是在生成gram时对高频片段做停用或者引入DF文档频率加权的余弦——类似于TF-IDF的变体低频gram的权重更高。6.2 实操中的常见问题速查表问题可能原因排查方向相似度普遍偏低N值太大短文本gram太少降低N用2-gram相似度普遍虚高高频无意义片段太多加停用词/DF权重英文大小写不同判不相似预处理没有统一lower在normalize里加lower全角数字/字母不匹配没有NFKC归一化用unicodedata.normalize空文本和短文本报错没有处理len(text)n返回空集定义边界规则两两比较太慢O(n^2)全量计算换倒排索引或MinHash两条只差一个词却分数很低交集gram太少尝试N1加权或词级N-Gram这张表基本覆盖了我被问到的80%问题。关键是每个问题出来先别急着调算法把预处理流程从头到尾检查一遍通常能解决一半。6.3 几条我的实操心得第一预处理优先级最高。我曾经用一个文本去重需求数据里充满全角空格和不同的换行符一开始相似度结果乱得像噪声后来把全角空格统一、换行符压缩同一批数据的准确率从不到60%提到了90%以上。很多团队花大量时间调N和阈值却忽略预处理属于捡了芝麻丢西瓜。第二保存N-Gram集合比保存原文本更划算。如果数据量允许我建议在离线阶段把每条文本的N-Gram集合或Counter序列化存储线上直接读取特征计算相似度省掉每次请求时的切分开销。用一个protocol buffer或parquet文件存整型ID集合查询时内存映射加载性能提升非常明显。第三阈值要跟业务数据绑定。我见过同一个阈值在A数据集上效果很好换到B数据集上就推到重来因为数据来源、长度分布、噪声水平完全不同。所以上线前一定要用当天或历史真实样本做阈值回归不要拿着旧阈值用一年。相似度算法是一个需要持续维护的模块N-Gram本身虽然简单但把它嵌进业务系统后它需要和业务一起进化。提示N-Gram相似度不代表语义相似度这个边界要时刻记在脑子里。它解决的是“字面重复”的问题而不是“意思相同”的问题。业务文档里一开始就要写清楚适用范围不然算法上线后会被各种“我以为”的需求挑战。最后再分享一个我在部署时常用的落地技巧如果线上请求对延迟特别敏感可以把N-Gram集合预先算好并压缩成整型哈希集合再用RoaringBitmap或字典映射加载到内存。这样每次相似度计算就变成两次求交集延迟能压到几十微秒。我试过用这个方案支撑单机每秒上千次判重请求稳定跑了半年没出过问题。N-Gram虽然是个老算法但把它用到极致依旧能打。
阅读完成 · 觉得有帮助？
