使用求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版本需要新增 行b
int sed1 = dp[index1][index2 - 1] + 1; // ps：sed 是 shortest edit distance 的缩写
// v1： ... a
// v2：...b
// 如果此时的编辑距离是最小的，则v2版本需要删除 行a
int 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：b
dp[ 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：...a
dp[ 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倍 )，那么当出现整块的修改时，差异化比较时，被当做多个单行的修改的概率就被降低了，因为那样的话编辑次数会更多，所以会优先的视为多行的删除( 块删除 )操作和多行的新增( 块新增 )。