在计算机科学中，字符串相似度是指两个字符串在内容上有多少相似之处。在现代计算机科学中，字符串相似度常被用于纠错、信息检索、数据挖掘等领域。在C++编程中，有很多算法可以用来比较字符串相似度，下面将介绍两种常用的算法：Levenshtein距离和Jaro-Winkler距离。

一、Levenshtein距离

Levenshtein距离又叫编辑距离，是指两个字符串间由一个转换为另一个所需的最少编辑操作次数。编辑操作包括插入一个字符、删除一个字符和替换一个字符。Levenshtein距离越小，表示两个字符串的相似度越高。

C++实现：

int LevenshteinDistance(const string& str1, const string& str2)

{

  int len1 = str1.size();

  int len2 = str2.size();

  vector > dp(len1 + 1, vector (len2 + 1, 0));

  for (int i = 0; i <= len1; i++) dp[i][0] = i;

  for (int i = 0; i <= len2; i++) dp[0][i] = i;

  for (int i = 1; i <= len1; i++) {

    for (int j = 1; j <= len2; j++) {

      if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];

      else dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));

    }

  }

  return dp[len1][len2];

}

二、Jaro-Winkler距离

Jaro-Winkler距离是在Jaro距离的基础上增加一个字符串前缀的权重值，用于更好地处理短字符串的相似度。Jaro-Winkler距离也是计算两个字符串之间的编辑操作次数，但是比Levenshtein距离更适合短字符串。

C++实现：

double JaroWinklerDistance(const string& str1, const string& str2)

{

  int len1 = str1.size(), len2 = str2.size();

  int m = max(len1, len2), l = 0, w = 0;

  double dj = 0.0, p = 0.1;

  if (len1 == 0 || len2 == 0) return 0;

  if (len1 < len2) swap(str1, str2), swap(len1, len2);

  for (int i = 0; i < len1; i++) {

    for (int j = max(0, i - m); j <= min(len2 - 1, i + m); j++) {

      if (str1[i] == str2[j]) {

        if (i == j) dj += 1.0;

        else if (i != j && str1[i] != str2[j]) w += 1;

        break;

      }

    }

  }

  if (dj == 0) return 0;

  dj = dj / len1;

  double dw = (double)w / 2.0;

  double lp = 0.1;

  int lmax = min((int)str1.size(), 4);

  for (int i = 0; i < lmax && i < len2 && str1[i] == str2[i]; i++) lp += (double)p * 1;

  return dj + dw / len1 + lp * (1 - dj);

}

总结

Levenshtein距离和Jaro-Winkler距离都是常见的用于字符串相似度比较的算法。在实际应用中，可以根据不同的需求和字符串长度，选择相应的算法进行应用。

相似文章
• 不要返回C++函数中的局部变量引用
  C++是一门相对来说高级的编程语言。其中最常见的编程范式就是面向对象编程（OOP）。这种编程方法最基本的概念就是对象。对象是实例化的类，它可以包含属性和方法。在C++中，函数是对象的重要组成部分。
  
  
• 如何在C++中实现自动设置变量？
  在C++编程中，有时候需要在代码中自动设置变量的值，以免手动设置出错。以下是如何在C++中实现自动设置变量的方法：
  
  
• C和C++有哪些区别？哪个更难？
  C和C++是两种编程语言，都是使用广泛的编程语言之一。尽管它们在语法和用途上有相似之处，但它们之间还是存在一些显著的区别。
  
  
• 使用C++编程求圆周率的近似值——用pi/2。
  Pi是一个不断求解的数学常数，称为圆周率。自古以来，人们一直在寻找更准确的方法来计算它。在计算机科学领域中，C++编程是一种有效的方式来实现这一目标，并且可以得到不少的近似值。
  
  
• 为什么C++变量定义要在开头？
  C++语言在定义变量时，要求变量定义必须放在程序开头。这一点与其他一些语言有所不同，例如Java语言、C#语言和Python语言等都不需要在开头完成变量定义。
  
  
• C++统计字符串单词个数
  C++是一种非常强大的编程语言，它可以用于各种计算机程序的开发。在C++中，我们可以使用各种函数和类来完成任务，在本文中，我们将介绍如何使用C++来统计字符串中的单词数量。
  
  
• C++实现查找两个数的最大公约数
  C++是一种常用的编程语言，它可以用来实现很多功能。其中，查找两个数的最大公约数是一个比较常见的算法需求。在C++中，我们可以使用欧几里得算法（辗转相除法）来实现。
  
  
• C++客户端开发人员招聘
  我们公司目前正在寻找有经验的C++客户端开发人员，如果您对此有兴趣并符合以下条件，欢迎加入我们的团队。
  
  
• 使用C++将输入的字母转换为对应的ASCII码值
  在计算机科学中，ASCII码是一种标准化的字符编码系统，用于将文本字符和其他符号映射为唯一的数字标识。在C++编程中，我们可以使用一些简单的代码将输入的字母转换为相应的ASCII码值。
  
  
• C++的面积函数
  C++是一种面向对象的编程语言，具有高效、可靠和更易于维护的特点。在C++中，面积计算是一个经常被用到的功能。本文将介绍如何在C++中编写面积函数。
  
  
• "C++竞赛常用函数大全"
  C++语言是一个广泛应用的编程语言，尤其在计算机竞赛领域中，其表现出色，成为强大的工具。C++语言具有丰富的库函数，可以帮助程序员开发高效率的竞赛程序。下面列出了一些常用的C++函数，对于参加竞赛的学生来说，这些函数将是非常有用的。
  
  
• Visual C++如何导入项目？
  Visual
  
  
• C++与Python如何编写进度条
  编写进度条是在编写任何程序时都可能遇到的一项常见需求。无论是C++还是Python，都有各自的方法来实现进度条的编写。下面详细介绍一下这两种编程语言如何编写进度条。
  
  
• C++数组如何进行赋值操作？
  在C++编程中，数组是一种非常常见且重要的数据类型。数组可以存储多个相同类型的变量，它们在内存中是连续存储的。在实际开发中，我们常常需要对数组进行赋值操作，本文将探讨C++数组如何进行赋值操作。
  
  
• C++如何判断数组中元素的大小？
  在C++中，判断数组中元素的大小是一个非常常见的操作。实际上，数组中每个元素的大小是可以直接用sizeof运算符来得到的。sizeof运算符返回一个对象或一种类型所占用的字节数。
  
  
• C++的构造函数是否允许返回值？
  C++的构造函数是一种特殊的成员函数，用于创建对象并初始化对象的数据成员。一般情况下，构造函数不允许有返回值，因为构造函数是用来初始化对象的，其返回值是对象本身，与通常的函数返回值不同。
  
  
• C++字符集简介
  C++作为一种计算机编程语言，不仅支持数值型数据的操作，也支持字符型数据的处理。而字符型数据的处理，也需要考虑到字符集的问题。
  
  
• C++算法：辗转相除法求最大公约数
  在数学中，最大公约数是指两个或多个整数的公共因子中最大的一个。C++语言中，我们可以使用辗转相除法来求解最大公约数。
  
  
• C++中的for循环语句嵌套
  在C++编程语言中，for循环语句的嵌套是非常常见的一种写法。通过嵌套使用多个for循环，可以使程序更加高效地完成一些重复性任务。
  
  
• C++递归函数求最大公约数：求x,y的最大公约数
  C++是一门非常强大的编程语言，在数学计算中，尤其是在求解最大公约数时，也可使用C++来帮助我们快速地完成计算工作。
  
  
• C++基础教程》：深入浅出掌握C++编程基础
  在当今数字化快速发展的世界中，计算机技术被广泛应用，成为人们生活中不可或缺的一部分。而C++作为一种高级程序语言，在计算机编程中也越发重要。C++有着比较高的效率和灵活性，且在多种领域都有着广泛应用。同时，想要学习更加高级的计算机语言，也需
  
  
• C++常用头文件详解
  C++是一种高级语言，它允许开发人员编写各种应用程序，包括桌面应用程序、移动应用程序、游戏、网络应用程序等。在C++开发中，头文件是非常重要的组成部分。它们包含了一些已经定义好的常用函数、类、变量等，可以帮助开发人员避免重复编写代码，提高开
  
  
• C++如何控制控制台输出位置？
  在C++中，我们可以使用控制台输出来显示打印出来的信息，但有时候我们可能需要将输出位置移动到控制台窗口的特定位置。在这种情况下，我们需要使用一些特定的代码来控制控制台输出的位置。
  
  
• C++和Golang，选择哪一个进行学习？
  C++和Golang是两种具有不同特点的编程语言。C++是一种面向对象的编程语言，适用于开发更加底层的应用程序，如操作系统和数据库。而Golang则是一种更加现代化，更加注重并发性能的编程语言，适用于构建高并发的网络服务等应用。
  
  
• 用递推求解c++猴子吃桃问题
  题目描述：猴子第一天摘了若干个桃子，当即吃了一半，感觉不饱又吃了一个。第二天早上一看，还剩下桃子的一半，照此办理，到第
  
  
• C++中的加法函数add()
  C++是一种面向对象的编程语言，它广泛应用于各种领域，如计算机图形、图像处理、游戏开发等等。在C++中，加法操作是最常见的数学操作之一，因此C++提供了一个名为add()的函数来实现加法操作。
  
  
• C++中的异常处理
  C++中的异常处理是一种非常重要的编程技术。异常处理可以帮助程序员在代码运行出现错误时通过改变程序的控制流来控制程序的行为。简而言之，C++中的异常处理是一种机制，它可以捕获并控制程序中的错误。
  
  
• C++类的地址是什么？
  在C++中，类是一种用户自定义的数据类型。类包含成员变量和成员函数，它们描述了数据类型的行为和属性。但是，许多初学者会感到困惑：类的地址是什么？
  
  
• C++取余操作
  C++中的取余操作是一种非常常用的数学运算操作。在C++中，我们可以使用百分号（%）来进行取余操作。其语法规则为：
  
  
• 如何取消C++中的函数覆盖？
  在C++中，函数覆盖是指派生类重写基类函数的过程。派生类可以重写基类中的函数，并且在调用基类的函数时，会优先调用派生类中的函数。然而，在某些情况下，我们需要取消函数覆盖，这可能会涉及到多层继承和虚函数表的概念。
  
  
• C++ 图片处理代码
  C++是一种高级语言，被广泛应用于计算机科学与软件工程中，尤其在图像处理方面。在图像处理中，C++语言提供了强大和灵活的功能，可以让程序员进行复杂的图像处理操作。下面是一些常用的C++图像处理代码。
  
  
• C++如何将字符串中的小写字母转换为大写字母？
  在C++编程中，有时候需要将字符串中的小写字母转换为大写字母。这个功能在某些场景中非常有用，比如进行字符串比较时，需要先将字符串中的所有字母转换为大写或小写字母，才能正确比较字符串的大小。在这里，我们将介绍两种将字符串中的小写字母转换为大写
  
  
• C++中单引号的含义是什么？
  在C++语言中，单引号（'）的含义是字符常量。字符常量是指只包含一个字符的常量。可以使用单引号将一个字符括起来，表示该字符是一个字符常量。字符常量的类型是char。
  
  
• C++快速判断质数的方法
  质数在数学中具有重要的地位，它是指只能被1和它本身整除的自然数。如何判断一个数是否为质数一直是计算机编程中的一个热门话题。在C++编程中，有许多方法可以用来快速判断一个数是否为质数，其中最常用的是欧拉筛法和米勒-拉宾素性测试法。
  
  
• C++入门书》百度云下载
  对于许多想要学习编程的人来说，C++是一个非常有用的编程语言。它是一种高级语言，经常用来编写非常复杂和大型的程序。学习C++需要一定的坚持和努力，但是它的应用范围非常广泛，可以应用于游戏开发、图形图像处理、机器学习等各种领域。如果你真的想学
  
  
• C++ Boost Asio：提高网络编程效率的利器
  C++
  
  
• C++小游戏编程：石头剪刀布
  石头剪刀布是一款非常简单又有趣的游戏，几乎让人们在任何时间和地点都可以玩。如果你爱玩石头剪刀布，为什么不尝试一下使用C++语言编写自己的石头剪刀布游戏呢？
  
  
• C++生成列表教程
  C++是一种十分重要的编程语言，也是广大程序员们常用的语言之一。C++有许多优点，例如高性能、易于调试、代码复用等等。在C++中，我们常常需要生成列表，这是一项重要的技能。接下来，我们就来看一下如何使用C++生成一个列表。
  
  
• 如何在C++中使用pi值
  在C++中使用π值可以实现一些数学计算和科学计算。π指的是圆周率，是一个无限不循环小数，通常用3.14或22/7来进行近似表示。在C++中，可以通过定义一个常量来使用π值。
  
  
• C++中如何表示16进制数
  C++是一种十分流行的编程语言，被广泛应用于各个领域。在C++中，我们可以使用不同的方式表示数字，比如十进制、二进制和十六进制等。本文将介绍C++中如何表示十六进制数。
  
  
• C++如何逆序输出数字数组
  在进行C++编程时，有时需要逆序输出数字数组。下面将介绍使用C++代码来实现逆序输出数字数组的几种方法。
  
  
• C++常用的开发工具有哪些？
  C++作为一种高性能的编程语言，被广泛应用于各种应用领域，如游戏开发、操作系统等。C++开发过程中需要配合多种工具进行开发、编译和调试。那么，C++常用的开发工具有哪些呢？
  
  
• C++编译错误提示：无法解析的外部符号public。
  近日，一些C++程序员遇到了一个常见的编译错误提示：无法解析的外部符号public。这种错误提示通常出现在使用类或函数时，未能正确引用相关的头文件或库文件，在编译时出现错误。
  
  
• C++里的问号是什么？
  在C++编程中，问号是一个非常重要的符号，它常常被用来表示条件运算符，也称为三元运算符。
  
  
• 黑马匠心精作：C++教程
  随着社会的发展，计算机技术越来越重要。而掌握好计算机技术，对于我们职场的竞争、个人的发展都有着重要的意义。而其中，C++编程语言是一个非常重要的领域。C++是一种高效而强大的编程语言，被广泛应用于计算机科学、游戏开发、图形图像处理等领域。
  
  
• Linux下C++编程入门指南
  Linux是开源界最为灵活、最为强大的操作系统之一，而C++则是一种高效的编程语言。如果你想要深入学习Linux系统和C++编程语言，那么这篇文章将为你提供一份入门指南。
  
  
• Dev C++ 为什么无法保存文件？
  Dev
  
  
• C++中如何删除一维数组？
  在C++中删除一维数组有多种方法。以下是其中的两种常用方法。
  
  
• 如何使用C++中的while循环
  C++是一种高效、快速、可靠的编程语言，它的一个非常重要的构造是循环。while循环是C++中用来重复执行某些代码或操作的一个非常有用的结构。
  
  
• C++代码趣味简单易学
  c++是一种很有趣的编程语言，它可以用于创建各种各样的应用程序，包括游戏、桌面应用程序、系统工具等等。与其他编程语言相比，c++代码简单易学，因此适合初学者和资深开发人员。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政