使用求2个字符串最长公共子序列的方法来实现 git diff 算法 java 实现

【代码】使用求2个字符串最长公共子序列的方法来实现 git diff 算法 java 实现。

NullPointerExpection

571人浏览 · 2023-11-29 14:46:53

NullPointerExpection · 2023-11-29 14:46:53 发布

测试类 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;
+         }
      }
  }