使用求2个字符串最长公共子序列的方法来实现 git diff 算法 java 实现
测试类 GitDiffTest2.java：
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class GitDiffTest2 {
private static String folder = "\\xxx\\";
private static List<String> lines_v1 = loadTxtFile2List(folder + "DemoClass1.java" );
private static List<String> lines_v2 = loadTxtFile2List(folder + "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 size_v1 = lines_v1.size();
int size_v2 = lines_v2.size();
int[][] dp = new int[size_v1][size_v2];
for (int index_v1 = 0; index_v1 < size_v1; index_v1++) {
for (int index_v2 = 0; index_v2 < size_v2; index_v2++) {
String line_v1 = lines_v1.get(index_v1);
String line_v2 = lines_v2.get(index_v2);
if ( line_v1.equals( line_v2 ) ) {
if( index_v1 == 0 || index_v2 == 0 ){
// v1：...a
// v2： a
dp[index_v1][index_v2] = 1;
}else {
// v1：...a
// v2：...a
dp[index_v1][index_v2] = dp[index_v1 - 1][index_v2 - 1] + 1;
}
} else {
if( index_v1==0 || index_v2==0 ){
// v1：...a
// v2： b
dp[index_v1][index_v2] = 0;
}else {
// v1：...a
// v2：...b
// v1： ... a
// v2：...b 此时，v1 的 a 前面的部分 "..." 和 v2 的 "...b" 来求最长公共子串长度
int lcs1 = dp[index_v1 - 1][index_v2];
// v1：...a
// v2： ... b 此时，v2 的 b 前面的部分 "..." 和 v1 的 "...a" 来求最长公共子串长度
int lcs2 = dp[index_v1][index_v2 - 1];
dp[index_v1][index_v2] = Math.max( lcs1,lcs2 );
}
}
}
}
List<String> result = new ArrayList<>();
int index_v1 = lines_v1.size() - 1;
int index_v2 = lines_v2.size() - 1;
while (index_v1 >= 0 && index_v2 >= 0) {
String line_v1 = lines_v1.get(index_v1);
String line_v2 = lines_v2.get(index_v2);
if ( line_v1.equals( line_v2 ) ) {
// v1：..... a
// v2： ... a
// 原封不动的输出行 a，因为 新旧版本文本中都有 a 行
result.add( " " + line_v1 );
index_v1--;
index_v2--;
}else {
// v1：..... a
// v2： ... b
// v1： ..... a
// v2： ... b 如果 lcs1 更长，则最长公共子串中不包含 行a,意味着 v2版本中需要删除v1版本中的行a
int lcs1 = dp[index_v1 - 1][index_v2];
// v1：..... a
// v2： ... b 如果 lcs2更长，则最长公共子串中不包含行b，意味着v2版本中需要新增 行b
int lcs2 = dp[index_v1][index_v2-1];
if ( lcs1 > lcs2 ) {
result.add( "- " + line_v1 );
index_v1--;
} else {
result.add( "+ " + line_v2 );
index_v2--;
}
}
}
while (index_v2 >= 0) {
result.add("+ " + lines_v2.get(index_v2));
index_v2--;
}
while (index_v1 >= 0) {
result.add("- " + lines_v1.get(index_v1));
index_v1--;
}
for (int k = result.size() - 1; k >= 0; k--) {
System.out.println(result.get(k));
}
}
private static List<String> loadTxtFile2List(String filePath) {
BufferedReader reader = null;
List<String> lines = new ArrayList<>();
try {
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();
}
}
}
}
}旧版本文本样例文件 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 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;
+ }
}
}