这是 git diff 后的效果，感觉挺简单的，不就是 比较新旧版本，新增了就用 "+" 显示新加一行，删除了就用 "-" 显示删除一行，修改了一行就用 "-"、"+" 显示将旧版本中的该行干掉了并且新版本中增加了一行，即使用 "删除" + "新增" 操作代替 "修改" 操作。
然后我写的测试代码如下：
import org.apache.commons.text.similarity.LevenshteinDistance;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class MyDiffTest {
public static void main(String[] args) {
List<String> lines_old = loadTxtFile2List("\\xxx\\DemoClass1.java" );
List<String> lines_new = loadTxtFile2List("\\xxx\\DemoClass2.java");
// lines1的起始行和 lines2 的起始行做映射
// 扫描旧版本中的每一行
int size = lines_old.size();
for( int i=0;i<size;i++ ){
// 从新版本中找该行
String line_old = lines_old.get(i);
String line_new = lines_new.get(i);
// 如果发现版本中中该行的数据变了，那么提示删除了旧的行，添加了新的行
if( line_new.equals( line_old ) ){
System.out.println( line_old );
}else {
System.out.println( "- " + line_old );
System.out.println( "+ " + line_new );
}
}
// xxxx xxxx1 -xxxx
// yyyy yyyy +xxxx1
// xxxxxx xxxxxx xxxxxx
// zzzz zzzz zzzz
}
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) {
// System.out.println(line);
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();
}
}
}
}
}
其中用到的2个新旧版本的文本如下：
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) {
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 相较于 DemoClass1.java 的区别是 "public class" 后面的类名不同，"private static final LevenshteinDistance LEVENSHTEIN_DISTANC..." 多复制了2行并改了名称，然后运行后显示差别如下：
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();
- public static String null2emptyWithTrim( String str ){
+ private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();
- if( str == null ){
+
- str = "";
+ public static String null2emptyWithTrim( String str ){
- }
+ if( str == null ){
- str = str.trim();
+ str = "";
- return str;
+ }
- }
+ str = str.trim();
-
+ return str;
- public static String requiredStringParamCheck(String param, String paramRemark) {
+ }
- param = null2emptyWithTrim( param );
+
- if( param.length() == 0 ){
+ public static String requiredStringParamCheck(String param, String paramRemark) {
- String msg = "操作失败，请求参数 \"" + paramRemark + "\" 为空";
+ param = null2emptyWithTrim( param );
- log.error( msg );
+ if( param.length() == 0 ){
- throw new BusinessLogicException( msg );
+ String msg = "操作失败，请求参数 \"" + paramRemark + "\" 为空";
- }
+ log.error( msg );
- return param;
+ 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());
+ public static double calculateSimilarity( String str1,String str2 ){
- System.out.println("相似度：" + similarity);
+ int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
- return similarity;
+ double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
- }
+ System.out.println("相似度：" + similarity);
- }
+ return similarity;
为啥？？？
如上两张图片，旧版本的第10行和新版本的第10行对应，从直观上看新版本的第11、12行是在旧版本的第10行和第11行之间插进去的，但是程序并不这么认为，它会认为将旧版本的第11行的空白行修改为了新版本的 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();” 为什么我们人眼会这么直观的感觉到 新版本的 第11、12行时插进去的，因为我们比较了新旧版本的第7、8、9、10行都差不多，旧版本的1127行和新版本的 1329行都差不多，所以自然而然的认为新版本的11、12行是直接插进去的，那么现在我们就来算法实现吧！（ ps：前文中的 “差不多” 是差几多？是完全equals 还是很像？”其实这里可以设置一个阈值，使用求字符串的相似度算法求出相似度，网上有现成的类库求相似度，自己也可以使用动态规划写一个简单的字符串相似度算法 ）
感觉恰当的算法的执行过程应该是这样的：
新旧版本各维持一个行号游标：index_old、index_new，最开始这两个游标相同，越往后可能不同，但是他们表示的行的内容应该是应该相似的，因为新版本的修改会导致内容越来越 “错位”。假设我们从上面2张图片的第7行开始描：
1. 最开始 index_old = index_new = 7，算法检测到新旧版本的第7行的内容相同( 后面我们就尽量用伪代码表示，就不说这么多啰里啰嗦的话了 )，即 lines_old[ 7] = lines_new[ 7]。
2. index_old++，index_new++，都变为8，算法检测到 lines_old[ 8 ] != lines_new[ index_new ]，并且他们的相似度很高，所以算法判断新版本的第8行相较于旧版本的第8行是做了修改操作。
3. index_old++，index_new++，都变为9，算法检测到 lines_old[ 9 ] = lines_new[ 9 ]。
4. index_old++，index_new++，都变为10，算法检测到 lines_old[ 10 ] = lines_new[ 10 ]。
5. index_old++，index_new++，都变为11，算法检测到 lines_old[ 11 ] != lines_new[ 11 ]，并且这两行的文本内容及不相似，所以判断新版本是在旧版本的第11行插入了一行 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 =LevenshteinDistance.getDefaultInstance();”，所以此时旧版本的第11行就和新版本的第11行对应不上了，而是和新版本的第12行做对应。
6. index_old 不变，index_new++，index_old 还是11，index_new 变为 12，即旧版本的第11行要和新版本的第12行做对应，就像找老婆一样，旧7和新7结为了夫妻，旧8和新8结为了夫妻( 虽然有一点点的裂痕，但不打紧 )，新9和新9结为了夫妻，...，所以旧11也要在新版本中找到一个新x作为自己的伴侣，本来已经找到了一个新11，但是发现新11和自己三观差别很大，根本合不来，所以pass掉，继续找，现在发现了下一个相亲对象 新12，发现lines_old[ 11 ] 和 lines_new[ 12 ] 相似度还是差别很大，所以算法判断新版本又插入了一个新行 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();”。
7. index_old 不变，index_new++，index_old 还是11，index_new 变为 13，因为 lines_old[ 11 ] = lines_new[ 13 ],所以 旧11 很幸运的找到了自己的伴侣 新13,。
8. index_old++，index_new++，index_old变为12，index_new变为14，因为 lines_old[ 12 ] = lines_new[ 14 ],所以此步未检测到变化。
...
改进后的测试代码如下：
import org.apache.commons.text.similarity.LevenshteinDistance;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class MyDiffTest {
public static void main(String[] args) {
List<String> lines_old = loadTxtFile2List("\\xxx\\DemoClass1.java" );
List<String> lines_new = loadTxtFile2List("\\xxx\\DemoClass2.java");
// lines1的起始行和 lines2 的起始行做映射
// 扫描旧版本中的每一行
// xxxx xxxx1 -xxxx
// yyyy yyyy +xxxx1
// xxxxxx xxxxxx xxxxxx
// zzzz zzzz zzzz
int index_old = 0;
int index_new = 0;
while ( true ){
if( index_old > ( lines_old.size() - 1 ) ){
break;
}
String line_old = lines_old.get(index_old);
String line_new = lines_new.get(index_new);
// 先检测是否相等
String line_old_trim = line_old.trim();
String line_new_trim = line_new.trim();
if( line_old_trim.equals( line_new_trim.trim() ) ){
// 相等，直接输出，表示此行没有修改
System.out.println( line_old );
index_old++;
index_new++;
}else {
// 不相等
// 检测相似度，
double similarity = MyStringUitls.calculateSimilarity(line_old_trim, line_new_trim);
if( similarity > 0.5d ){
// 相似，表示此行进行了修改
System.out.println( "-" + line_old );
System.out.println( "+" + line_new );
index_old++;
index_new++;
}else {
// 不相似，表示新版本进行了插入
System.out.println( "+" +line_new );
index_new++;
}
}
}
}
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) {
// System.out.println(line);
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();
}
}
}
}
}
修改 DemoClass2.java 中方法 calculateSimilarity 的代码( 方法内容使用 try catch 包裹 )后比较差异后的的输出效果如下：
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();
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 ){
+ try {
int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
System.out.println("相似度：" + similarity);
return similarity;
+ }catch ( Exception e ){
+ e.printStackTrace();
+ return 0d;
}
}
感觉有点 "git diff" 的那味儿了，其实算法还右很多需要优化的部分，比如这里最开始 index_old、index_new 都初始化为0，这是因为本例中的旧版本文本 DemoClass1.java 和 新版本文本DemoClass2.java 头部的几行都相同。比如新版本删除了行 ...
如下，右侧的新版本删除了 "log.error( msg );" 行。
如下，右侧新版本在 "log.error( msg );" 上面新增了三行。
那么算法在 “String msg = "操作失败，请求参数 "" + paramRemark + "" 为空";” 这一行配对后，分别进去新旧版本各自的下一行后，如何配对呢？换句话说，旧版本取出 “log.error( msg );” 行，新版本无论是新增行还是删除行，都找不到与之配对的行，那么是怎么判断新版本是新增行还是删除行呢？
如上图，新版本在 "log.error( msg );" 行上边新增了三行 "// xxxx"，导致 "log.error( msg );" 被挤到了下边，导致旧版本的行 "log.error( msg );" 未匹配到 新版本的行 "log.error( msg );"( 匹配到了 "// xxxx" )。这时候如果检测 lines_new 中 Index > index_new的部分是否存在line_old，如果存在则表示新版本做了新增行操作，否则表示新版本做了删除行操作。如果做了新增行操作，输出 "+" +line_new，index_new++；如果做了删除行操作，输出 "-" +line_old，index_old++。改进后的算法如下：
import org.apache.commons.text.similarity.LevenshteinDistance;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class MyDiffTest {
public static void main(String[] args) {
List<String> lines_old = loadTxtFile2List("\\xxx\\DemoClass1.java" );
List<String> lines_new = loadTxtFile2List("\\xxx\\DemoClass2.java");
// lines1的起始行和 lines2 的起始行做映射
// 扫描旧版本中的每一行
// xxxx xxxx1 -xxxx
// yyyy yyyy +xxxx1
// xxxxxx xxxxxx xxxxxx
// zzzz zzzz zzzz
int index_old = 0;
int index_new = 0;
while ( true ){
if( index_old > ( lines_old.size() - 1 ) ){
break;
}
String line_old = lines_old.get(index_old);
String line_new = lines_new.get(index_new);
// 先检测是否相等
String line_old_trim = line_old.trim();
String line_new_trim = line_new.trim();
if( line_old_trim.equals( line_new_trim.trim() ) ){
// 相等，直接输出，表示此行没有修改
String prefix = getPrefix( index_old, index_new,true );
System.out.println( prefix + line_old );
index_old++;
index_new++;
}else {
// 不相等
// 检测相似度，
double similarity = MyStringUitls.calculateSimilarity(line_old_trim, line_new_trim);
if( similarity > 0.5d ){
// 相似，表示此行进行了修改
String prefix = getPrefix( index_old, index_new,true );
System.out.println( prefix + "-" + line_old );
System.out.println( prefix + "+" + line_new );
index_old++;
index_new++;
}else {
// 不相似，表示新版本进行了 插入 或 删除( 如何判断是做了插入操作还是删除操作呢？ )
Boolean doInsert = false;
// 新版本的当前行和旧版本的当前行相似度低于50%，要么新版本在当前行做了删除行操作，要么新版本在当前行做了新增行操作
// 怎么检测呢？如果是新增操作，则新版本中和 旧版本的 line_old 内容相同的行会被挤到下( 下... )行，
// 即检测 lines_new 中 index> index_new 的部分是否存在内容和 旧版本 line_old 内容一样的行，如果存在，表示新版本做了新增行操作
// 否则，新版本做了删除行操作，
if( contains( lines_new,index_new+1,line_old ) ){
// 新版本做了插入操作
String prefix = getPrefix(index_old, index_new, false);
System.out.println( prefix + "+" +line_new );
index_new++;
}else {
// 新版本做了删除操作
String prefix = getPrefix(index_old, index_new, false);
System.out.println( prefix + "-" +line_old );
index_old++;
}
}
}
}
}
/**
* 检测集合 list 中是否包含 targetElement 元素( 从 index_beginCheck 角标处开始检查，包含该角标 )
* @param list
* @param index_beginCheck
* @return
*/
private static boolean contains(List<String> list, int index_beginCheck,String targetElement) {
int size = list.size();
targetElement = targetElement.trim();
for (int i = index_beginCheck; i < size; i++) {
if( targetElement.equals( list.get( i ).trim() ) ){
return true;
}
}
return false;
}
private static String getPrefix( int index_old,int index_new,boolean matched ){
index_old++;
index_new++;
return ( index_old < 10?" ":"" ) + index_old + "-->" + ( index_new < 10?" ":"" ) + index_new + " " + ( matched?"matched ":"not found " );
}
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) {
// System.out.println(line);
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();
}
}
}
}
}
测试输出如下：
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();
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 ){
+ try {
int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
System.out.println("相似度：" + similarity);
return similarity;
+ }catch ( Exception e ){
+ e.printStackTrace();
+ return 0d;
}
}
其实稍微使用一点现实工作中复杂点的两个版本的代码文件进行diff会发现达不到预期，虽然逻辑上对，但是不是人眼直观看到的，即从 旧版本到新版本的笔变化的步骤，新增一行(+)、删除一行(-)、修改一行(-、+)不是花费最小的，我们应该找出一条最小的编辑步骤，所以还是需要使用动态规划，和求2个字符串的最小编辑距离很类似，只不过这里换成了2个集合，集合中的每个元素是一行文本，...
MyDiffTest_v2.java：
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class MyDiffTest_v2 {
private static final List<String> lines_v1 = loadTxtFile2List("\\xxx\\DemoClass1.txt" );
private static final List<String> lines_v2 = loadTxtFile2List("\\xxx\\DemoClass2.txt");
public static void main(String[] args) {
// 一行代表一个元素
// 删除一个元素，新增一个元素，修改一个元素
// 使用动态规划求出 lines_old 转换为 lines_new 的最小步骤
MinimumTransferWayVO way = calculateMinimumTransferWay(lines_v1, lines_v2);
printOpeartions( way.getOperations() );
}
/**
* ReadOperationVO 不共享操作次数
* @param operations
*/
private static int getOpeartionCount(List<OperationVO> operations) {
int count = 0;
for( OperationVO operation:operations ){
if( operation instanceof ReadOperationVO ){
// ReadOperationVO 不贡献操作次数
}else {
count++;
}
}
return count;
}
private static void printOpeartions(List<OperationVO> operations) {
for( OperationVO operation:operations ){
if( operation instanceof ReadOperationVO ){
ReadOperationVO readOperation = (ReadOperationVO) operation;
System.out.println( " " + lines_v1.get( readOperation.getLineNum_v1() ) );
}else if( operation instanceof InsertOperationVO ){
InsertOperationVO insertOperation = (InsertOperationVO) operation;
System.out.println( "+ " + lines_v2.get( insertOperation.getLineNum_v2() ) );
}else if( operation instanceof DeleteOperationVO ){
DeleteOperationVO deleteOperation = (DeleteOperationVO) operation;
System.out.println( "- " + lines_v1.get( deleteOperation.getLineNum_v1() ) );
}else if( operation instanceof EditOperationVO ){
EditOperationVO editOperation = (EditOperationVO) operation;
System.out.println( "- " + lines_v1.get( editOperation.getLineNum_v1() ) );
System.out.println( "+ " + lines_v2.get( editOperation.getLineNum_v2() ) );
}
}
}
private static MinimumTransferWayVO calculateMinimumTransferWay( List<String> lines_v1,List<String> lines_v2 ){
// dp[i][j] 表示的是将 lines_v1 的前i个元素变换为 lines_new 中的前j个元素需要使用的最优( 即需要转换步骤最少 )的转换方式
MinimumTransferWayVO[][] dp = new MinimumTransferWayVO[lines_v1.size()][lines_v2.size()];
int size_v1 = lines_v1.size();
int size_v2 = lines_v2.size();
for (int lineNum_v1 = 0; lineNum_v1 < size_v1; lineNum_v1++) {
String line_v1 = lines_v1.get( lineNum_v1 );
String line_v1_trim = line_v1.trim();
for (int lineNum_v2 = 0; lineNum_v2 < size_v2; lineNum_v2++) {
String line_v2 = lines_v2.get( lineNum_v2 );
String line_v2_trim = line_v2.trim();
MinimumTransferWayVO minimumTransferWay = new MinimumTransferWayVO();
if( lineNum_v1 == 0 ){
if( lineNum_v2 == 0 ){
// v1 和 v2 都只有 1 行文本，此时最简单，只需要检测这 1 行文本是否相同？
/*
v1 v2
1111111111111111111111 ==》 1111111111111111111111
*/
List<OperationVO> steps = new ArrayList<>();
if( line_v1_trim.equals( line_v2_trim ) ){
// 相同,不需要任何变换
}else {
// 不相同,需要 1 步修改操作
EditOperationVO editOperation = new EditOperationVO();
editOperation.setLineNum_v1( lineNum_v1 );
editOperation.setLineNum_v2( lineNum_v2 );
steps.add( editOperation );
}
minimumTransferWay.setOperations( steps );
}else {
// v1只有1行文本，v2有多行文本，此时的变换也比较简单，
// 检测 line_v1 在 lines_v2 中是否存在
List<OperationVO> operations = new ArrayList<>();
if( contains( lines_v2,line_v1_trim,0,lineNum_v2 ) ){
// line_v1 在 lines_v2 中存在
/*
v1 v2
1111111111111111111111 ==》 2222222222222222222222
1111111111111111111111
444444444444444444444444
555555555555555555
如下一种情形，v1转换为v2需要在 "1111111111111111111111" 上面插入一行 "2222222222222222222222",
然后在 "1111111111111111111111" 下面插入 "444444444444444444444444"、"555555555555555555" 行
*/
// firstEqualIndex 介于 0 和 lineNum_v2 之间
int firstEqualIndex = getFirstEqualIndex(lines_v2, line_v1_trim, 0, lineNum_v2);
for (int lineNum = 0; lineNum <=lineNum_v2 ; lineNum++) {
if( lineNum == firstEqualIndex ){
ReadOperationVO readOperation = new ReadOperationVO();
readOperation.setLineNum_v1( lineNum_v1 );
readOperation.setLineNum_v1( lineNum );
operations.add( readOperation );
}else {
// 插入行
InsertOperationVO insertOperation = new InsertOperationVO();
insertOperation.setLineNum_v2( lineNum );
operations.add( insertOperation );
}
}
}else {
// line_v1 在 lines_v2 中不存在
/*
v1 v2
1111111111111111111111 ==》 2222222222222222222222
3333333333333333333
444444444444444444444444
555555555555555555
此时，v1 转换成 v2，需要先删除 "1111111111111111111111" 行，
再插入 "2222222222222222222222"、
"3333333333333333333"、
"444444444444444444444444"、
"555555555555555555" 行
*/
DeleteOperationVO deleteOperation = new DeleteOperationVO();
deleteOperation.setLineNum_v1( lineNum_v1 );
operations.add( deleteOperation );
for (int lineNum = 0; lineNum <= lineNum_v2; lineNum++) {
InsertOperationVO insertOperation = new InsertOperationVO();
insertOperation.setLineNum_v2( lineNum );
operations.add( insertOperation );
}
}
minimumTransferWay.setOperations( operations );
}
}else {
if( lineNum_v2 == 0 ){
// v1有多行文本，v1只有1行文本,
List<OperationVO> operations = new ArrayList<>();
// 检测 line_v2 是否在 lines_v1 中存在
if( contains(lines_v1, line_v2_trim, 0, lineNum_v1) ){
// line_v2 在 lines_v1 中存在
/*
v1 v2
11111111111111 333333333333
333333333333
444444444444444
5555555555
*/
// 此时，v1转换为 v2需要删除 "333333333333" 上面的 "11111111111111"行，删除 "333333333333" 下面的 "444444444444444"、"5555555555" 行
int firstEqualIndex = getFirstEqualIndex(lines_v1, line_v2_trim, 0, lineNum_v1);
for (int lineNum = 0; lineNum <=lineNum_v1 ; lineNum++) {
if( lineNum == firstEqualIndex){
ReadOperationVO readOperation= new ReadOperationVO();
readOperation.setLineNum_v1( lineNum );
readOperation.setLineNum_v2( lineNum_v2 );
operations.add( readOperation );
}else {
// 删除行
DeleteOperationVO deleteOperation = new DeleteOperationVO();
deleteOperation.setLineNum_v1( lineNum );
operations.add( deleteOperation );
}
}
}else {
// line_v2 在 lines_v1 中不存在
/*
v1 v2
11111111111111 22222222222222
333333333333
444444444444444
5555555555
*/
// 此时，v1 转换为 v2 需要删除 "11111111111111"、 "333333333333"、 "444444444444444"、 "5555555555"，再新增 "22222222222222"
for (int lineNum = 0; lineNum <=lineNum_v1 ; lineNum++) {
// 删除行
DeleteOperationVO deleteOperation = new DeleteOperationVO();
deleteOperation.setLineNum_v1( lineNum );
operations.add( deleteOperation );
}
// 插入行
InsertOperationVO insertOperation = new InsertOperationVO();
insertOperation.setLineNum_v2( lineNum_v2 );
operations.add( insertOperation );
}
minimumTransferWay.setOperations( operations );
}else {
List<OperationVO> operations = new ArrayList<>();
// v1 和 v2 都有多行文本，最复杂。
// 检测 v1 的 v2 的当前行是否相同
if( line_v1_trim.equals( line_v2_trim ) ){
// line_v1 和 line_v2 相同
/*
v1 v2
11111111 1111111
22222222 33333
... ...
44444444 555555
66666666 66666666
*/
// 如上所示，v1的当前行 "66666666" 和 v2 的当前行 "66666666" 相同，只需要看 v1 点位前面部分 转换wield v2的前面部分的最小转换方式就行了，
MinimumTransferWayVO minimumTransferWay_prev = dp[lineNum_v1 - 1][lineNum_v2 - 1];
// todo 是否需要深拷贝
operations.addAll( minimumTransferWay_prev.getOperations() );
// 追加一个读操作，方便输出转换过程
ReadOperationVO readOperation = new ReadOperationVO();
readOperation.setLineNum_v1( lineNum_v1 );
readOperation.setLineNum_v2( lineNum_v2 );
operations.add( readOperation );
}else {
// line_v1 和 line_v2 不相同
/*
v1 v2
11111111 1111111
22222222 33333
... ...
44444444 555555
66666666 7777777
*/
// 如上所示，v1 的当前行 "66666666" 和 v2 的当前行 "7777777" 不相同,则有3个候选转换方式，需要从中选择最小的转换方式
// 1. v1 的前面部分转换为 v2的前面部分，v1的 当前行 "66666666" 修改为 v2 的当前行 "7777777"
MinimumTransferWayVO minimumTransferWay_prev1 = dp[lineNum_v1 - 1][lineNum_v2 - 1];
int opeartionCount_1 = getOpeartionCount(minimumTransferWay_prev1.getOperations());
// 2. v1 的前面部分 转换为 v2 的前面部分 + v2 的当前行部分，删除 v1 的当前行 "66666666"
MinimumTransferWayVO minimumTransferWay_prev2 = dp[lineNum_v1 - 1][lineNum_v2];
int opeartionCount_2 = getOpeartionCount(minimumTransferWay_prev2.getOperations());
// 3. v1 的前面部分 + v1 的当前行部分 转换为 v2 的前面部分，v2 新增当前行 "7777777"
MinimumTransferWayVO minimumTransferWay_prev3 = dp[lineNum_v1 ][lineNum_v2 - 1];
int opeartionCount_3 = getOpeartionCount(minimumTransferWay_prev3.getOperations());
boolean isOne = true;
boolean isTwo = false;
boolean isThree = false;
MinimumTransferWayVO minimumTransferWay_prev = minimumTransferWay_prev1;
int opeartionCount = opeartionCount_1;
if( opeartionCount_2 < opeartionCount ){
minimumTransferWay_prev = minimumTransferWay_prev2;
opeartionCount = opeartionCount_2;
isOne = false;
isTwo = true;
isThree = false;
}
if( opeartionCount_3 < opeartionCount ){
minimumTransferWay_prev = minimumTransferWay_prev3;
opeartionCount = opeartionCount_3;
isOne = false;
isTwo = false;
isThree = true;
}
operations.addAll( minimumTransferWay_prev.getOperations() );
if( isOne ){
// v1 的 当前行 "66666666" 修改为 v2 的当前行 "7777777"
EditOperationVO editOperation = new EditOperationVO();
editOperation.setLineNum_v1( lineNum_v1 );
editOperation.setLineNum_v2( lineNum_v2 );
operations.add( editOperation );
}else if( isTwo ){
// 删除 v1 的当前行 "66666666"
DeleteOperationVO deleteOperation = new DeleteOperationVO();
deleteOperation.setLineNum_v1( lineNum_v1 );
operations.add( deleteOperation );
}else if( isThree ){
// v2 新增当前行 "7777777"
InsertOperationVO insertOperation = new InsertOperationVO();
insertOperation.setLineNum_v2( lineNum_v2 );
operations.add( insertOperation );
}
}
minimumTransferWay.setOperations( operations );
}
}
dp[ lineNum_v1 ][ lineNum_v2 ] = minimumTransferWay;
}
}
return dp[ lines_v1.size() -1 ][ lines_v2.size() -1 ];
}
/**
* @param list
* @param targetElement
* @param beginIndex
* @param endIndex
* @return
*/
private static boolean contains(List<String> list, String targetElement, int beginIndex, int endIndex) {
for (int i = beginIndex; i <=endIndex ; i++) {
if( targetElement.equals( list.get( i ).trim() ) ){
return true;
}
}
return false;
}
private static int getFirstEqualIndex(List<String> list, String targetElement, int beginIndex, int endIndex) {
for (int i = beginIndex; i <=endIndex ; i++) {
if( targetElement.equals( list.get( i ).trim() ) ){
return i;
}
}
return -1;
}
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) {
// System.out.println(line);
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();
}
}
}
}
}
MinimumTransferWayVO.java：
import lombok.Getter;
import lombok.Setter;
import java.io.Serializable;
import java.util.List;
@Getter
@Setter
public class MinimumTransferWayVO implements Serializable {
private List<OperationVO> operations;
}
OperationVO.java：
import lombok.Getter;
import lombok.Setter;
import java.io.Serializable;
@Getter
@Setter
public class OperationVO implements Serializable {
}
ReadOperationVO.java：
import lombok.Getter;
import lombok.Setter;
/**
* ReadOperationVO 不贡献操作步数，只是为了方便输出v1到v2的整个变换过程
**/
@Getter
@Setter
public class ReadOperationVO extends OperationVO {
// 此时 lines_v1[ lineNum_v1 ] 和 lines_v2[ lineNum_v2 ] 相同
private int lineNum_v1;
private int lineNum_v2;
}
InsertOperationVO.java：
import lombok.Getter;
import lombok.Setter;
import java.io.Serializable;
@Getter
@Setter
public class InsertOperationVO extends OperationVO {
private int lineNum_v2;
}
DeleteOperationVO.java：
import lombok.Getter;
import lombok.Setter;
import java.io.Serializable;
@Getter
@Setter
public class DeleteOperationVO extends OperationVO {
private int lineNum_v1;
}
EditOperationVO.java：
import lombok.Getter;
import lombok.Setter;
@Getter
@Setter
public class EditOperationVO extends OperationVO {
private int lineNum_v1;
private int lineNum_v2;
}
DemoClass1.txt 和 DemoClass2.txt 的文本内容如下所示：
测试输出如下所示：
本文转载自: https://blog.csdn.net/heshiyuan1406146854/article/details/134600458
版权归原作者 狄龙疤 所有， 如有侵权，请联系我们删除。
版权归原作者 狄龙疤 所有， 如有侵权，请联系我们删除。