0

0

C++如何进行字符串的Jaro-Winkler相似度计算?(姓名匹配算法)

穿越時空

穿越時空

发布时间:2026-03-05 08:42:41

|

470人浏览过

|

来源于php中文网

原创

不能直接用 std::string 比较姓名相似度,因为 == 无法处理错字、缩写、顺序颠倒、音近字等问题;jaro-winkler 能量化“看着像”的程度,尤其适合短字符串,但需注意 utf-8 下汉字切分、拼音预处理、前缀计算和浮点截断等关键实现细节。

c++如何进行字符串的jaro-winkler相似度计算?(姓名匹配算法)

为什么不能直接用 std::string 比较姓名相似度?

因为姓名常有错字、缩写、顺序颠倒(如“张三丰” vs “三丰张”)、音近字(如“李” vs “里”),==std::equal 会直接返回 false,而 Jaro-Winkler 能量化这种“看着像”的程度——它对前缀一致的字符串额外加分,特别适合中文姓名、英文名这类短字符串匹配。

jaro_winkler_similarity 函数怎么写才不出错?

标准库没有这个函数,必须手写或引入第三方。手写时最容易在「转置数计算」和「前缀缩放因子」上出错:比如把字符对交换次数算成绝对位置差,或把前缀长度截成固定 4 而不是实际公共前缀长度。下面是一个轻量、可读、避坑的 C++17 实现要点:

无序列表:

  • 先转成小写并过滤空格(std::transform + std::remove_if),避免“ZHANG SAN”和“zhangsan”被判为零分
  • 用两个 std::vector<size_t></size_t> 分别记录每个字符在对方字符串中的匹配位置,再遍历找「错位但可配对」的转置对,不要用双重循环暴力计数,否则 O(n³)
  • 前缀长度取 std::min({a.size(), b.size(), 4UL}),但实际公共前缀要逐字符比,不能硬截
  • 最后结果必须 clamp 在 [0.0, 1.0] 区间,浮点误差可能导致 1.0000001
double jaro_winkler_similarity(const std::string& a, const std::string& b) {
    auto clean = [](const std::string& s) {
        std::string out;
        for (char c : s) if (std::isalnum(c)) out += std::tolower(c);
        return out;
    };
    std::string s1 = clean(a), s2 = clean(b);
    if (s1.empty() && s2.empty()) return 1.0;
    if (s1.empty() || s2.empty()) return 0.0;
<pre class='brush:php;toolbar:false;'>// ...(匹配逻辑与转置数计算略,重点是按上述要点实现)
double jaro = /* 计算基础 Jaro */
int prefix_len = 0;
for (int i = 0; i < std::min({(int)s1.size(), (int)s2.size(), 4}); ++i)
    if (s1[i] == s2[i]) prefix_len++; else break;
return jaro + (0.1 * prefix_len * (1.0 - jaro));

}

立即学习C++免费学习笔记(深入)”;

Poly.ai
Poly.ai

AI电话语音服务助手,接听电话并自动回复客户。

下载

中文姓名用 Jaro-Winkler 有什么特殊问题?

直接套用英文版会严重失真:汉字是单字语义单元,但算法默认按字节/码点切分。UTF-8 下一个汉字占 3 字节,std::string[] 会切在中间,导致乱码匹配。所以必须先转成 std::u32string 或用 ICU 库做 Unicode 正规化。

无序列表:

  • 别用 s[i] 遍历原始 UTF-8 std::string,改用 std::wstring_convert<:codecvt_utf8>, char32_t>{}</:codecvt_utf8>(C++17 前)或 C++20 的 std::from_chars + UTF-8 解码逻辑
  • 拼音预处理更实用:调用 pypinyin(Python 后端)或集成 cppjieba + libpinyin 先转拼音再算,避免“王”和“汪”因字形近被判高分
  • 姓氏权重可单独加权:比如提取首字符后,对常见姓氏(“李”“王”“张”)在 Jaro 结果上乘 1.2,但需业务校准,不能硬编码

性能和线上部署要注意什么?

单次计算在百微秒级,但批量比对(比如 1 万条待匹配姓名 vs 100 万条库)会迅速变成瓶颈。Jaro-Winkler 本身不可索引,没法像 LIKE 'abc%' 那样走 B+ 树。

无序列表:

  • 预计算并缓存常用姓名对的结果,用 std::unordered_map<:pair std::string>, double></:pair>,注意自定义哈希——别直接用 std::hash<:string></:string> 套 pair
  • 加粗前置过滤:先用编辑距离 ≤2 或 n-gram(如 trigram)快速筛掉明显不相关的,再对候选集跑 Jaro-Winkler
  • 多线程别直接共享同一个 std::string 对象去并发调用,确保输入参数是值传递或 const 引用,避免隐式共享导致的写时复制(COW 已废弃,但某些 libstdc++ 版本仍有残留)

真正麻烦的是边界 case:空格、括号、中英文混排(如“Tom(汤姆)”)、生僻字(Unicode 扩展区),这些不会报错,但会让相似度值飘忽不定——得靠真实业务数据反复校验阈值,而不是信默认的 0.85。

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

930

2023.08.02

c语言const用法
c语言const用法

const是关键字,可以用于声明常量、函数参数中的const修饰符、const修饰函数返回值、const修饰指针。详细介绍:1、声明常量,const关键字可用于声明常量,常量的值在程序运行期间不可修改,常量可以是基本数据类型,如整数、浮点数、字符等,也可是自定义的数据类型;2、函数参数中的const修饰符,const关键字可用于函数的参数中,表示该参数在函数内部不可修改等等。

557

2023.09.20

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

698

2023.08.03

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

219

2023.09.04

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

1561

2023.10.24

字符串介绍
字符串介绍

字符串是一种数据类型,它可以是任何文本,包括字母、数字、符号等。字符串可以由不同的字符组成,例如空格、标点符号、数字等。在编程中,字符串通常用引号括起来,如单引号、双引号或反引号。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

645

2023.11.24

java读取文件转成字符串的方法
java读取文件转成字符串的方法

Java8引入了新的文件I/O API,使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java,可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中,你需要将文件路径替换为你的实际文件路径,并且可能需要处理可能的IOException异常。想了解更多java的相关内容,可以阅读本专题下面的文章。

1148

2024.03.22

php中定义字符串的方式
php中定义字符串的方式

php中定义字符串的方式:单引号;双引号;heredoc语法等等。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

1122

2024.04.29

PHP高性能API设计与Laravel服务架构实践
PHP高性能API设计与Laravel服务架构实践

本专题围绕 PHP 在现代 Web 后端开发中的高性能实践展开,重点讲解基于 Laravel 框架构建可扩展 API 服务的核心方法。内容涵盖路由与中间件机制、服务容器与依赖注入、接口版本管理、缓存策略设计以及队列异步处理方案。同时结合高并发场景,深入分析性能瓶颈定位与优化思路,帮助开发者构建稳定、高效、易维护的 PHP 后端服务体系。

4

2026.03.04

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C# 教程
C# 教程

共94课时 | 10.6万人学习

C 教程
C 教程

共75课时 | 5.2万人学习

C++教程
C++教程

共115课时 | 20.5万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号