★ FEATURED ARTICLE 做数据清洗的时候我经常要面对一个很现实的问题同一家公司的客户姓名在两个系统里写法不一样比如“张丽华”和“张丽桦”又比如英文名“JONATHON”被录成了“JONATHAN”到底该不该判成同一个人这时候Jaro-Winkler similarity就派上用场了。这个字符串相似度比较算法在处理短字符串、人名、拼写错误这类场景时非常稳它天然对前缀一致的字符串更友好所以特别适合做姓名去重、实体匹配、拼写纠错这类活儿。这篇文章我想把这套算法彻底讲透从公式原理、计算过程、代码实现到工程落地中的坑一次说清楚。无论你是要做数据清洗还是正在选型相似度算法或者纯粹想搞明白Jaro–Winkler和编辑距离Levenshtein distance到底差在哪这篇文章都值得你花十分钟看完。1. 内容整体设计与思路拆解1.1 为什么需要Jaro–Winkler这个字符串相似度算法先聊一个问题做字符串相似度比较工具库里明明有Levenshtein编辑距离、Dice系数、Cosine相似度为什么还要单独研究Jaro-Winkler similarity拿编辑距离举例它计算的是把一个字符串变成另一个字符串最少需要多少次插入、删除、替换。这很直观但有个毛病它对前缀差异非常敏感。举个例子“abcdef”和“abcxyz”编辑距离是3看起来好像和“abcdef”与“xbcdef”的编辑距离差不多但实际上人在判断时会觉得“abcdef”和“abcxyz”更像因为前三个字符完全一样而“abcdef”和“xbcdef”只有第一个字符不同后面全一样。编辑距离把这两种情况一视同仁这就导致在某些场景下排序会不符合直觉。Jaro–Winkler算法就是专门针对这个场景优化的。它在Jaro相似度的基础上给公共前缀加了一个权重前缀相同的字符越多相似度被抬得越高。这种设计非常贴合真实场景一个名字大部分情况是开头被正确记录越靠后的字符越容易录入出错。比如“McDonald”和“MacDonald”一看就知道是同一个因为前缀“M”和“Mac”的相似度摆在那里。另一个原因是Jaro–Winkler的计算效率很高。相比编辑距离需要维护一个二维DP表时间复杂度O(n*m)Jaro–Winkler可以通过一次遍历加两次字符匹配完成计算时间复杂度稳定在O(nm)内存占用也少。在数据量大、实时性要求高的场景下这个优势非常明显。1.2 算法家族的选型对比网上聊字符串相似度算法的文章很多但很少有文章把选型思路讲透。这里我把自己在项目中常用的几个算法做个对比方便你判断什么时候该用Jaro–Winkler算法核心思想时间复杂度擅长场景短板Levenshtein编辑距离最小编辑次数O(n*m)拼写纠错、DNA序列对前缀不敏感短字符串区分度差Jaro–Winkler字符匹配前缀加权O(nm)人名、地名、实体匹配对顺序打乱较敏感重排字符会扣分Dice系数字符bigram交集O(nm)文本相似度泛化短字符串容易误判Cosine相似度向量空间夹角O(nm)长文本、语义近似对字符级错拼不敏感这个对比表在真正的工程选型中非常实用。如果你只是判断一个单词是否拼错编辑距离就够如果你在做用户姓名匹配、地址标准化、脏数据合并Jaro–Winkler明显更合适如果你在做长文本的近似重复检测Dice或Cosine会更合适。我在实际项目里通常的组合方案是先用Jaro–Winkler粗筛一遍候选集再用编辑距离或人工规则做最终判定。这样既保证了速度又提高了准确率。后面在写实践细节的时候我会再展开。2. 核心原理拆解Jaro相似度与Winkler前缀加权2.1 Jaro相似度的基础计算逻辑Jaro–Winkler的基础是Jaro相似度两步走。第一步确定匹配字符与匹配窗口。给定两个字符串s1和s2首先确定一个匹配窗口match window。这个窗口不是随便定义的它由两个字符串的长度决定match_window max(len(s1), len(s2)) / 2 - 1注意这里的除法向下取整窗口大小至少为0。匹配窗口的含义是s1中的某个字符如果在s2中存在且位置差不超过这个窗口那么才认为它有机会成为匹配字符。这个设计是为了避免把相隔太远的字符强行配对。比如s1 abcdes2 axbycze虽然a在s1中位置0在s2中位置0可以匹配但e在s1中位置4在s2中位置6位置差为2如果窗口小于2e就不会计入匹配。这么做是为了防止一个字符串中的字符和另一个字符串中位置完全错乱的字符形成虚假匹配。第二步计算匹配字符个数和转置次数。匹配字符个数m很好理解就是在匹配窗口内能够对应上的字符总数。转置次数t就稍微绕一点。把s1中匹配到的字符按顺序取出来组成序列A把s2中匹配到的字符也按顺序取出来组成序列B然后比较A和B中位置不一致的字符对数目除以2就是转置次数。转置次数的大白话解释两个字符串里都有这些字符但它们出现的顺序不完全一致位置错位的对数就是转置的代价。得到m和t之后Jaro相似度的公式如下jaro (m/len(s1) m/len(s2) (m-t)/m) / 3这个公式由三部分组成s1中匹配字符比例、s2中匹配字符比例、匹配字符中未发生转置的比例。三个部分取平均所以Jaro相似度的取值在0到1之间1表示完全相同0表示完全不同。2.2 Winkler前缀加权的条件与公式Winkler的改进在于利用了一个观察两个字符串如果前缀一致它们属于同一实体的概率会增加。于是他在Jaro相似度上套了一个前缀提升因子。设公共前缀长度为l且l不超过4个字符超过4个后提升效果不再增加则jaro_winkler jaro l * p * (1 - jaro)其中p是前缀权重缩放因子标准取值为0.1。p的取值范围通常是0到0.25之间超过0.25会导致相似度过度膨胀可能把完全不相关的字符串判成近似。把p0.1和l的上限4代进去可以算出最大提升量是0.4 * (1 - jaro)这意味着即使完全相同前缀也只给到额外0.4的加权空间不会突破1。还有一个容易被忽略的细节Winkler并不是对所有情况都做前缀加权而是有一个阈值判断。常见做法是只在Jaro相似度大于某个阈值比如0.7时才启动加权。如果两个字符串本身的Jaro相似度很低说明它们差异太大即使前缀相同也不应该被强行拉近。这个阈值在很多实现里可以根据业务调整比如在姓名匹配场景中我会把阈值调到0.7或0.75既保留了对正确匹配的宽容度又不会让错误匹配钻空子。2.3 一个逐步计算的经典例子空谈公式不好懂我们来跑一遍。以经典的“MARTHA”和“MARHTA”为例。s1 MARTHA长度6s2 MARHTA长度6。匹配窗口 max(6,6)/2 - 1 3 - 1 2。窗口是2意味着字符位置差不能超过2。逐个字符检查M: s1位置0s2位置0差0匹配。A: s1位置1s2位置1差1匹配。R: s1位置2s2位置2差2匹配。T: s1位置3s2中T在位置4差1匹配。H: s1位置4s2中H在位置3差1匹配。A: s1位置5s2位置5差0匹配。m 6且按照匹配顺序提取序列s1匹配序列是MARTHAs2匹配序列是MARHTA。这个例子中第3和第4个字符T和H的顺序发生了交换s1里T在H前s2里H在T前。所以顺序不一致的对数是2转置次数t 2 / 2 1。代入公式jaro (6/6 6/6 (6-1)/6) / 3 (1 1 0.8333) / 3 0.9444然后看前缀M、A都是相同字符第三个字符s1是Rs2也是R相同。第四个字符s1是Ts2是H不同。公共前缀长度l 3。由于jaro0.9444大于0.7启用Winklerjaro_winkler 0.9444 3 * 0.1 * (1 - 0.9444) 0.9444 0.0167 0.9611最终相似度0.9611非常接近1。完全符合直觉MARTHA和MARHTA就是同一个人名的拼写变体。再举一个不那么匹配的例子s1 DIXONs2 DICKSONX。这个例子很多人第一次算会蒙。s1长度5s2长度8。窗口 max(5,8)/2 - 1 4 - 1 3。s1中D、I、O、N都可以在s2中找到对应字符且位置差不超过3X在s2中多出来。m 4。提取匹配序列时s1的匹配序列是DIONs2的匹配序列是DICKSONX中按顺序取匹配字符D、I、C、K、S、O、N筛出匹配字符是DION但注意O和N在s1位置是2和4在s2位置是5和7顺序一致转置次数t 0。代入公式jaro (4/5 4/8 (4-0)/4)/3 (0.8 0.5 1)/3 0.7667。Winkler前缀l 2D、I相同jaro 0.7加权后 jaro_winkler 0.7667 20.1(1-0.7667) 0.8133。这个结果可以让业务方接受这是一个候选项。2.4 边界条件与特殊字符串处理Jaro-Winkler虽然好用但边界条件一定要搞清楚否则线上会出各种隐蔽bug。空字符串任何一个字符串为空相似度直接判为0。两个都为空严格来说可以认为是1但工程上我更建议返回1并单独处理因为业务上两个空名字不应当被合并成同一个人。匹配窗口小于0当某个字符串长度为1时窗口 max(1, n)/2 - 1如果n很小窗口可能为0甚至负数。比如s1As2B窗口0那只有位置差为0的字符才可能匹配。这种情况下m可能等于0带入公式会出现除零错误。常规做法是当m0时直接返回0不进入转置计算。单字符字符串对比s1As2A窗口0m1jaro(1/1 1/1 (1-0)/1)/3 1。s1As2Bm0返回0。s1As2AB窗口0s2中A在位置0和s1的A位置差0匹配m1jaro(1/1 1/2 1/1)/3 0.8333。看起来还算合理。大写与空格Jaro-Winkler本身区分大小写且不处理空格所以在中文业务场景里一定要先做预处理统一转成小写或大写、去除多余空格、全半角转换。这个问题我在后面实操部分会重点讲。字符串长度差异极大比如s1As2是一个100字符的字符串即使前缀完全一致Jaro相似度也会被s2的长度拉低。因为公式里m/len(s2)很小。这在业务上通常是合理的短字符串和长字符串很难是同一个实体。但如果业务需要匹配“缩写”和“全称”比如“IBM”和“International Business Machines”Jaro-Winkler几乎帮不上忙得考虑专门做缩写字典。3. 实操过程与代码实现3.1 从零实现Jaro-Winkler相似度算法的Python版本算法原理搞清楚了代码实现其实没有那么难。我建议每个想深入用这个算法的朋友至少手写一遍不要一上来就调库。手写一遍你才能真正理解匹配窗口、转置次数的含义后面遇到诡异结果时也能更快定位问题。下面这个Python实现是我在项目中验证过的版本稍微做了优化逻辑清晰可以直接抄作业def jaro_similarity(s1: str, s2: str) - float: if not s1 or not s2: return 0.0 if s1 s2: return 1.0 len1, len2 len(s1), len(s2) match_window max(len1, len2) // 2 - 1 match_window max(match_window, 0) s1_match [False] * len1 s2_match [False] * len2 matches 0 for i in range(len1): start max(0, i - match_window) end min(i match_window 1, len2) for j in range(start, end): if s2_match[j]: continue if s1[i] ! s2[j]: continue s1_match[i] True s2_match[j] True matches 1 break if matches 0: return 0.0 # 收集匹配字符序列计算转置次数 seq1 [s1[i] for i in range(len1) if s1_match[i]] seq2 [s2[j] for j in range(len2) if s2_match[j]] transpositions 0 for k in range(len(seq1)): if seq1[k] ! seq2[k]: transpositions 1 t transpositions // 2 return (matches / len1 matches / len2 (matches - t) / matches) / 3.0 def jaro_winkler_similarity(s1: str, s2: str, p: float 0.1, max_prefix: int 4, prefix_weight_threshold: float 0.7) - float: js jaro_similarity(s1, s2) if js prefix_weight_threshold: return js prefix_len 0 for i in range(min(len(s1), len(s2), max_prefix)): if s1[i] s2[i]: prefix_len 1 else: break return js prefix_len * p * (1 - js)这段代码有两个细节值得注意。第一匹配窗口我用了max(len1, len2) // 2 - 1这是主流的定义方式。也有一些实现会加上abs(len1 - len2)之类的调整项但我实测下来标准定义更稳定也更容易和别人的结果对齐。第二转置次数是顺序不一致字符对数的一半所以最后要// 2。有的文章会把transpositions直接当作t这是错误的会导致相似度被人为压低。用上面两个例子验证一下print(jaro_winkler_similarity(MARTHA, MARHTA)) # 0.9611111111111111 print(jaro_winkler_similarity(DWAYNE, DUANE)) # 0.8400000000000001 print(jaro_winkler_similarity(DIXON, DICKSONX)) # 0.8133333333333334结果和标准参考值一致。3.2 工程中直接使用的标准库方案如果不想重复造轮子业界常用的几个库可以直接拿来用。我这里比较推荐下面三个jellyfish老牌的字符串相似度库性能不错接口干净。jellyfish.jaro_winkler_similarity(s1, s2)一行搞定。但它内部实现里p值固定为0.1max_prefix固定为4阈值判断也是写死的。好在这些参数是数学上最常用的标准配置大部分场景下足够了。textdistance这个库更像一个算法集合里面实现了30多种距离和相似度算法包括Jaro-Winkler、Levenshtein、Damerau-Levenshtein等。它的优势是方便做横向对比调试时特别好用。如果业务方问“你俩这个相似度是不是太低”我通常会直接用textdistance跑一排版对比把Jaro-Winkler、Dice、编辑距离的结果拉出来看看是不是只有这个算法表现特别异常。fuzzywuzzy / RapidFuzzfuzzywuzzy基于Levenshtein做了很多封装本身不提供Jaro-Winkler。但RapidFuzz里同时提供了Jaro和Jaro-Winkler而且RapidFuzz的C实现非常快处理上百万条字符串时优势明显。如果你在做一个调用量很大的服务我建议直接用RapidFuzz。具体用法如下# pip install jellyfish import jellyfish print(jellyfish.jaro_winkler_similarity(MARTHA, MARHTA)) # 0.9611111111111111 # pip install textdistance import textdistance print(textdistance.jaro_winkler.similarity(MARTHA, MARHTA)) # 0.9611111111111111 # pip install rapidfuzz from rapidfuzz.distance import JaroWinkler print(JaroWinkler.similarity(MARTHA, MARHTA)) # 0.9611111111111111从工程角度我更推荐RapidFuzz因为它不只是提供Jaro-Winkler还提供了一整套模糊匹配工具包括process.extractOne这种批量查询接口能直接从一个字符串列表中找出最相似的前K个候选配合C底层的速度在线上服务里非常能打。3.3 Java实现版本与SpringBoot集成思路搜“字符串相似度算法”的人里很多是Java后端这里我补一个Java实现。网上有很多人问怎么在业务系统里集成这种算法其实思路都差不多。public class JaroWinkler { public static double similarity(String s1, String s2) { if (s1 null || s2 null) { throw new IllegalArgumentException(Strings must not be null); } if (s1.equals(s2)) { return 1.0; } int len1 s1.length(); int len2 s2.length(); if (len1 0 || len2 0) { return 0.0; } int matchWindow Math.max(len1, len2) / 2 - 1; matchWindow Math.max(matchWindow, 0); boolean[] s1Matched new boolean[len1]; boolean[] s2Matched new boolean[len2]; int matches 0; for (int i 0; i len1; i) { int start Math.max(0, i - matchWindow); int end Math.min(i matchWindow 1, len2); for (int j start; j end; j) { if (s2Matched[j]) { continue; } if (s1.charAt(i) ! s2.charAt(j)) { continue; } s1Matched[i] true; s2Matched[j] true; matches; break; } } if (matches 0) { return 0.0; } StringBuilder sb1 new StringBuilder(); StringBuilder sb2 new StringBuilder(); for (int i 0; i len1; i) { if (s1Matched[i]) { sb1.append(s1.charAt(i)); } } for (int i 0; i len2; i) { if (s2Matched[i]) { sb2.append(s2.charAt(i)); } } String seq1 sb1.toString(); String seq2 sb2.toString(); int transpositions 0; for (int i 0; i seq1.length(); i) { if (seq1.charAt(i) ! seq2.charAt(i)) { transpositions; } } double t transpositions / 2.0; double jaro (matches / (double) len1 matches / (double) len2 (matches - t) / matches) / 3.0; // 计算Jaro-Winkler if (jaro 0.7) { return jaro; } int prefix 0; for (int i 0; i Math.min(Math.min(len1, len2), 4); i) { if (s1.charAt(i) s2.charAt(i)) { prefix; } else { break; } } return jaro prefix * 0.1 * (1 - jaro); } }在SpringBoot里集成这个算法我一般把它做成一个工具类然后在Service层做一个批量去重接口。比如客户表里有10万条记录前端上传一批新客户名单后端先做数据清洗、统一格式然后对每一条新记录调用JaroWinkler.similarity遍历已有客户找出相似度高于0.9的候选再结合其他业务规则比如手机号、身份证做最终合并。这个方案我们实测在100万规模内响应时间都在几十毫秒内性能上没有压力。3.4 参数计算结果对比与调参经验很多朋友第一次用Jaro-Winkler时会有一个困惑代码跑出来了分数也能算但不知道阈值该设多少。这个事儿真没有标准答案但如果给一个经验范围我推荐按场景来场景推荐阈值理由精确去重同一人/同一地址0.90以上容忍极小的拼写差异误报率最低中等容错同义词、别称0.800.90能覆盖大多数姓名的常见错误宽匹配候选集预筛选0.700.80宁可多召回后续再用规则过滤下限Jaro阈值0.7低于这个值Winkler wouldnt even apply强行使用加权会误判有一个很常见的坑是业务方觉得自己数据质量差于是把阈值调到0.6甚至更低结果相似度全在0.6-0.7之间无法区分。这个问题的根源不在于阈值低了而在于没有理解Jaro-Winkler只适合短字符串容错匹配。如果数据里除姓名外还混了地址、公司名这些长文本相似度会被预期拉低此时应该把长文本单独用Dice或Cosine算法来计算而不是强行用低阈值。我踩过一次坑早期做商品名去重时直接用Jaro-Winkler比对一堆几十个字符的句子结果各种奇怪误报。后来我把商品名先拆成核心词品牌型号规格核心词之间用Jaro-Winkler剩余部分用Dice系数准确率一下子提升了很多。算法没有银弹组合使用才是王道。4. 常见问题与实战避坑4.1 中文场景下的Jaro-Winkler表现与处理方式Jaro-Winkler最初是为英文字符串设计的对中文的支持属于“能用但不够聪明”。原因很好理解中文没有空格分词字符单位是汉字一个汉字在匹配窗口内找对应字符时和英文的字母逻辑一样但中文姓名通常只有2-4个字信息量小单字错位对相似度的影响会被放大。比如“王小明”和“王晓明”长度都是3窗口0max(3,3)/2-1 0只有位置完全匹配的字符才能算匹配。王匹配小匹配明和晓错位不匹配。m2jaro(2/3 2/3 (2-0)/2)/3 0.7778。公共前缀l2“王小”相同jaro 0.7加权后0.7778 20.1(1-0.7778)0.8223。这个值能提示我们这是潜在匹配但不够高。换成人名如果变成“张丽华”和“张丽桦”最后那个字不同m2l2结果也差不多0.82左右。这就是我说中文短文本信息量不足的原因。实战建议做中文姓名匹配时先对姓氏单独判断中文姓氏比较有限可以搞一个常见姓氏表姓氏匹配名字Jaro得分组合出一个综合分数。将全名字符串按长度补齐后计算我试过在名字前后填充分隔符效果不稳定不如上面那种拆姓氏方式可靠。对于中文地址、公司名这种长文本不建议直接用Jaro-Winkler先做分词提取行政区划、道路、门牌等关键片段再逐段比较。4.2 数据预处理里最容易被忽略的三个细节Jaro-Winkler对输入数据非常敏感这里三个预处理细节能救你很多次大小写统一。Jaro-Winkler严格区分大小写。你的数据源如果既有“john”又有“John”直接比较结果会偏低。统一走.lower()或.upper()一般建议全小写。全半角与特殊符号。中文系统里经常混着全角字符和半角字符。比如“”全角和“john”半角肉眼一样算法眼里完全不同。必须用.translate()或者正则做全角转半角。另外带连字符的名字比如“Jean-Pierre”和“Jean Pierre”建议把连字符、多余空格、句点统一替换成空字符串或者同一个分隔符。去除业务噪声。客户从不同渠道录入时可能会带“先生” “女士” “个人”这种后缀或者“某某有限公司”这种公司类型的噪声词。在做姓名或公司名匹配前建议先维护一个通用词表把这些词去掉。这一步比后面调任何参数都管用我用一句话概括预处理做得好相似度算法省心一半。4.3 性能优化百万级数据下怎么跑如果你要把Jaro-Winkler用在全量数据清洗上最怕的就是两个大列表两两对比那就是O(n*m)的复杂度。100万条对100万条算到天荒地老。我实际用的优化方案有三种方案一长度桶过滤。如果两个字符串长度差超过一定比例比如30%它们的Jaro相似度理论上是有上限的。可以直接用长度差做粗筛只在长度接近的候选对里计算Jaro-Winkler。实现起来简单效果却很显著。方案二前缀索引 候选集。因为Jaro-Winkler对前缀加权很大所以可以拿前2-3个字符建倒排索引。只对前缀相同或相近的记录计算相似度。注意这里不是全文扫描而是先缩小候选集。如果有拼音或者别的索引字段也可以用。方案三用RapidFuzz的process.extractOne。这个接口内置了阈值过滤和批处理能力底层是C性能比我手写的Python循环快几十倍。在单机百万级数据里基本是秒级出结果。如果你还嫌慢可以考虑多进程并行切分数据或者上Redis之类缓存住预处理的字符串向量。4.4 相似度算法的实际应用场景扩展写完基础实现之后你会发现Jaro-Winkler能玩的花样挺多。这里列几个我实际做过或见过的应用供你参考拼写纠错。搜索引擎或输入法里的“你的意思是不是XXX”提示候选词就是通过Jaro-Winkler从词库里捞出来的。词库几万个词每次输入都全量匹配不现实但配合前缀索引效果非常不错。数据库记录合并Record Linkage。两个CRM系统合并客户数据时把姓名、电话、地址三个字段分别算相似度再加权得到一个综合匹配分。Jaro-Winkler在姓名这个字段上往往比编辑距离表现好主要就是因为它更贴近人对名字相似度的主观感受。日志聚类。服务日志里大量报错文本只有细微差异比如时间戳、IP、用户ID。用Jaro-Winkler可以把重复日志聚成一类方便定位高频故障。这里需要注意把动态字段先做正则替换再比较。地理信息匹配。地名、路名这种短字符串Jaro-Winkler在容错上表现不赖。比如用户输入“北京中关村大街”和“北京中官村大街”Jaro-Winkler能识别为同一地点候选。5. 写在最后的实操心得我大概从四年前开始真正大规模使用Jaro-Winkler similarity中间踩过的坑比看过的文档还多。一个很大的体会是这算法不是用来替代其他相似度算法的而是用来给它们在短字符串、前缀敏感的场景里做互补的。在它之前我默认用编辑距离表面上很严谨实际上在处理人名、地名时经常被业务方挑战“这俩明明差不多啊怎么分数这么低”。换成Jaro-Winkler之后这种抱怨少了很多。还有一点想提醒算法参数别乱调。网上很多文章喜欢教你把p调到0.2、把max_prefix调到10好像分值高了就更好用。实际上一旦提高前缀权重很容易把“AB”和“ABCXYZ”这种前缀相同但实际没什么关系的字符串拉出高分。我在项目里一般保持p0.1、max_prefix4、阈值0.7这个标准配置只有在特定场景下才微调阈值从不改p和max_prefix因为数学上这两个参数被大量实验验证过稳定性更高。如果你正在做数据清洗或者实体匹配最后建议你做一个简单的对照实验拿人工标注好的1000对数据分别用Jaro-Winkler、编辑距离和Dice系数跑一遍画出ROC曲线或者人工挑几十个典型案例看效果。很多时候算法选型的答案不在论文里在你自己的数据里。用Jaro-Winkler跑一遍再结合业务规则这套组合拳基本能覆盖八成以上的字符串匹配需求。
阅读完成 · 觉得有帮助？
