使用求2个字符串最短编辑距离动态规划算法实现 git diff 算法 java 实现

测试类 MyDiffTest.java：
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;public class MyDiffTest {private static String path = "\\xxx\\";private static List<String> lines_v1 = readFile2List( path + "DemoClass1.java" );private static List<String> lines_v2 = readFile2List( path + "DemoClass2.java" );public static void main(String[] args) {/*lines_v1 = new ArrayList<>();lines_v2 = new ArrayList<>();lines_v1.add( "m" );lines_v1.add( "o" );lines_v1.add( "t" );lines_v1.add( "h" );lines_v1.add( "e" );lines_v1.add( "r" );lines_v2.add( "m" );lines_v2.add( "o" );lines_v2.add( "n" );lines_v2.add( "s" );lines_v2.add( "t" );lines_v2.add( "e" );lines_v2.add( "r" );*/int[][] dp =  calculateMinimumTransferWay(lines_v1, lines_v2);int index1 = lines_v1.size() - 1;int index2 = lines_v2.size() - 1;System.out.println( "最短编辑距离：" +  dp[index1][index2] );List<String> result = new ArrayList<>();while ( index1 >= 0 && index2 >= 0 ){String line_v1 = lines_v1.get(index1);String line_v2 = lines_v2.get(index2);if( line_v1.equals( line_v2 ) ){// v1：...a// v2：...a// 此时，v1 和 v2 的当前行相同，原封不懂的输出，表示没有改动result.add( "  " + line_v1 );index1--;index2--;}else {// v1：...a// v2：...b// 此时，v1版本的当前行和 v2版本的当前行不相同，所以v1转化为v2过程中，对 行a、行b的操作有3种可能：新增行b、删除行a// v1：...a// v2： ...  b// 如果此时的编辑距离是最小的，则v2版本需要新增 行bint sed1 = dp[index1][index2 - 1] + 1; // ps：sed 是 shortest edit distance 的缩写// v1： ...  a// v2：...b// 如果此时的编辑距离是最小的，则v2版本需要删除 行aint sed2 = dp[ index1 - 1 ][ index2 ] + 1;// v1： ...  a// v2： ...  b// 如果此时的编辑路基是最小的，则v2版本需要将 删除行a+新增行b( 一共2步操作 )int sed3 = dp[ index1 - 1 ][ index2 - 1 ] + 2;int sed = Math.min(Math.min(sed1, sed2), sed3);if( sed1 == sed ){result.add( "+ " + line_v2 );index2--;}else if( sed2 == sed ){result.add( "- " + line_v1 );index1--;}else if( sed3 == sed ){result.add( "+ " + line_v2 );result.add( "- " + line_v1 );index1--;index2--;}}}while ( index1 >= 0 ){// v1 还剩下的一些 "首行们" 都是需要被删除的行，因为v2版本没有result.add( "- " + lines_v1.get( index1 ) );index1--;}while ( index2 >= 0 ){// v2 还剩下的一些 "首行们" 都是需要被添加的行，因为v1版本没有result.add( "+ " + lines_v2.get( index2 ) );index2--;}for (int i = ( result.size() - 1 ); i >= 0;i-- ) {System.out.println( result.get( i ) );}}private static List<String> readFile2List( String filePath ){BufferedReader reader = null;try {List<String> lines = new ArrayList<>();reader = new BufferedReader(new FileReader(filePath));String line = reader.readLine();while (line != null) {lines.add( line );line = reader.readLine();}return lines;} catch (Exception e) {e.printStackTrace();return null;} finally {if (reader != null) {try {reader.close();} catch (Exception e) {e.printStackTrace();}}}}private static int[][] calculateMinimumTransferWay(List<String> lines_v1, List<String> lines_v2 ){int size_v1 = lines_v1.size();int size_v2 = lines_v2.size();int[][] dp = new int[ size_v1 ][ size_v2 ];for (int index1 = 0; index1 < size_v1; index1++) {String line_v1 = lines_v1.get( index1 );for (int index2 = 0; index2 < size_v2; index2++) {String line_v2 = lines_v2.get( index2 );if( index1 == 0 ){if( index2 == 0 ){if( line_v1.equals( line_v2 ) ){// v1：a// v2：a// 无需任何操作dp[ index1 ][ index2 ] = 0;}else {// 不相同,需要 1 步删除操作，1步插入操作// v1：a// v2：bdp[ index1 ][ index2 ] = 2;}}else {if( getFirstEqualIndex( lines_v2,line_v1,0,index2 ) != -1 ){// v1：      a// v2：...a...// 需要 index2 步插入操作dp[ index1 ][ index2 ] = index2;}else {// v1：      a// v2：...b...// 需要1步删除操作，index2 + 1步插入操作dp[ index1 ][ index2 ] = index2 + 2;}}}else {if( index2 == 0 ){if( getFirstEqualIndex(lines_v1, line_v2, 0, index1) != -1 ){// v1：...a...// v2：      a// 需要 index1 步删除操作dp[ index1 ][ index2 ] = index1;}else {// v1：...a...// v2：      b// 需要 index1 + 1 步删除操作，1步插入操作dp[ index1 ][ index2 ] = index1 + 2;}}else {if( line_v1.equals( line_v2 ) ){// v1：...a// v2：...adp[ index1 ][ index2 ] = dp[index1 - 1][index2 - 1];}else {// v1：...a// v2：...b// sed means "shorest edit distance"int sed1 = dp[index1 - 1][index2];int sed2 = dp[index1 ][index2 - 1];int sed3 = dp[index1 - 1][index2 - 1];int sed = Math.min( Math.min( sed1,sed2 ),sed3 );if( sed1 == sed || sed2 == sed ){dp[ index1 ][ index2 ] = sed + 1;}else {dp[ index1 ][ index2 ] = sed + 2;}}}}}}return dp;}private static int getFirstEqualIndex(List<String> lines, String targetLine, int beginIndex, int endIndex) {for (int i = beginIndex; i <=endIndex ; i++) {if( targetLine.equals( lines.get( i ) ) ){return i;}}return -1;}
}

旧版本文本文件 DemoClass1.java：

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
public class DemoClass1 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();public static String null2emptyWithTrim( String str ){if( str == null ){str = "";}str = str.trim();return str;}public static String requiredStringParamCheck(String param, String paramRemark) {param = null2emptyWithTrim( param );if( param.length() == 0 ){String msg = "操作失败，请求参数 \"" + paramRemark + "\" 为空";log.error( msg );throw new BusinessLogicException( msg );}return param;}public static double calculateSimilarity( String str1,String str2 ){int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());System.out.println("相似度：" + similarity);return similarity;}
}

新版本文本文件 DemoClass2.java：

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
public class DemoClass2 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();public static String null2emptyWithTrim( String str ){// if( str == null ){//     str = "";// }// str = str.trim();return str;}public static String requiredStringParamCheck(String param, String paramRemark) {return null;}public static double calculateSimilarity( String str1,String str2 ){try {int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());return similarity;}catch ( Exception e ){e.printStackTrace();return 0d;}}
}

测试输出：

import com.goldwind.ipark.common.exception.BusinessLogicException;import lombok.extern.slf4j.Slf4j;import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
- public class DemoClass1 {
+ public class DemoClass2 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();
+     private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();
+     private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();public static String null2emptyWithTrim( String str ){
-         if( str == null ){
-             str = "";
-         }
-         str = str.trim();
+         // if( str == null ){
+         //     str = "";
+         // }
+         // str = str.trim();return str;}public static String requiredStringParamCheck(String param, String paramRemark) {
-         param = null2emptyWithTrim( param );
-         if( param.length() == 0 ){
-             String msg = "操作失败，请求参数 \"" + paramRemark + "\" 为空";
-             log.error( msg );
-             throw new BusinessLogicException( msg );
-         }
-         return param;
+         return null;}public static double calculateSimilarity( String str1,String str2 ){
-         int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
-         double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
-         System.out.println("相似度：" + similarity);
-         return similarity;
+         try {
+             int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
+             double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
+             return similarity;
+         }catch ( Exception e ){
+             e.printStackTrace();
+             return 0d;
+         }}}

求做小编辑距离的时候，我这里不允许编辑操作，通常的求最小编辑距离一共允许三种操作( 删除、新增、编辑 )，其中一个编辑操作和删除、新增操作的权重都算作一步，我这里不允许编辑操作，比如迫不得已必须用编辑操作时，例如将a 行变为b行，我们必须先删除，后增加，其实等效于允许编辑操作，但是编辑操作权重大一些，为什么这样规定呢？

如上所示，新版本相对于旧版本来说是连续的修改了多行，我们人眼比较习惯这种差异比较后的输出：

而不是这种输出( 虽然逻辑上也对 )：

如果允许编辑操作( 或者编辑操作的权重和删除、新增操作一样时 )，就可能会出现这种情况，整块整块的修改给当做每一行来一个编辑操作。如果不允许编辑操作( 其实等价于将编辑操作的权重设置为删除或者插入操作的2倍 )，那么当出现整块的修改时，差异化比较时，被当做多个单行的修改的概率就被降低了，因为那样的话编辑次数会更多，所以会优先的视为多行的删除( 块删除 )操作和多行的新增( 块新增 )。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/211112.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【PUSDN】SpringBoot的jar进行解压后，替换其中的文件重新生成新的jar-SW

【PUSDN】SpringBoot的jar进行解压后，替换其中的文件重新生成新的jar-SW

当你解压Spring Boot的JAR文件时&#xff0c;实际上是在打开一个压缩文件&#xff0c;类似于ZIP。你可以按照以下步骤进行替换文件并重新生成新的JAR&#xff1a; 解压原始的JAR文件&#xff1a; 使用任何ZIP工具&#xff08;如WinRAR、7-Zip或命令行工具&#xff09;&#xf…
阅读更多...
[论文精读]序列建模使大视觉模型的规模化学习成为可能

[论文精读]序列建模使大视觉模型的规模化学习成为可能

本博客是一篇最新论文的精读&#xff0c;论文为UC伯克利大学及约翰霍普金斯大学相关研究者新近(2023.12.1)在arxiv上上传的《Sequential Modeling Enables Scalable Learning for Large Vision Models》 。知名科技新媒体“新智元”给与本文极高评价&#xff0c;并以《计算机视…
阅读更多...
Linux(统信UOS) 发布.Net Core，并开启Https，绑定证书

Linux(统信UOS) 发布.Net Core，并开启Https，绑定证书

实际开发中&#xff0c;有时会需要为小程序或者需要使用https的应用提供API接口服务&#xff0c;这就需要为.Net Core 配置https&#xff0c;配置起来很简单&#xff0c;只需要在配置文件appsettings.json中添加下面的内容即可 "Kestrel": {"Endpoints": …
阅读更多...
一文带你了解云计算的未来发展趋势与优势

一文带你了解云计算的未来发展趋势与优势

试问现在IT圈还有什么技术比较火&#xff1f;云在数字世界中扮演一个非常重要的角色&#xff0c;目前云计算还不算技术“红海”&#xff0c;它正处于高速发展前期的技术领域&#xff0c;现在早早转型过去&#xff0c;可能还能赶上一波技术红利&#xff0c;连目前大火的ChatGPT …
阅读更多...
STM32-新建工程（标准库）

STM32-新建工程（标准库）

目录 STM32F10x新建工程&#xff08;标准库&#xff09; 移植文件夹 新建工程 添加启动文件和必需文件 在工程中加载新添加的文件 在工程中添加文件路径 在工程中添加main函数 添加lib库 添加必需文件 添加宏定义 点亮LED&#xff08;标准库&#xff09; STM32F10x新…
阅读更多...
力扣题:字符的统计-12.4

力扣题:字符的统计-12.4

力扣题-12.4 [力扣刷题攻略] Re&#xff1a;从零开始的力扣刷题生活 力扣题1&#xff1a;657. 机器人能否返回原点 解题思想&#xff1a;进行统计即可 class Solution(object):def judgeCircle(self, moves):""":type moves: str:rtype: bool""&qu…
阅读更多...
安装获取mongodb

安装获取mongodb

目录 本地安装 获取云上资源 获取Atlas免费数据库 本地连接数据库 在Atlas中连接数据库 本文适合初学者或mongodb感兴趣的同学来准备学习测试环境&#xff0c;或本地临时开发环境。mongodb是一个对用户非常友好的数据库。这种友好&#xff0c;不仅仅体现在灵活的数据结构和…
阅读更多...
pre标签展示代码块

pre标签展示代码块

pre样式 添加背景色、边框、以及调整了字体大小。 pre { border: 1px solid #999; page-break-inside: avoid; display: block; padding: 3px 3px 2px; margin: 0 0 10px; font-size: 13px; line-height: 20px; word-break: break-all; word-wrap: break-word; /* white-space:…
阅读更多...
​HTML代码混淆技术：原理、应用和实现方法详解

​HTML代码混淆技术：原理、应用和实现方法详解

​HTML代码混淆技术&#xff1a;原理、应用和实现方法详解 HTML代码混淆是一种常用的反爬虫技术&#xff0c;它可以有效地防止爬虫对网站数据的抓取。本文将详细介绍HTML代码混淆技术的原理、应用以及实现方法&#xff0c;帮助大家更好地了解和运用这一技术。 一、HTML代码混淆…
阅读更多...
HarmonyOS学习--初次下载安装和配置环境

HarmonyOS学习--初次下载安装和配置环境

一、Windows下载与安装软件 运行环境要求&#xff1a; 为保证DevEco Studio正常运行&#xff0c;建议电脑配置满足如下要求&#xff1a; 操作系统&#xff1a;Windows10 64位、Windows11 64位内存&#xff1a;8GB及以上硬盘&#xff1a;100GB及以上分辨率&#xff1a;1280*80…
阅读更多...
springBoot3.2 + jdk21 + GraalVM上手体验

springBoot3.2 + jdk21 + GraalVM上手体验

springBoot3.2 jdk21 GraalVM上手体验 SpringBoot2.x官方已经停止维护了&#xff0c;jdk8这次真的得换了&#x1f923; 可以参考官方文章进行体验&#xff1a;https://spring.io/blog/2023/09/09/all-together-now-spring-boot-3-2-graalvm-native-images-java-21-and-virt…
阅读更多...
行云海CMS SQL注入漏洞复现

行云海CMS SQL注入漏洞复现

0x01 产品简介 行云海cms是完全开源的一套CMS内容管理系统,简洁,易用,安全,稳定,免费。 0x02 漏洞概述 行云海cms中ThinkPHP在处理order by排序时可利用key构造SQL语句进行注入，LtController.class.php中发现传入了orderby未进行过滤导致sql注入。攻击者除了可以利用 SQL 注入…
阅读更多...
Web开发-问题-前后端交互数据不一致

Web开发-问题-前后端交互数据不一致

0x01 问题描述 所用的技术&#xff1a;VueSpring Boot后端传给前端数据&#xff1a; [Student(studentId1, personorg.fatmansoft.teach.models.Person4abe6020, major软件工程, className一班, grade一年级), Student(studentId2, personorg.fatmansoft.teach.models.Person…
阅读更多...
产品学习之路（一）

产品学习之路（一）

在做好开发的同时&#xff0c;还需要熟悉产品业务逻辑&#xff0c;不能为了功能而做功能&#xff0c;要从产品经理的角度去看待每个需求和客户痛点所在&#xff0c;这样针对产品设计出来的东西自己也有发言权&#xff1b; 目前作为一名前端开发人员&#xff0c;也在自学产品知识…
阅读更多...
mysql原理--InnoDB记录结构

mysql原理--InnoDB记录结构

1.InnoDB行格式 我们平时是以记录为单位来向表中插入数据的&#xff0c;这些记录在磁盘上的存放方式也被称为 行格式 或者 记录格式 。 设计 InnoDB 存储引擎的大叔们到现在为止设计了4种不同类型的 行格式 &#xff0c;分别是 Compact 、 Redundant 、Dynamic 和 Compressed 行…
阅读更多...
多线程--11--ConcurrentHashMap

多线程--11--ConcurrentHashMap

ConcurrentHashMap与HashMap等的区别 HashMap线程不安全 我们知道HashMap是线程不安全的&#xff0c;在多线程环境下&#xff0c;使用Hashmap进行put操作会引起死循环&#xff0c;导致CPU利用率接近100%&#xff0c;所以在并发情况下不能使用HashMap。 ConcurrentHashMap 主…
阅读更多...
arcgis图上添加发光效果！

arcgis图上添加发光效果！

看完本文， 你可以不借助外部图片素材， 让你的图纸符号表达出你想要的光！ 我们以之前的某个项目图纸为例，来介绍下让符号发光的技术！ 第一步—底图整理 准备好栅格影像底图、行政边界的矢量数据，确保“数据合适、位置正确、边界吻合”。 确定好图纸的大小、出图比例、投…
阅读更多...
基于SpringBoot的仓库管理系统设计与实现附带源码和论文

基于SpringBoot的仓库管理系统设计与实现附带源码和论文

博主24h在线&#xff0c;想要源码文档部署视频直接私聊&#xff0c;全网最低价&#xff0c;9.9拿走&#xff01; 【关键词】仓库管理系统&#xff0c;jsp编程技术&#xff0c;mysql数据库&#xff0c;SSM&#xff0c;Springboot 目 录 摘 要 Abstract 第1章 绪论 1.1 课题…
阅读更多...
springboot整合swagger

springboot整合swagger

1&#xff09;简介&#xff1a; 作为后端开放人员&#xff0c;最烦的事就是自己写接口文档和别人没有写接口文档&#xff0c;不管是前端还是后端开发&#xff0c;多多少少都会被接口文档所折磨&#xff0c;前端会抱怨后端没有及时更新接口文档&#xff0c;而后端又会觉得编写接…
阅读更多...
windows下DSS界面本地集成linkis管理台

windows下DSS界面本地集成linkis管理台

说明&#xff1a;当前开发环境为windows&#xff0c;node版本使用16.15.1。启动web时&#xff0c;确保后端服务已准备就绪。 1.linkis web编译 #进入项目WEB根目录 $ cd linkis/linkis-web #安装项目所需依赖 $ npm install参考官方编译说明&#xff0c;windows下编译一直异常…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023