当前位置: 首页 > news >正文

相似度计算方法-编辑距离 (Edit Distance)

定义

        编辑距离(Edit Distance),也称为Levenshtein距离,是一种衡量两个字符串相似度的方法。它定义为从一个字符串转换为另一个字符串所需的最少单字符编辑操作次数,这些操作包括插入、删除或替换一个字符。

计算方法

        对于两个字符串 S_1 = (s_{11}, s_{12}, \ldots, s_{1m})S_2 = (s_{21}, s_{22}, \ldots, s_{2n}),编辑距离 d_E(S_1, S_2) 可以通过动态规划的方式计算,其中mn分别是S_1S_2的长度。

        定义一个 (m+1) \times (n+1)的矩阵 D,其中 D[i][j] 表示 S_1 的前 i  个字符到 S_2 的前 j 个字符的编辑距离。

初始化矩阵的第一行和第一列为:

D[i][0] = i \quad \text{for } 0 \leq i \leq m
D[0][j] = j \quad \text{for } 0 \leq j \leq n

动态规划的状态转移方程为:

D[i][j] = \min \left( \begin{array}{c} D[i-1][j] + 1 \\ D[i][j-1] + 1 \\ D[i-1][j-1] + 1_{s_{1i} \neq s_{2j}} \end{array} \right)

其中 1_{s_{1i} \neq s_{2j}} 是指示函数,当  s_{1i} \neq s_{2j} 时返回 1,否则返回 0。

最终的编辑距离为:

d_E(S_1, S_2) = D[m][n]

逻辑解析

        编辑距离可以通过动态规划方法来求解。动态规划的核心是构建一个二维表来存储中间结果,并使用这些中间结果来解决更大的子问题。在这个问题中,我们构建一个矩阵 dp,其中 dp[i][j] 表示字符串S_1 的前 i 个字符到字符串 S_2 的前 j 个字符的编辑距离

        初始化

        初始化矩阵的第一行和第一列,因为要从空字符串转换到任意长度的字符串,只需要相应的插入或删除操作次数。因此,dp[i][0] = i 和 dp[0][j] = j

        动态规划方程

        对于每个 dp[i][j] 的值,我们可以考虑以下情况来决定其值:

  1. 如果 s1[i-1] == s2[j-1],则不需要做任何操作,所以 dp[i][j] = dp[i-1][j-1]
  2. 如果 s1[i-1] != s2[j-1],则可以考虑以下三种操作:
    • 替换:将 s1[i-1] 替换成 s2[j-1],那么 dp[i][j] = dp[i-1][j-1] + 1
    • 删除:从 s1 中删除一个字符,那么 dp[i][j] = dp[i-1][j] + 1
    • 插入:在 s1 中插入一个字符,那么 dp[i][j] = dp[i][j-1] + 1
  3. 如果进入到步骤2,我们肯定选择替换、删除、插入距离最小的一项,即对应上述计算方法中的状态转移方程。
  4. 等迭代计算完成后,最终的答案就是 dp[m][n],其中 mn 分别是字符串 S_1S_2 的长度。

        删除逻辑解析

        对于替换操作来说,理解起来很简单,S_1的前 i-1个字符到S_2的前j-1个字符的编辑距离是dp[i-1][j-1],再加一次替换操作,即是最后的 dp[i][j] = dp[i-1][j-1] + 1。

        当我们考虑从 S_1中删除一个字符时,我们实际上是在比较 S_1 的前 i-1 个字符与 S_2 的前 j 个字符的编辑距离。这意味着我们从 S_1中删除了第 i 个字符。

        在动态规划表 dp 中,dp[i][j] 表示字符串 S_1的前 i 个字符到字符串 S_2 的前 j 个字符的编辑距离。如果我们想从 S_1 中删除一个字符,那么可以这样理解:

  • 我们从 s1 的前 i-1 个字符到 s2 的前 j 个字符的编辑距离 dp[i-1][j] 开始。
  • 然后加上一次删除操作的成本,即 + 1

因此,动态规划方程中的删除操作可以表示为: dp[i][j]=dp[i-1][j]+1

  1. 状态转移

    • dp[i-1][j] 表示从 S_1 的前 i-1 个字符到 S_2 的前 j 个字符的编辑距离。
    • dp[i][j] 表示从 S_1的前 i 个字符到 S_2 的前 j 个字符的编辑距离。
  2. 删除操作

    • 如果我们从 S_1 中删除第 i 个字符,那么 S_1 的前 i 个字符到 S_2 的前 j 个字符的编辑距离就变成了 S_1 的前 i-1 个字符到 S_2 的前 j 个字符的编辑距离加上一次删除操作的成本。
    • 因此,dp[i][j] = dp[i-1][j] + 1

        删除示例

假设我们有两个字符串 s1 = "kitten"s2 = "sitting",我们来计算 dp[1][1] 的值,即从 s1 的前 1 个字符到 s2 的前 1 个字符的编辑距离。

  1. 初始化

    • s1 的前 1 个字符是 "k"
    • s2 的前 1 个字符是 "s"
  2. 删除操作

    • 如果我们从 s1 中删除 "k",那么 dp[1][1] 应该等于 dp[0][1] + 1
    • dp[0][1] 是从空字符串到 "s" 的编辑距离,即 1。
    • 因此,dp[1][1] = 1 + 1 = 2

        插入逻辑解析

        插入操作意味着在字符串 S_1 中插入一个字符以使其更接近字符串 S_2。当我们考虑在 S_1 中插入一个字符时,我们实际上是在比较 S_1 的前 i 个字符与 S_2 的前 j-1 个字符的编辑距离。这意味着我们在 S_1 的末尾插入了 S_2 的第 j 个字符。

        在动态规划表 dp 中,dp[i][j] 表示字符串 S_1 的前 i 个字符到字符串 S_2 的前 j 个字符的编辑距离。如果我们想在 S_1 中插入一个字符,那么可以这样理解:

  • 我们从 S_1  的前 i 个字符到 S_2  的前 j-1 个字符的编辑距离 dp[i][j-1] 开始。
  • 然后加上一次插入操作的成本,即 + 1

        因此,动态规划方程中的插入操作可以表示为: dp[i][j]=dp[i][j-1]+1

  1. 状态转移

    • dp[i][j-1] 表示从 S_1 的前 i 个字符到 S_2的前 j-1 个字符的编辑距离。
    • dp[i][j] 表示从 S_1 的前 i 个字符到 S_2的前 j 个字符的编辑距离。
  2. 插入操作

    • 如果我们在 S_1 的末尾插入 S_2  的第 j 个字符,那么 S_1  的前 i 个字符到 S_2 的前 j 个字符的编辑距离就变成了 S_1 的前 i 个字符到 S_2  的前 j-1 个字符的编辑距离加上一次插入操作的成本。
    • 因此,dp[i][j] = dp[i][j-1] + 1

        插入示例

        假设我们有两个字符串 s1 = "kitten"s2 = "sitting",我们来计算 dp[1][2] 的值,即从 s1 的前 1 个字符到 s2 的前 2 个字符的编辑距离。

  1. 初始化

    • s1 的前 1 个字符是 "k"
    • s2 的前 2 个字符是 "si"
  2. 插入操作

    • 如果我们在 s1 的末尾插入 "s",那么 dp[1][2] 应该等于 dp[1][1] + 1
    • dp[1][1] 是从 "k" 到 "s" 的编辑距离,假设已经计算过为 1。
    • 因此,dp[1][2] = 1 + 1 = 2

代码实现

public class EditDistance {public static void main(String[] args) {String str1 = "kitten";String str2 = "sitting";int distance = calculateEditDistance(str1, str2);System.out.printf("The edit distance between '%s' and '%s' is: %d\n", str1, str2, distance);}/*** 计算两个字符串之间的编辑距离。** @param s1 第一个字符串* @param s2 第二个字符串* @return 两个字符串之间的编辑距离*/public static int calculateEditDistance(String s1, String s2) {int[][] dp = new int[s1.length() + 1][s2.length() + 1];// 初始化第一行和第一列for (int i = 0; i <= s1.length(); i++) {dp[i][0] = i;}for (int j = 0; j <= s2.length(); j++) {dp[0][j] = j;}// 动态规划填充dp数组for (int i = 1; i <= s1.length(); i++) {for (int j = 1; j <= s2.length(); j++) {int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1,      // 删除dp[i][j - 1] + 1),     // 插入dp[i - 1][j - 1] + cost);    // 替换}}return dp[s1.length()][s2.length()];}
}

注意,从代码中可以看出,编辑距离的时间复杂度和空间复杂度都是O(m \times n)

优劣势

优势

  1. 全面考虑编辑操作

    • 编辑距离考虑了三种基本的编辑操作:插入、删除和替换,能够全面地评估字符串之间的差异。
  2. 计算稳定性

    • 编辑距离的计算基于动态规划方法,保证了计算结果的一致性和准确性。

编辑距离的劣势

  1. 时间复杂度

    • 编辑距离的计算复杂度为 O(m\times n),其中 m 和 n 分别是两个字符串的长度。
    • 对于较长的字符串,计算时间可能会较长,编辑距离的计算可能会消耗大量的时间和计算资源。
  2. 不考虑编辑操作的成本

    • 编辑距离默认每种编辑操作的成本相同,但实际上不同类型的编辑操作可能有不同的成本。
    • 例如,在某些应用场景中,替换操作可能比插入或删除操作成本更高。
  3. 不适用于非字符串数据

    • 编辑距离主要用于字符串数据,对于非字符串数据(如数值型数据或图像数据)可能不适用。
  4. 空间复杂度

    • 动态规划方法需要存储一个 (m+1)\times (n+1)的矩阵,这在处理长字符串时可能导致较高的空间复杂度。

应用场景

  1. 拼写检查

    1. 在拼写检查和自动纠错中,编辑距离可用于自动纠正拼写错误,通过查找编辑距离最小的正确单词来纠正输入的单词。

  2. 自然语言处理

    • 在语音识别中,用于比较语音转写的文本与目标文本之间的相似度。
    • 在机器翻译中,用于评估翻译质量或生成候选翻译。
  3. 生物信息学

    • 在DNA或蛋白质序列比对中,用于比较序列之间的相似性。
    • 在基因组学中,用于识别相似的基因序列。
  4. 数据挖掘

    • 在相似文档或网页的检测中,用于比较文本内容的相似度。
    • 在推荐系统中,用于比较用户的兴趣或行为模式。
  5. 软件工程

    • 在版本控制中,用于比较文件版本之间的差异。
    • 在代码审查工具中,用于识别代码片段之间的相似性。

相关文章:

相似度计算方法-编辑距离 (Edit Distance)

定义 编辑距离&#xff08;Edit Distance&#xff09;&#xff0c;也称为Levenshtein距离&#xff0c;是一种衡量两个字符串相似度的方法。它定义为从一个字符串转换为另一个字符串所需的最少单字符编辑操作次数&#xff0c;这些操作包括插入、删除或替换一个字符。 计算方法 …...

初识FPGA

大学的时候有一门verilog语言&#xff0c;觉得很难&#xff0c;不愿学。有学习套件是黑金的一块FPGA开发板&#xff0c;可能当时点灯和点数码管了。全都忘了。 今项目需要&#xff0c;使用FPGA中的ZYNQ&#xff0c;需要c语言开发&#xff0c;随即开始学习相关知识。 ZYNQ内部…...

探索 JavaScript:从入门到精通

目录 1. JavaScript 的介绍与基础 示例&#xff1a;弹出欢迎信息 JavaScript&#xff0c;作为网络时代最流行的脚本语言之一&#xff0c;赋予了网页生动活泼的动态功能。无论是新手还是经验丰富的开发者&#xff0c;掌握 JavaScript 的核心概念和技能都是开启网络编程之门的钥…...

这4款视频压缩软件堪称是压缩界的神器!

视频在我们的日常设备当中会占用相对较多的空间&#xff0c;尤其是喜欢用视频记录的朋友。但是过多过大的视频不仅会给我们的设备带来了压力&#xff0c;也不利于分享和管理。今天我就要给大家分享几个视频压缩的小妙招。 1、福昕压缩 直通车&#xff1a;www.foxitsoftware.cn…...

【ARM 芯片 安全与攻击 5.6 -- 侧信道与隐蔽信道的区别】

文章目录 侧信道与隐蔽信道的区别侧信道攻击(Side-channel Attack)侧信道攻击简介侧信道攻击 使用方法侧信道攻击示例隐蔽信道(Covert Channel)隐蔽信道简介隐蔽信道使用方法隐蔽信道代码示例侧信道与隐蔽信道在芯片及系统安全方面的使用侧信道的应用隐蔽信道的应用Summary…...

C#:Bitmap类使用方法—第4讲

大家好&#xff0c;今天接着上一篇文章继续讲。 下面是今天的方法&#xff1a; &#xff08;1&#xff09;Bitmap.MakeTransparent 方法&#xff1a;使此 Bitmap的默认透明颜色透明。 private void MakeTransparent_Example1(PaintEventArgs e) { // Create a Bitmap object…...

Vue是如何实现nextTick的?

你好同学&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏和关注。个人知乎 Vue.js 的 nextTick 函数是一个非常重要的功能&#xff0c;它用于延迟执行代码块到下次 DOM 更新循环之后。这在 Vue.js 的异步更新队列机制中非常有用&#xff0c;尤其是在你需要基于更新后的 DOM 来…...

rabbitmq镜像集群搭建

用到的ip地址 ip地址端口192.168.101.65&#xff08;主&#xff09;15672192.168.101.7515672192.168.101.8515672 安装erlang和rabbitmq 安装 安装三个包 yum install esl-erlang_23.0-1_centos_7_amd64.rpm -y yum install esl-erlang-compat-18.1-1.noarch.rpm -y rpm -…...

《c++并发编程实战》 笔记

《c并发编程实战》 笔记 1、你好&#xff0c;C的并发世界为什么要使用并发 第2章 线程管理2.1.1 启动线程2.2 向线程函数传递参数2.5 识别线程 第3章 线程间共享数据3.2.1 C中使用互斥量避免死锁的进阶指导保护共享数据的替代设施 第4章 同步并发操作4.1 等待一个事件或其他条件…...

57qi5rW35LqRZUhS pc.mob SQL注入漏洞复现

0x01 产品简介 57qi5rW35LqRZUhS是大中型企业广泛采用人力资源管理系统。某云是国内顶尖的HR软件供应商,是新一代eHR系统的领导者。 0x02 漏洞概述 57qi5rW35LqRZUhS pc.mob 接口存在SQL注入漏洞,未经身份验证的远程攻击者除了可以利用 SQL 注入漏洞获取数据库中的信息(例…...

微信小程序--27(自定义组件4)

一、父子组件之间通信的3种方式 1、属性绑定 用于父组件向子组件的只当属性设置数据&#xff0c;但只能设置JSON兼容的数据 2、事件绑定 用于子组件向父组件传递数据&#xff0c;可以传递任意数据 3、获取组件实例 父组件还可以通过this.select Component()获取子组件的实…...

Linux | Linux进程万字全解:内核原理、进程状态转换、优先级调度策略与环境变量

目录 1、从计算机组成原理到冯诺依曼架构 计算机系统的组成 冯诺依曼体系 思考&#xff1a;为什么计算机不能直接设计为 输入设备-CPU运算-输出设备 的结构&#xff1f; 2、操作系统(Operator System) 概念 设计OS的目的 描述和组织被管理对象 3、进程 基本概念 进程id和父进程…...

VBA技术资料MF184:图片导入Word添加说明文字设置格式

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…...

在函数设计中应用单一职责原则:函数分解与职责分离

在函数设计中应用单一职责原则&#xff1a;函数分解与职责分离 引言 单一职责原则&#xff08;Single Responsibility Principle, SRP&#xff09;是面向对象设计原则中的核心原则之一&#xff0c;强调一个类或函数应该只有一个责任或理由去改变。在函数设计中&#xff0c;应…...

多线程锁机制面试

目录 乐观锁的底层原理 ReentrantLock的实现原理 读写锁 ReentrantReadWriteLock synchronized 底层原理 Lock和synchronized的区别 乐观锁的底层原理 版本号机制 在数据库表中添加一个版本号字段&#xff08;如 version&#xff09;&#xff0c;每次更新数据时都会将版本号…...

《SQL 中计算地理坐标两点间距离的魔法》

在当今数字化的世界中&#xff0c;地理数据的处理和分析变得越来越重要。当我们面对一个包含地理坐标数据的表时&#xff0c;经常会遇到需要计算两点之间距离的需求。无论是在物流配送路线规划、地理信息系统应用&#xff0c;还是在基于位置的服务开发中&#xff0c;准确计算两…...

微服务可用性设计

一、隔离 对系统或资源进行分割&#xff0c;实现当系统发生故障时能限定传播范围和影响范围。进一步的&#xff0c;通过隔离能够降低系统之间得耦合度&#xff0c;使得系统更容易维护和扩展。某些业务场景下合理使用隔离技巧也能提高整个业务的性能。我理解隔离本质就是一种解…...

【扒代码】dave readme文档翻译

jerpelhan/DAVE (github.com) 摘要 低样本计数器估算选定类别对象的数量&#xff0c;即使在图像中只有少量或没有标注样本的情况下。目前最先进的技术通过对象位置密度图的总和来估算总数量&#xff0c;但这种方法无法提供单个对象的位置和大小&#xff0c;这对于许多应用来说…...

c语言---文件

这一节我准备分三个部分来带领大家了解文件 ——一、有关文件的基础知识 ————二、文件的简单操作 ————————三、文件结束的判定 ————————————四、文件缓冲区 一、文件的基础知识&#xff1a; 首先在了解文件之前&#xff0c;我们需要了解C/C程序内存…...

Windows系统下Go安装与使用

step1&#xff1a; 下载go语言SDK 下载地址&#xff1a;https://go.dev/dl/ 下载后选择合适位置安装即可&#xff0c;我选择D盘 在安装完成后&#xff0c;可以通过go env 命令检测是否安装成功。在“命令提示符”界面输入“go env”命令&#xff0c;如果显示如下类似结果则说明…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...