문자열 차이 비교 알고리즘 분석

문자열 차이 비교 알고리즘 은 보통 같은 파일 의 다른 버 전이 나 같은 글 두 편의 같은 부분 을 비교 하 는 데 사 용 됩 니 다.다음은 문 제 를 다음 과 같이 설명 한다.
두 문자열 a, b 를 지정 합 니 다.작성 자 는 a 와 b 의 같은 부분 을 빈 칸 으로 대체 하고 다른 부분 은 보류 합 니 다.
예 를 들 어 a = "평생 한 가지 일 만 한다", b = "태 어 날 때 부터 한 가지 일 만 한다".처 리 를 거 친 후에 문자열 a 는 '평생' 으로 바 뀌 었 고 문자열 b 는 '태어나면서' 로 바 뀌 었 다.
위 와 같이 처리 한 후에 우 리 는 빈 칸 이 아 닌 하 이 라이트 만 있 으 면 두 텍스트 의 다른 점 을 한눈 에 알 수 있다.
위의 문 제 는 비교적 직접적인 사 고 는 두 문자열 을 문자 의 집합 으로 나 누 어 두 문자 의 집합 을 구 하 는 것 이다.그리고 교 집합 에 있 는 문 자 를 빈 칸 으로 바 꿉 니 다.그러나 문 제 를 완벽 하 게 해결 할 수 는 없다.예 를 들 어 문자열 a 에 '하나' 가 두 번 나 타 났 고 b 에 한 번 나 타 났 다.프로그램 은 a 중의 두 개의 '하나' 를 모두 같은 부분 으로 착각 할 수 있다.그리하여 a = "생" 을 얻다.
위의 문제 가 발생 한 이 유 는 한 글자 가 문자열 에서 반복 되 기 쉬 우 므 로 문자열 을 길이 가 2 인 하위 문자열 로 분해 하 는 것 을 고려 해 보 자.예 를 들 어 a 는: ， ， ， ， ， ， 로 분해 된다.b 분 해 는: ， ， ， ， ， .두 문자열 모두 ， ， ， 가 있 음 을 알 수 있다.같은 부분 을 빼 면 정확 한 결 과 를 얻 을 수 있다.
그러나 글 이 길 면 길이 가 2 인 하위 문자열 도 중복 된다.이것 은 우리 가 가장 긴 하위 꼬치 부터 중복 항목 을 찾 아야 한 다 는 것 을 알려 준다.
해결 방향: a, b 의 짧 은 문자열 을 a 로 가정 하고 그 길 이 를 $l 로 가정 합 니 다.a $, 즉:

l=$l_a$

문자열 의 길이 가 l 인 하위 문자열 을 끝까지 들 고 각 하위 문자열 에 대해 문자열 b 가 이 하위 문자열 을 포함 하 는 지 확인 합 니 다

포함 하면 a, b 의 해당 부분 을 빈 칸 으로 설정 합 니 다.a 중 스페이스 바 영역 왼쪽 이 빈 문자열 이 아니라면 b 와 재 귀적 으로 비교 합 니 다.마찬가지 로 a 중 빈 칸 구역 오른쪽 이 빈 문자열 이 아니라면 b 와 진일보 한 재 귀 비 교 를 한다.(좌우 재 귀 는 a 의 하위 문자열 을 가난 하 게 들 때 빈 문자열 로 설 정 된 부분 을 피하 기 위해 서) 결 과 를 직접 되 돌려 줍 니 다.

2 단계 의 모든 하위 문자열 b 가 포함 되 지 않 으 면 l = l / 2

주의: a 와 b 가 비슷 할 때 이 알고리즘 은 효율 이 높 습 니 다.l 최대 가능 한 하위 꼬치 부터 끝까지 들 기 때문에 대량의 같은 부분 을 빈 칸 으로 설정 하여 후속 적 인 하위 꼬치 의 계 산 량 을 줄 일 수 있다.만약 에 a 와 b 가 거의 다르다 면 비교 의 복잡 도 는 a *b 와 정비례 할 것 이다.
알고리즘 의 관건 적 인 부분 은 다음 과 같 습 니 다 (자바 언어 설명). 알고리즘 의 입 구 는 첫 번 째 getDiff 방법 입 니 다.

    
    //          ，          ，               
    public String[] getDiff(String a, String b) {
        String[] result = null;
        //                
        if (a.length() < b.length()) {
            result = getDiff(a, b, 0, a.length());
        } else {
            result = getDiff(b, a, 0, b.length());
            result = new String[]{result[1],result[0]};
        }
        return result;
    }
    
    // a      b          
    private String[] getDiff(String a, String b, int start, int end){
        String[] result = new String[]{a, b};
        int len = result[0].length();
        while (len > 0) {
            for (int i = start; i < end - len + 1; i++) {
                String sub = result[0].substring(i, i + len);
                int idx = -1;
                if ((idx = result[1].indexOf(sub)) != -1) {
                    System.out.println(sub);
                    result[0] = setEmpty(result[0], i, i + len);
                    result[1] = setEmpty(result[1], idx, idx + len);
                    if (i > 0) {
                        //            
                        result = getDiff(result[0], result[1], 0, i);
                    }
                    if (i + len < end) {
                        //            
                        result = getDiff(result[0], result[1], i + len, end);
                    }
                    len=0;//  while  
                    break;
                }
            }
            len = len / 2;
        }
        return result;
    }

    //    s          
    public String setEmpty(String s, int start, int end) {
        char[] array = s.toCharArray();
        for (int i = start; i < end; i++) {
            array[i] = ' ';
        }
        return new String(array);
    }