문자열 차이점 발견 전략(Diff Strategies)

본 문서는 http://neil.fraser.name/writing/diff/의 내용을 번역한 것입니다.

2006년 4월에 네일 프레서(Neil Fraser)에 의해서

두 문자열 간의 차이점을 계산하는 것은 많은 응용 프로그램의 중요 연산이다. 아래는 두 문자열 간의 차이점에 대한 간단한 예제이다.

Text 1: Apples are a fruit.

Text 2: Bananas are also fruit.

Diff:      AppleBananas are also fruit.

이 글은 차이 발견 알고리즘에 대한 문헌들을 조사하고, 그것들을 비교하고, 실제 활용엣 그들의 유용성을 증대시키기 위한 여러 기술들을 설명한다. 특별히, 우리는 선행 처리 최적화, 특정 작업을 위한 최적의 차이 발견 알고리즘의 선택, 그리고 사후처리 제거 방식 등에 대해서 논의한다.

---

1. 선행 처리 최적화

심지어 가장 잘 알려진 차이 발견 알고리즘조차 계산이 많이 필요한 처리 단계이다. 대부분의 실제 상황에서, 비교되는 두 시퀀스들(문자열)은 어떤 한도 내에서 서로 비슷하다. 이러한 관찰은 알고리즘의 실제 동작 시간을 개선할 수 있는 다양한 최적화를 가능하게 하고, 특정 상황에서는 알고리즘을 실행할 필요 조차 없앨 수도 있다.

1.1. 동일성

가장 명백하고, 가장 단순한 최적화는 동일성 비교이다. 사실 두 시퀀스가 완전히 동일할 경우가 많기 때문에, 이런 경우를 검사하는 것은 매우 간단하고, 이것을 먼저 검사하는 것이 논리적이다. 이 검사의 부작용은 뒤의 코드들을 간단하게 한다는 점이다. 이 검사 후에, 차이점이 반드시 있을 것임이 보장된다. 게다가 null인 경우가 제거된다.

JavaScript Code

1. if (text1 == text2)  
2.   return null;  

Java Code

1. if (text1.equals(text2))  
2.   return null; 

Python Code

1. if text1 == text2:  
2.   return None  

1.2. 공통 접두사/접미사

만약 문자열들 간에 어떠한 공통점이 존재한다면, 그들 간에는 시작과 종료 지점에 공통 부분 문자열을 공유하기 쉽다.

Text 1: The cat in the hat.

Text 2: The dog in the hat.

이것은 다음과 같이 간략화 될 수 있다.

Text 1: cat

Text 2: dog

이러한 공통 부분 문자열을 위치시키는 것은 이진 검색을 이용해서 O(log n)에 수행될 수 있다. 이진 검색은 최악의 경우에도 최소한 효율적이고, 아무런 공통성도 가지지 않는 것이 현실 세계에서는 매우 일반적이기 때문이다. 그러므로 검색을 시작하기 전에 처음(혹은 끝의) 문자에 대해 빠른 검사를 하는 것이 합리적이다.

(이 절은 많은 이메일을 받도록 만들었다. 제기되었던 문제는 설명한 알고리즘은 O(n log n)인데, 문자열 동일성 비교 연산 (a == b)가 일반적으로 O(n)이라는 내용이었다. 하지만, 고차원 언어를 다룰 때, 루프 연산과 동일성 비교 연산의 속도 차이는 모든 그러한 현실적인 목적에 대해서라면 O(1)으로 고려되어질 수 있다. 더 복잡한 문제는 모든 문자열에 대한 해시 테이블을 사용하는 파이썬과 같은 언어는, 동일성 검사를 O(1)로 만들며, 문자열 생성을 O(n)으로 만든다. 더 자세한 내용은, 성능 평가(http://neil.fraser.name/news/2007/10/09/)를 참고하기 바란다.

JavaScript Code

1. function diff_commonPrefix(text1, text2) {  
2.   // Quick check for common null cases.  
3.   if (!text1 || !text2 || text1.charCodeAt(0) !== text2.charCodeAt(0)) {  
4.     return 0;  
5.   }  
6.   // Binary search.  
7.   var pointermin = 0;  
8.   var pointermax = Math.min(text1.length, text2.length);  
9.   var pointermid = pointermax;  
10.   var pointerstart = 0;  
11.   while (pointermin < pointermid) {  
12.     if (text1.substring(pointerstart, pointermid) ==  
13.         text2.substring(pointerstart, pointermid)) {  
14.       pointermin = pointermid;  
15.       pointerstart = pointermin;  
16.     } else {  
17.       pointermax = pointermid;  
18.     }  
19.     pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);  
20.   }  
21.   return pointermid;  
22. }  
23.   
24. function diff_commonSuffix(text1, text2) {  
25.   // Quick check for common null cases.  
26.   if (!text1 || !text2 || text1.charCodeAt(text1.length - 1) !==  
27.                           text2.charCodeAt(text2.length - 1)) {  
28.     return 0;  
29.   }  
30.   // Binary search.  
31.   var pointermin = 0;  
32.   var pointermax = Math.min(text1.length, text2.length);  
33.   var pointermid = pointermax;  
34.   var pointerend = 0;  
35.   while (pointermin < pointermid) {  
36.     if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==  
37.         text2.substring(text2.length - pointermid, text2.length - pointerend)) {  
38.       pointermin = pointermid;  
39.       pointerend = pointermin;  
40.     } else {  
41.       pointermax = pointermid;  
42.     }  
43.     pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);  
44.   }  
45.   return pointermid;  
46. }  

Java Code

1. public int diff_commonPrefix(String text1, String text2) {  
2.   // Quick check for common null cases.  
3.   if (text1.length() == 0 || text2.length() == 0 ||  
4.       text1.charAt(0) != text2.charAt(0)) {  
5.     return 0;  
6.   }  
7.   // Binary search.  
8.   int pointermin = 0;  
9.   int pointermax = Math.min(text1.length(), text2.length());  
10.   int pointermid = pointermax;  
11.   int pointerstart = 0;  
12.   while (pointermin < pointermid) {  
13.     if (text1.regionMatches(pointerstart, text2, pointerstart,  
14.         pointermid - pointerstart)) {  
15.       pointermin = pointermid;  
16.       pointerstart = pointermin;  
17.     } else {  
18.       pointermax = pointermid;  
19.     }  
20.     pointermid = (pointermax - pointermin) / 2 + pointermin;  
21.   }  
22.   return pointermid;  
23. }  
24.   
25. public int diff_commonSuffix(String text1, String text2) {  
26.   // Quick check for common null cases.  
27.   if (text1.length() == 0 || text2.length() == 0 ||  
28.       text1.charAt(text1.length() - 1) != text2.charAt(text2.length() - 1)) {  
29.     return 0;  
30.   }  
31.   // Binary search.  
32.   int pointermin = 0;  
33.   int pointermax = Math.min(text1.length(), text2.length());  
34.   int pointermid = pointermax;  
35.   int pointerend = 0;  
36.   while (pointermin < pointermid) {  
37.     if (text1.regionMatches(text1.length() - pointermid, text2,  
38.                             text2.length() - pointermid,  
39.                             pointermid - pointerend)) {  
40.       pointermin = pointermid;  
41.       pointerend = pointermin;  
42.     } else {  
43.       pointermax = pointermid;  
44.     }  
45.     pointermid = (pointermax - pointermin) / 2 + pointermin;  
46.   }  
47.   return pointermid;  
48. }  

Python Code

1. def diff_commonPrefix(text1, text2):  
2.   # Quick check for common null cases.  
3.   if not text1 or not text2 or text1[0] != text2[0]:  
4.     return 0  
5.   # Binary search.  
6.   pointermin = 0  
7.   pointermax = min(len(text1), len(text2))  
8.   pointermid = pointermax  
9.   pointerstart = 0  
10.   while pointermin < pointermid:  
11.     if text1[pointerstart:pointermid] == text2[pointerstart:pointermid]:  
12.       pointermin = pointermid  
13.       pointerstart = pointermin  
14.     else:  
15.       pointermax = pointermid  
16.     pointermid = int((pointermax - pointermin) / 2 + pointermin)  
17.   return pointermid  
18.   
19. def diff_commonSuffix(text1, text2):  
20.   # Quick check for common null cases.  
21.   if not text1 or not text2 or text1[-1] != text2[-1]:  
22.     return 0  
23.   # Binary search.  
24.   pointermin = 0  
25.   pointermax = min(len(text1), len(text2))  
26.   pointermid = pointermax  
27.   pointerend = 0  
28.   while pointermin < pointermid:  
29.     if (text1[-pointermid:len(text1) - pointerend] ==  
30.         text2[-pointermid:len(text2) - pointerend]):  
31.       pointermin = pointermid  
32.       pointerend = pointermin  
33.     else:  
34.       pointermax = pointermid  
35.     pointermid = int((pointermax - pointermin) / 2 + pointermin)  
36.   return pointermid  

GNU diff 프로그램(접두사와 접미사에 대해 선형 검색을 수행하는)는 그들의 문서에서 주장하기를(http://www.gnu.org/software/diffutils/manual/html_node/diff-Performance.html), "때때로 [접두사와 접미사 떼어내기]가 최소가 아닌 결과를 생성할 수도 있다"라고 한다. 비록 그들이 이것에 대한 예를 제공하지 않지만 말이다.

1.3. 단일 삽입/삭제

매우 일반적인 차이점은 몇몇 문자열의 삽입 또는 삭제이다.

Text 1: The cat in the hat.                | Text 1: The cat in the hat.

Text 2: The furry cat in the hat.       | Text 2: The cat.

공통의 접두사와 접미사를 제거하면, 다음을 얻을 수 있다.

Text 1:                                    | Text 1:  in the hat

Text 2: furry                           | Text 2: 

첫 예제에서 비어 있는 'Text1'의 존재는 'Text2'가 삽입임을 나타낸다. 두 번째 예제에서 비어있는 'Text2'의 존재는 'Text1'이 삭제임을 나타낸다. 이러한 일반적인 경우들을 발견하는 것은 차이점 발견 알고리즘을 실행시킬 필요성을 제거하게 된다.

아래의 예제 코드와 그리고 이후의 예제 코드에서, 차이점 집합을 표현하기 위한 내부 포맷은 튜플의 배열이다. 각 튜플의 첫번째 요소는 해당 튜플이 삽입(DIFF_INSERT)인지, 삭제(DIFF_DELETE) 혹은 동일(DIFF_EQUAL)한지 명시한다. 두번째 요소는 영향 받은 문자열을 명시한다.

JavaScript Code

1. if (!text1) {  
2.   // Just add some text.  
3.   return [[DIFF_INSERT, text2]];  
4. }  
5. if (!text2) {  
6.   // Just delete some text.  
7.   return [[DIFF_DELETE, text1]];  
8. }  

Java Code

1. LinkedList<Diff> diffs = new LinkedList<Diff>();  
2. if (text1.length() == 0) {  
3.   // Just add some text.  
4.   diffs.add(new Diff(Operation.INSERT, text2));  
5.   return diffs;  
6. }  
7. if (text2.length() == 0) {  
8.   // Just delete some text.  
9.   diffs.add(new Diff(Operation.DELETE, text1));  
10.   return diffs;  
11. }  

Python Code

1. if not text1:  
2.   # Just add some text.  
3.   return [(DIFF_INSERT, text2)]  
4. if not text2:  
5.   # Just delete some text.  
6.   return [(DIFF_DELETE, text1)]

1.4. 두 번의 편집

두 번의 편집을 감지하고 다루는 것은 단일의 편집들을 다루는 것보다 어렵다. 두 단순한  삽입은 'Text2' 안에 'Text1'이 존재하는지 찾음으1.4. 두 번의 편집로서 감지할 수 있다. 마찬가지로 두개의 단순한 삭제는 'Text1' 안에 'Text2'가 존재하는지 찾음으로써 감지할 수 있다.

Text 1: The cat in the hat.

Text 2: The happy cat in the black hat.

첫 번째 단계로써 공통의 접두사와 접미사를 제거하는 것은 남아있는 문자열의 각 끝에 차이점이 있음을 보장한다.다음으로 짧아진 문자열 ("cat it the")가 긴 문자열인 ("happy cat in the black")에 있는지 결정하는 것은 쉽다.

JavaScript Code

1. var longtext = text1.length > text2.length ? text1 : text2;  
2. var shorttext = text1.length > text2.length ? text2 : text1;  
3. var i = longtext.indexOf(shorttext);  
4. if (i != -1) {  
5.   // Shorter text is inside the longer text.  
6.   diffs = [[DIFF_INSERT, longtext.substring(0, i)],  
7.            [DIFF_EQUAL, shorttext],  
8.            [DIFF_INSERT, longtext.substring(i + shorttext.length)]];  
9.   // Swap insertions for deletions if diff is reversed.  
10.   if (text1.length > text2.length) {  
11.     diffs[0][0] = diffs[2][0] = DIFF_DELETE;  
12.   }  
13.   return diffs;  
14. }  

Java Code

1. String longtext = text1.length() > text2.length() ? text1 : text2;  
2. String shorttext = text1.length() > text2.length() ? text2 : text1;  
3. int i = longtext.indexOf(shorttext);  
4. if (i != -1) {  
5.   // Shorter text is inside the longer text.  
6.   Operation op = (text1.length() > text2.length()) ?  
7.                  Operation.DELETE : Operation.INSERT;  
8.   diffs.add(new Diff(op, longtext.substring(0, i)));  
9.   diffs.add(new Diff(Operation.EQUAL, shorttext));  
10.   diffs.add(new Diff(op, longtext.substring(i + shorttext.length())));  
11.   return diffs;  
12. }  

Python Code

1. if len(text1) > len(text2):  
2.   (longtext, shorttext) = (text1, text2)  
3. else:  
4.   (shorttext, longtext) = (text1, text2)  
5. i = longtext.find(shorttext)  
6. if i != -1:  
7.   # Shorter text is inside the longer text.  
8.   diffs = [(DIFF_INSERT, longtext[:i]), (DIFF_EQUAL, shorttext),  
9.            (DIFF_INSERT, longtext[i + len(shorttext):])]  
10.   # Swap insertions for deletions if diff is reversed.  
11.   if len(text1) > len(text2):  
12.     diffs[0] = (DIFF_DELETE, diffs[0][1])  
13.     diffs[2] = (DIFF_DELETE, diffs[2][1])  
14.   return diffs  

만약 편집이 단순한 두 번의 삽입이나 단순한 두번의 삭제가 아니면 상황은 더욱 복잡해진다. 이들 경우는 아마 검색이 수행되어지는 대상 문자열에서 두 편집들을 분리하면 아마 대부분의 경우 감지할 수 있을 것이다.

Text 1: The cat in the hat.

Text 2: The ox in the box.

공통의 접두사와 접미사를 제거하면 다음을 얻을 수 있다.

Text 1: cat in the hat

Text 2: ox in the box

만약 최소한 주어진 문자열 중 긴 문자열의 절반의 길이를 가진 부분 문자열이 두 주어진 문자열 안에 존재하면, 그것이 공통의 문자열이 될 것임이 보장된다. 이 경우에 주어진 문자열들은 두 부분으로 쪼개질 수 있고, 별개의 차이점 비교 연산들이 수행된다.

Text 1: cat     | Text 1: hat

Text 2: ox      | Text 2: box

이러한 검사를 재귀적으로 수행하는 것은 아마 일반적으로 더 많은 쪼개짐을 야기할 것이다. 비록 위의 에제에서는 추가적인 쪼개짐이 없지만 말이다.

최장 공통 부분 문자열 찾기는 차이점을 계산하는 것만큼 복잡한 연산이다. 이 말은 이 지점에서는 개선이 없을 수도 있을 것이라는 뜻이다. 하지만, 공통 부분이 반드시 최소한 긴 문자열의 절반이 되어야 한다는 제한점은 성능 개선을 제공할 것이다. 아래의 그림에서 표현한 것처럼, 만약 그러한 길이의 공통 부분 문자열이 존재하면, 다음에 가장 긴 문자열의 2/4와 3/4의 문자열은 이 부분 문자열의 일부를 형성해야한다.

이 부분에는 동작하는 코드가 있는데 이 링크(http://neil.fraser.name/writing/diff/#hl_2)를 따라가서 확인하길 바란다.

더 짧은 문자열은 이 두 1/4 길이의 문자열에 대해서 일치하는지 검색될 수 있고, 공통의 접두사와 접미사를 찾음으로써 두 주어진 문자열에 대해서 어떠한 종류의 일치가 있는지 비교되어질 수 있다. 문자열들은 주어진 문자열 중 더 긴 문자열의 중간 길이 이상인 최장 일치의 지점에서 쪼개질 것이다. 반복되는 문자열이 있는 문제 때문에, 단순히 필요한 길이에 도달한 첫번째 문자열 뿐만 아니라 각 1/4 길이의 문자열 안의 일치들도 검사되어져야 한다.

JavaScript Code

1. // Check to see if the problem can be split in two.  
2. var hm = diff_halfMatch(text1, text2);  
3. if (hm) {  
4.   // A half-match was found, sort out the return data.  
5.   var text1_a = hm[0];  
6.   var text1_b = hm[1];  
7.   var text2_a = hm[2];  
8.   var text2_b = hm[3];  
9.   var mid_common = hm[4];  
10.   // Send both pairs off for separate processing.  
11.   var diffs_a = diff_main(text1_a, text2_a);  
12.   var diffs_b = diff_main(text1_b, text2_b);  
13.   // Merge the results.  
14.   return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);  
15. }  
16.   
17. function diff_halfMatch(text1, text2) {  
18.   // Do the two texts share a substring which is at least half the length of the  
19.   // longer text?  
20.   var longtext = text1.length > text2.length ? text1 : text2;  
21.   var shorttext = text1.length > text2.length ? text2 : text1;  
22.   if (longtext.length < 10 || shorttext.length < 1) {  
23.     return null;  // Pointless.  
24.   }  
25.   
26.   function diff_halfMatchI(longtext, shorttext, i) {  
27.     // Start with a 1/4 length substring at position i as a seed.  
28.     var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));  
29.     var j = -1;  
30.     var best_common = '';  
31.     var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;  
32.     while ((j = shorttext.indexOf(seed, j + 1)) != -1) {  
33.       var prefixLength = diff_commonPrefix(longtext.substring(i),  
34.                                            shorttext.substring(j));  
35.       var suffixLength = diff_commonSuffix(longtext.substring(0, i),  
36.                                            shorttext.substring(0, j));  
37.       if (best_common.length < suffixLength + prefixLength) {  
38.         best_common = shorttext.substring(j - suffixLength, j) +  
39.             shorttext.substring(j, j + prefixLength);  
40.         best_longtext_a = longtext.substring(0, i - suffixLength);  
41.         best_longtext_b = longtext.substring(i + prefixLength);  
42.         best_shorttext_a = shorttext.substring(0, j - suffixLength);  
43.         best_shorttext_b = shorttext.substring(j + prefixLength);  
44.       }  
45.     }  
46.     if (best_common.length >= longtext.length / 2) {  
47.       return [best_longtext_a, best_longtext_b,  
48.               best_shorttext_a, best_shorttext_b, best_common];  
49.     } else {  
50.       return null;  
51.     }  
52.   }  
53.   
54.   // First check if the second quarter is the seed for a half-match.  
55.   var hm1 = diff_halfMatchI(longtext, shorttext,  
56.                              Math.ceil(longtext.length / 4));  
57.   // Check again based on the third quarter.  
58.   var hm2 = diff_halfMatchI(longtext, shorttext,  
59.                              Math.ceil(longtext.length / 2));  
60.   var hm;  
61.   if (!hm1 && !hm2) {  
62.     return null;  
63.   } else if (!hm2) {  
64.     hm = hm1;  
65.   } else if (!hm1) {  
66.     hm = hm2;  
67.   } else {  
68.     // Both matched.  Select the longest.  
69.     hm = hm1[4].length > hm2[4].length ? hm1 : hm2;  
70.   }  
71.   
72.   // A half-match was found, sort out the return data.  
73.   var text1_a, text1_b, text2_a, text2_b;  
74.   if (text1.length > text2.length) {  
75.     text1_a = hm[0];  
76.     text1_b = hm[1];  
77.     text2_a = hm[2];  
78.     text2_b = hm[3];  
79.   } else {  
80.     text2_a = hm[0];  
81.     text2_b = hm[1];  
82.     text1_a = hm[2];  
83.     text1_b = hm[3];  
84.   }  
85.   var mid_common = hm[4];  
86.   return [text1_a, text1_b, text2_a, text2_b, mid_common];  
87. }  

Java Code

1. // Check to see if the problem can be split in two.  
2. String[] hm = diff_halfMatch(text1, text2);  
3. if (hm != null) {  
4.   // A half-match was found, sort out the return data.  
5.   String text1_a = hm[0];  
6.   String text1_b = hm[1];  
7.   String text2_a = hm[2];  
8.   String text2_b = hm[3];  
9.   String mid_common = hm[4];  
10.   // Send both pairs off for separate processing.  
11.   LinkedList<Diff> diffs_a = diff_main(text1_a, text2_a);  
12.   LinkedList<Diff> diffs_b = diff_main(text1_b, text2_b);  
13.   // Merge the results.  
14.   diffs = diffs_a;  
15.   diffs.add(new Diff(Operation.EQUAL, mid_common));  
16.   diffs.addAll(diffs_b);  
17.   return diffs;  
18. }  
19.   
20. protected String[] diff_halfMatch(String text1, String text2) {  
21.   // Do the two texts share a substring which is at least half the length of the  
22.   // longer text?  
23.   String longtext = text1.length() > text2.length() ? text1 : text2;  
24.   String shorttext = text1.length() > text2.length() ? text2 : text1;  
25.   if (longtext.length() < 10 || shorttext.length() < 1) {  
26.     return null;  // Pointless.  
27.   }  
28.   
29.   // First check if the second quarter is the seed for a half-match.  
30.   String[] hm1 = diff_halfMatchI(longtext, shorttext,  
31.                                  (longtext.length() + 3) / 4);  
32.   // Check again based on the third quarter.  
33.   String[] hm2 = diff_halfMatchI(longtext, shorttext,  
34.                                  (longtext.length() + 1) / 2);  
35.   String[] hm;  
36.   if (hm1 == null && hm2 == null) {  
37.     return null;  
38.   } else if (hm2 == null) {  
39.     hm = hm1;  
40.   } else if (hm1 == null) {  
41.     hm = hm2;  
42.   } else {  
43.     // Both matched.  Select the longest.  
44.     hm = hm1[4].length() > hm2[4].length() ? hm1 : hm2;  
45.   }  
46.   
47.   // A half-match was found, sort out the return data.  
48.   if (text1.length() > text2.length()) {  
49.     return hm;  
50.     //return new String[]{hm[0], hm[1], hm[2], hm[3], hm[4]};  
51.   } else {  
52.     return new String[]{hm[2], hm[3], hm[0], hm[1], hm[4]};  
53.   }  
54. }  
55.   
56. private String[] diff_halfMatchI(String longtext, String shorttext, int i) {  
57.   // Start with a 1/4 length substring at position i as a seed.  
58.   String seed = longtext.substring(i, i + longtext.length() / 4);  
59.   int j = -1;  
60.   String best_common = "";  
61.   String best_longtext_a = "", best_longtext_b = "";  
62.   String best_shorttext_a = "", best_shorttext_b = "";  
63.   while ((j = shorttext.indexOf(seed, j + 1)) != -1) {  
64.     int prefixLength = diff_commonPrefix(longtext.substring(i),  
65.                                          shorttext.substring(j));  
66.     int suffixLength = diff_commonSuffix(longtext.substring(0, i),  
67.                                          shorttext.substring(0, j));  
68.     if (best_common.length() < suffixLength + prefixLength) {  
69.       best_common = shorttext.substring(j - suffixLength, j)  
70.           + shorttext.substring(j, j + prefixLength);  
71.       best_longtext_a = longtext.substring(0, i - suffixLength);  
72.       best_longtext_b = longtext.substring(i + prefixLength);  
73.       best_shorttext_a = shorttext.substring(0, j - suffixLength);  
74.       best_shorttext_b = shorttext.substring(j + prefixLength);  
75.     }  
76.   }  
77.   if (best_common.length() >= longtext.length() / 2) {  
78.     return new String[]{best_longtext_a, best_longtext_b,  
79.                         best_shorttext_a, best_shorttext_b, best_common};  
80.   } else {  
81.     return null;  
82.   }  
83. }

Python Code

1. # Check to see if the problem can be split in two.  
2. hm = diff_halfMatch(text1, text2)  
3. if hm:  
4.   # A half-match was found, sort out the return data.  
5.   (text1_a, text1_b, text2_a, text2_b, mid_common) = hm  
6.   # Send both pairs off for separate processing.  
7.   diffs_a = diff_main(text1_a, text2_a)  
8.   diffs_b = diff_main(text1_b, text2_b)  
9.   # Merge the results.  
10.   return diffs_a + [(DIFF_EQUAL, mid_common)] + diffs_b  
11.   
12. def diff_halfMatch(text1, text2):  
13.   # Do the two texts share a substring which is at least half the length of the  
14.   # longer text?  
15.   if len(text1) > len(text2):  
16.     (longtext, shorttext) = (text1, text2)  
17.   else:  
18.     (shorttext, longtext) = (text1, text2)  
19.   if len(longtext) < 10 or len(shorttext) < 1:  
20.     return None  # Pointless.  
21.   
22.   def diff_halfMatchI(longtext, shorttext, i):  
23.     seed = longtext[i:i + len(longtext) / 4]  
24.     best_common = ''  
25.     j = shorttext.find(seed)  
26.     while j != -1:  
27.       prefixLength = diff_commonPrefix(longtext[i:], shorttext[j:])  
28.       suffixLength = diff_commonSuffix(longtext[:i], shorttext[:j])  
29.       # print "%s|%s+%s|%s vs. %s|%s+%s|%s" %  
30.       #     (my_suffix[0], my_suffix[2], my_prefix[2], my_prefix[0],  
31.       #     my_suffix[1], my_suffix[2], my_prefix[2], my_prefix[1])  
32.       if len(best_common) < suffixLength + prefixLength:  
33.         best_common = (shorttext[j - suffixLength:j] +  
34.             shorttext[j:j + prefixLength])  
35.         best_longtext_a = longtext[:i - suffixLength]  
36.         best_longtext_b = longtext[i + prefixLength:]  
37.         best_shorttext_a = shorttext[:j - suffixLength]  
38.         best_shorttext_b = shorttext[j + prefixLength:]  
39.       j = shorttext.find(seed, j + 1)  
40.   
41.     if len(best_common) >= len(longtext) / 2:  
42.       return (best_longtext_a, best_longtext_b,  
43.               best_shorttext_a, best_shorttext_b, best_common)  
44.     else:  
45.       return None  
46.   
47.   # First check if the second quarter is the seed for a half-match.  
48.   hm1 = diff_halfMatchI(longtext, shorttext, (len(longtext) + 3) / 4)  
49.   # Check again based on the third quarter.  
50.   hm2 = diff_halfMatchI(longtext, shorttext, (len(longtext) + 1) / 2)  
51.   if not hm1 and not hm2:  
52.     return None  
53.   elif not hm2:  
54.     hm = hm1  
55.   elif not hm1:  
56.     hm = hm2  
57.   else:  
58.     # Both matched.  Select the longest.  
59.     if len(hm1[4]) > len(hm2[4]):  
60.       hm = hm1  
61.     else:  
62.       hm = hm2  
63.   
64.   # A half-match was found, sort out the return data.  
65.   if len(text1) > len(text2):  
66.     (text1_a, text1_b, text2_a, text2_b, mid_common) = hm  
67.   else:  
68.     (text2_a, text2_b, text1_a, text1_b, mid_common) = hm  
69.   return (text1_a, text1_b, text2_a, text2_b, mid_common)

함수 'diff_commonPrefix'와 'diff_commonSuffix'는 이전의 예제 코드를 참조하기 바란다.

---

2. 차이 비교 알고리즘들

선형 처리 최적화가 완료되면, 남은 문자열은 차이 비교 알고리즘으로로 비교된다. 막무가내(brute force) 기술은 O(mn)의 시간이 걸릴 것이다. 여기에서 m, n은 각각 입력 질의 문자열의 길이이다. 이것은 명백히 문자열의 길이가 임의로 변하는 실제 응용 프로그램에서 확장 불가능하다. O(m+n)에 근접하는 나은 알고리즘에 대한 많은 연구가 수행되어져 왔다. 하지만, 이 알고리즘들은 서로 교환이 불가능하다. 속도 이상의으로 중요한다양한 조건들이 있다.

2.1 입력

입력 문자열들을 비교하기 위한 세가지 공통 모드가 있다.

Text 1: The cat in the hat.

Text 2: The bird in the hand.

Char diff: The catbird in the hatnd.

Word diff: The catbird in the hathand.

Line diff: The cat in the hat.The bird in the hand.

개별적인 문자들을 비교하는 것은 가장 정밀한 수준의 차이점을 생성하지만, 토큰의 갯수가 많은 까닭에 실행하는데 가장 오랜 시간이 걸리게 된다. 단어의 경계(공백)나 선 구분자(엔터 기호)들을 비교하는 것이 더 빠르고, 더 적은 편집들을 생성한다. 하지만, 이 경우에는 편집의 전체 길이가 길어지게 된다. 요구되는 차이점의 수준은 응용에 따라서 달라지게 된다. 예를 들어, 소스 코드의 비교와 같은 경우에는 일반적으로 선과 선 사이의 차이점에 기반을 두고, 반면 영어 문서의 비교는 단어와 단어 사이의 비교, 이진 데이터나 DNA 시퀀스는 일반적으로 문자와 문자 사이의 차이점에 기반을 둔다.

이론적으로 어떠한 차이점 비교 알고리즘은 그것이 문자 단위로 쪼개지든, 단어나 선으로 쪼개지든 어떠한 입력에 대해서도 처리할 수 있다. 하지만, 몇몇 차이 비교 알고리즘들은 문자와 같이 작은 토큰을 처리하는데 훨씬 더 효율적이고, 다른 알고리즘은 선과 같이 큰 토큰들을 다루는데 더 효율적이다. 그 이유는 무한대의 가능한 선들이 있고, 한 주어진 문자열에서 나타나지 않은 문자가 다른 주어진 문자열에서 나타나면 자동적으로 삽입이나 삭제로 알려지기 때문이다. 반면, 문자들을(a-z, A-Z, 0-9, 그리고 몇몇 구두점들) 처리하는데 오직 80개의 토큰만이 있거나 매우 중요한 토큰들만이 있을 수 있다. 이 말은 중요한 문자열들에는 모든 문자들이 있는 것이 아니라 자주 나타나는 문자가 있다는 뜻이다. 차이점 알고리즘은 이러한 통계적 차이점들을 입력 문자열에서 사용할 수 있고, 더 효율적인 전략을 수립할 수 있다. 선과 선 사이의 차이점을 비교하는데 특별히 고안된 한 알고리즘이 J. 헌트와 M. 맥로이(J. Hunt, M. Mcllroy)의 1976년도 논문에 소개되어 있다: An Algorithm for Differential File Comparison(http://www.cs.dartmouth.edu/~doug/diff.ps).

고려해야하는 다른 요인은 유요한 함수의 가용성이다. 대부분의 컴퓨터 언어들은 배열 처리 기능과 비교되는 뛰어난 문자열 처리 기능을 가지고 있다(정규 표현식과 같은). 더 강력한 이들 기능들은 문자 기반의 차이점 비교 알고리즘을 쉽게 프로그래밍 할 수 있도록 해준다. 반면에, 많은 프로그래밍 언어에서 유니 코드 지원의 등장은 문자열들이 65,536의 알파벳 크기까지 포함할 수 있다는 뜻이다. 이것은 단어 또는 선들이 단일 문자로 해싱될 수 있고 그래서 차이점 비교 알고리즘이 배열 대신에 문자열들을 사용할 수 있음을 나타낸다. 이 관점을 가지고, 킹 제임스 성경은 30,833의 유일한 선들과 28,880의 유일한 '단어들'(공백으로 쪼개졌고, 선행 또는 후행 구두점에 의해서 구분된 것은 아님)을 가지고 있다.

2.2 출력

전통적인 차이점 발견 알고리즘은 첫째로 주어진 문자열이 두번째 문자열을 생성할 때 삽입과 삭제의 리스트를 생성한다. 이것에 대한 확장은 '이동' 연산자의 추가이다.

Text 1: The black cat in the hat?

Text 2: The cat in the black hat!

Ins & Del: The black cat in the black hat?!

...& Move: The ^cat in the black hat?!

큰 블록의 문자열이 한 지점에서 다른 지점으로 옮겨질 때, 단순히 삭제나 삽입으로 표시하는 것보다는 이것을 이동으로써 표시하는 것이 좀 더 합리적이다.'이동' 연산자를 사용하는 알고리즘은 P. 헥켈(P. Heckel)의 1978년도 논문에 설명되어 있다: A technique for isolating differences between files(http://portal.acm.org/citation.cfm?doid=359460.359467). 

완전히 다른 차이점 비교 접근법은 '복사'와 '삽입'을 연산자들로 사용하는 것이다.

Text 1: The black cat in the hat?

Text 2: The black hat on the black cat!

Copy & Ins: The black hat on the black cat!

이 접근법은 두번째 문자열을 생성하기 위해 복사되고 붙여지는 첫번째 문자열에서의 조각들을 사용한다. 이것은 임의의 노트를 작성하기 위해서 신문으로부터 단어들을 잘라내는 것과 유사하다. 다른 점이라면, 잘라진 단어들이 그대로 복사되어서 여러번 사용된다는 점이다. 완전히 새로운 문자열은 삽입된 구절이다. 복사/삽입 차이점들은 일반적으로 인간이 읽지 못하는 형태로 저장된다. 하지만, 이들은 차이점 압축 응용에서 삽입/삭제 차이점들에 비해 처리되는 것이 엄청나게 빠르기 때문에 그들이 훨씬 더 나은 선택이 되게 한다. '복사'와 '삽입' 연산자들을 사용하는 알고리즘은 J. 맥도날드(J. MacDonald)의 2000년도 논문에 설명되어 있다: File System Support for Delta Compression(http://www.xmailserver.org/xdfs.pdf).

2.3. 정확도

차이점 비교 알고리즘은 결코 잘못된 출력을 내지 않았어야 했다. 잘못된 출력이란, 한 주어진 문자열에서 다른 주어진 문자열로의 적합한 차이점 경로를 설명하지 않는 것을 말한다. 하지만, 몇몇 알고리즘들은 아마 속도의 증진을 위해서 부 최적의 결과를 출력할 것이다. 예를 들어, 헥켈의 알고리즘(1978)은 빠르지만, 만약 입력 문자열에 반복되는 문자열이 있을 경우 헷갈려 한다.

Text 1:  A X X X X B

Text 2:  C X X X X D

Optimal: AC X X X X BD

Heckel:  A X X X X BC X X X X D

속도를 위해서 정확도를 희생시키는 다른 예는 전체 문자열을 선을 기반으로 처리한 후에 각 변형된 선들을 재처리할 때는 문자 기반으로 처리하는 알고리즘이 있다. 이 다중 처리 접근법의 문제는 선을 기반으로 차이점을 찾을 때 종종 두 선들 사이의 잘못된 공통점을 발견한다는 점이다. 비어있는 선은 이것의 주요 원인이며 이것은 공백이 서로 상관 없는 문자열들에서 나타날 수 있기 때문이다. 이 부정확한 공통성은 편집 블록들을 임의로 쪼개는데 일조하고, 문자 기반의 처리 단계 동안에 공통 문자열들이 정상적으로 발견되는 것을 방해한다. 이것에 대한 해결책은 선 기반의 차이점 비교 단계를 통과하고 문자 기반의 차이점 비교를 수행하기 전에 의미론적인 정리 알고리즘(아래 3.2 절에 설명되어 있음)을 동작시키는 것이다. 긴 문서에 다수의 편집들이 관련되어 있는 경우, 고차원의 차이점 처리 후에 저차원의 차이점 처리를 수행하는 것은 속도와 메모리 요구 사항에서 상당한 성능 향상을 가져온다. 하지만, 결과로 나타나는 차이점 경로가 가장 짧은 것이 아닐 가능성이라는 위험이 남아 있다.

논쟁이 있지만, 최고의 일반 목적의 차이점 비교 알고리즘은 E. 마이어스(E. Myers)의 1986년 논문에 설명되어 있다: An O(ND) Difference Algorithm and Its Variations(http://www.xmailserver.org/diff2.pdf). 하나의 제안된 최적화는 양쪽 끝에서 동시에 차이점을 처리하고 중간에서 만나는 것이다. 대부분의 경우 성능은 50%까지 향상된다. 하지만, 여기에는 두 차이점들이 만나지 않을 경우가 발생한다.

마이어스씨가 말하길, "최적의 D-경로의 중간 스네이크(snake)를 찾는 단계는 두 V 벡터들을 위해서 총 O(D)의 동작 공간을 요구한다." 불행하게도 이것은 언제나 중간 스네이크가 존재한다는 보증되지 않은 가정에 기반을 두고 있다. 만약, 구현이 이런 경우를 예측하지 않는다면, 결과는 아무런 공통성도 없는 차이점, 무한 루프, 혹은 충돌 중 한 가지의 결과를 낳게 된다.

이 문제에는 두가지 해결책이 있다. 하나는 하위 경로에 의해 방문된 모든 지점과 그 지점의 D-값에 대한 값을 저장하기 위해서 해시를 사용하는 것이다. 이것은 한 경로들이 같은 스네이크에서 만나는 경우가 없이 연결을 할 수 있도록 해준다. 운나쁘게도 이것은 동작 공간 소모를 으로 늘린다. 그것은 또한 경로가 동시적으로 서로에게 다가가기 때문에 성능의 하락을 야기한다. 다른 해결책은 역행 경로의 길이가 길이가 D의 절반을 넘어갈 때 역행 경로를 종결시키거나 무시한 다음에 순행 경로를 반대편 코너로 향하게 몰아가는 것이다. 이것은 O(ND)의 성능 하략을 야기한다. 이 두 해결책들은 한 기술이 특정한 경우에는 성능을 하락시키지만, 일반적인 경우에 알고리즘의 성능을 향상시키는 예를 보인다.

마이어스씨는 또한 "알고리즘은 또한 가장 작은 D가 반대 방향 오버랩에 있는 D-경로에 도달하는 즉시 멈춘다."라고 언급했다. 하지만, 이것은 첫번째 오버랩이 가장 짧은 경로일 것이라는 불확실한 가정에 기반을 두고 있다. 이것은 언제나 발생하는 경우가 아니다:

이 예에서 경로는 (4, 4)에서 만나지만, 이 경로는 조합된 편집거리 9을 가지며, 대조적으로, 최상단 선분을 따라 (0,0)으로 접근해 가는 불완전한 경로는 결국 편집거리 6을 가지게 된다. 이것은 XABXCYXABC와 XAXCXABCY를 구분하는 것을 표현한다. 그 최종 목적지에 아직 도달하지 않은 편집 거리를 예측하는 문제에 대한 일반적인 해결책은 아직 나타나지 않았다. 그 결과, 차이점을 양 끝단에서부터 처리해가는 것은 속도를 두 배 증진시키지만, 정확도를 낮춘다.

---

3. 사후 처리 제거 방식

완전한 차이점 비교 알고리즘은 한 문자열에서 다른 문자열로 변환하기 위해서 요구되는 최소의 횟수를 가진 편집들만 표시할 것이다. 하지만, 종종 그 결과가 너무나도 완벽해서 문제가 될 수 있다:

Text 1: I am the very model of a modern major general.

Text 2: `Twas brillig, and the slithy toves did gyre and gimble in the wabe.

Diff:   I`Twas brillig, amnd the verslithy mtodvels ofdid a modgyrern majornd gimble in ther walbe.

새로운 차이점 결과를 다루는 첫번째 단계는 순서를 바꾸고 구절들의 조합처럼 합병시키는 것이다. 위의 에제에서 그러한 최적화가 가능하다.

Old:   I`Twas brillig, amnd ...

New: I`Twas brillig, amnd ...

이 두 차이점 결과들은 그 출력 결과가 동일하지만, 두번째 결과의 경우 동일한 편집의 위치(공백)를 바꿈으로써 두 연산이 하나의 연산으로 합쳐졌다.

JavaScript Code

1. function diff_cleanupMerge(diffs) {  
2.   // Reorder and merge like edit sections.  Merge equalities.  
3.   // Any edit section can move as long as it does not cross an equality.  
4.   diffs.push([DIFF_EQUAL, '']);  // Add a dummy entry at the end.  
5.   var pointer = 0;  
6.   var count_delete = 0;  
7.   var count_insert = 0;  
8.   var text_delete = '';  
9.   var text_insert = '';  
10.   var commonlength;  
11.   while (pointer < diffs.length) {  
12.     switch (diffs[pointer][0]) {  
13.       case DIFF_INSERT:  
14.         count_insert++;  
15.         text_insert += diffs[pointer][1];  
16.         pointer++;  
17.         break;  
18.       case DIFF_DELETE:  
19.         count_delete++;  
20.         text_delete += diffs[pointer][1];  
21.         pointer++;  
22.         break;  
23.       case DIFF_EQUAL:  
24.         // Upon reaching an equality, check for prior redundancies.  
25.         if (count_delete !== 0 || count_insert !== 0) {  
26.           if (count_delete !== 0 && count_insert !== 0) {  
27.             // Factor out any common prefixies.  
28.             commonlength = diff_commonPrefix(text_insert, text_delete);  
29.             if (commonlength !== 0) {  
30.               if ((pointer - count_delete - count_insert) > 0 &&  
31.                   diffs[pointer - count_delete - count_insert - 1][0] ==  
32.                   DIFF_EQUAL) {  
33.                 diffs[pointer - count_delete - count_insert - 1][1] +=  
34.                     text_insert.substring(0, commonlength);  
35.               } else {  
36.                 diffs.splice(0, 0, [DIFF_EQUAL,  
37.                     text_insert.substring(0, commonlength)]);  
38.                 pointer++;  
39.               }  
40.               text_insert = text_insert.substring(commonlength);  
41.               text_delete = text_delete.substring(commonlength);  
42.             }  
43.             // Factor out any common suffixies.  
44.             commonlength = diff_commonSuffix(text_insert, text_delete);  
45.             if (commonlength !== 0) {  
46.               diffs[pointer][1] = text_insert.substring(text_insert.length -  
47.                   commonlength) + diffs[pointer][1];  
48.               text_insert = text_insert.substring(0, text_insert.length -  
49.                   commonlength);  
50.               text_delete = text_delete.substring(0, text_delete.length -  
51.                   commonlength);  
52.             }  
53.           }  
54.           // Delete the offending records and add the merged ones.  
55.           if (count_delete === 0) {  
56.             diffs.splice(pointer - count_delete - count_insert,  
57.                 count_delete + count_insert, [DIFF_INSERT, text_insert]);  
58.           } else if (count_insert === 0) {  
59.             diffs.splice(pointer - count_delete - count_insert,  
60.                 count_delete + count_insert, [DIFF_DELETE, text_delete]);  
61.           } else {  
62.             diffs.splice(pointer - count_delete - count_insert,  
63.                 count_delete + count_insert, [DIFF_DELETE, text_delete],  
64.                 [DIFF_INSERT, text_insert]);  
65.           }  
66.           pointer = pointer - count_delete - count_insert +  
67.                     (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;  
68.         } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {  
69.           // Merge this equality with the previous one.  
70.           diffs[pointer - 1][1] += diffs[pointer][1];  
71.           diffs.splice(pointer, 1);  
72.         } else {  
73.           pointer++;  
74.         }  
75.         count_insert = 0;  
76.         count_delete = 0;  
77.         text_delete = '';  
78.         text_insert = '';  
79.         break;  
80.     }  
81.   }  
82.   if (diffs[diffs.length - 1][1] === '') {  
83.     diffs.pop();  // Remove the dummy entry at the end.  
84.   }  
85.   
86.   // Second pass: look for single edits surrounded on both sides by equalities  
87.   // which can be shifted sideways to eliminate an equality.  
88.   // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC  
89.   var changes = false;  
90.   pointer = 1;  
91.   // Intentionally ignore the first and last element (don't need checking).  
92.   while (pointer < diffs.length - 1) {  
93.     if (diffs[pointer - 1][0] == DIFF_EQUAL &&  
94.         diffs[pointer + 1][0] == DIFF_EQUAL) {  
95.       // This is a single edit surrounded by equalities.  
96.       if (diffs[pointer][1].substring(diffs[pointer][1].length -  
97.           diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) {  
98.         // Shift the edit over the previous equality.  
99.         diffs[pointer][1] = diffs[pointer - 1][1] +  
100.             diffs[pointer][1].substring(0, diffs[pointer][1].length -  
101.                                         diffs[pointer - 1][1].length);  
102.         diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];  
103.         diffs.splice(pointer - 1, 1);  
104.         changes = true;  
105.       } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==  
106.           diffs[pointer + 1][1]) {  
107.         // Shift the edit over the next equality.  
108.         diffs[pointer - 1][1] += diffs[pointer + 1][1];  
109.         diffs[pointer][1] =  
110.             diffs[pointer][1].substring(diffs[pointer + 1][1].length) +  
111.             diffs[pointer + 1][1];  
112.         diffs.splice(pointer + 1, 1);  
113.         changes = true;  
114.       }  
115.     }  
116.     pointer++;  
117.   }  
118.   // If shifts were made, the diff needs reordering and another shift sweep.  
119.   if (changes) {  
120.     diff_cleanupMerge(diffs);  
121.   }  
122. }

Java Code

1. public void diff_cleanupMerge(LinkedList<Diff> diffs) {  
2.   // Reorder and merge like edit sections.  Merge equalities.  
3.   // Any edit section can move as long as it does not cross an equality.  
4.   diffs.add(new Diff(Operation.EQUAL, ""));  // Add a dummy entry at the end.  
5.   ListIterator<Diff> pointer = diffs.listIterator();  
6.   int count_delete = 0;  
7.   int count_insert = 0;  
8.   String text_delete = "";  
9.   String text_insert = "";  
10.   Diff thisDiff = pointer.next();  
11.   Diff prevEqual = null;  
12.   int commonlength;  
13.   while (thisDiff != null) {  
14.     switch (thisDiff.operation) {  
15.     case INSERT:  
16.       count_insert++;  
17.       text_insert += thisDiff.text;  
18.       prevEqual = null;  
19.       break;  
20.     case DELETE:  
21.       count_delete++;  
22.       text_delete += thisDiff.text;  
23.       prevEqual = null;  
24.       break;  
25.     case EQUAL:  
26.       if (count_delete != 0 || count_insert != 0) {  
27.         // Delete the offending records.  
28.         pointer.previous();  // Reverse direction.  
29.         while (count_delete-- > 0) {  
30.           pointer.previous();  
31.           pointer.remove();  
32.         }  
33.         while (count_insert-- > 0) {  
34.           pointer.previous();  
35.           pointer.remove();  
36.         }  
37.         if (count_delete != 0 && count_insert != 0) {  
38.           // Factor out any common prefixies.  
39.           commonlength = diff_commonPrefix(text_insert, text_delete);  
40.           if (commonlength != 0) {  
41.             if (pointer.hasPrevious()) {  
42.               thisDiff = pointer.previous();  
43.               assert thisDiff.operation == Operation.EQUAL  
44.                      : "Previous diff should have been an equality.";  
45.               thisDiff.text += text_insert.substring(0, commonlength);  
46.               pointer.next();  
47.             } else {  
48.               pointer.add(new Diff(Operation.EQUAL,  
49.                   text_insert.substring(0, commonlength)));  
50.             }  
51.             text_insert = text_insert.substring(commonlength);  
52.             text_delete = text_delete.substring(commonlength);  
53.           }  
54.           // Factor out any common suffixies.  
55.           commonlength = diff_commonSuffix(text_insert, text_delete);  
56.           if (commonlength != 0) {  
57.             thisDiff = pointer.next();  
58.             thisDiff.text = text_insert.substring(text_insert.length()  
59.                 - commonlength) + thisDiff.text;  
60.             text_insert = text_insert.substring(0, text_insert.length()  
61.                 - commonlength);  
62.             text_delete = text_delete.substring(0, text_delete.length()  
63.                 - commonlength);  
64.             pointer.previous();  
65.           }  
66.         }  
67.         // Insert the merged records.  
68.         if (text_delete.length() != 0) {  
69.           pointer.add(new Diff(Operation.DELETE, text_delete));  
70.         }  
71.         if (text_insert.length() != 0) {  
72.           pointer.add(new Diff(Operation.INSERT, text_insert));  
73.         }  
74.         // Step forward to the equality.  
75.         thisDiff = pointer.hasNext() ? pointer.next() : null;  
76.       } else if (prevEqual != null) {  
77.         // Merge this equality with the previous one.  
78.         prevEqual.text += thisDiff.text;  
79.         pointer.remove();  
80.         thisDiff = pointer.previous();  
81.         pointer.next();  // Forward direction  
82.       }  
83.       count_insert = 0;  
84.       count_delete = 0;  
85.       text_delete = "";  
86.       text_insert = "";  
87.       prevEqual = thisDiff;  
88.       break;  
89.     }  
90.     thisDiff = pointer.hasNext() ? pointer.next() : null;  
91.   }  
92.   // System.out.println(diff);  
93.   if (diffs.getLast().text.length() == 0) {  
94.     diffs.removeLast();  // Remove the dummy entry at the end.  
95.   }  
96.   
97.   /* 
98.    * Second pass: look for single edits surrounded on both sides by equalities 
99.    * which can be shifted sideways to eliminate an equality. 
100.    * e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC 
101.    */  
102.   boolean changes = false;  
103.   // Create a new iterator at the start.  
104.   // (As opposed to walking the current one back.)  
105.   pointer = diffs.listIterator();  
106.   Diff prevDiff = pointer.hasNext() ? pointer.next() : null;  
107.   thisDiff = pointer.hasNext() ? pointer.next() : null;  
108.   Diff nextDiff = pointer.hasNext() ? pointer.next() : null;  
109.   // Intentionally ignore the first and last element (don't need checking).  
110.   while (nextDiff != null) {  
111.     if (prevDiff.operation == Operation.EQUAL &&  
112.         nextDiff.operation == Operation.EQUAL) {  
113.       // This is a single edit surrounded by equalities.  
114.       if (thisDiff.text.endsWith(prevDiff.text)) {  
115.         // Shift the edit over the previous equality.  
116.         thisDiff.text = prevDiff.text  
117.             + thisDiff.text.substring(0, thisDiff.text.length()  
118.                                          - prevDiff.text.length());  
119.         nextDiff.text = prevDiff.text + nextDiff.text;  
120.         pointer.previous(); // Walk past nextDiff.  
121.         pointer.previous(); // Walk past thisDiff.  
122.         pointer.previous(); // Walk past prevDiff.  
123.         pointer.remove(); // Delete prevDiff.  
124.         pointer.next(); // Walk past thisDiff.  
125.         thisDiff = pointer.next(); // Walk past nextDiff.  
126.         nextDiff = pointer.hasNext() ? pointer.next() : null;  
127.         changes = true;  
128.       } else if (thisDiff.text.startsWith(nextDiff.text)) {  
129.         // Shift the edit over the next equality.  
130.         prevDiff.text += nextDiff.text;  
131.         thisDiff.text = thisDiff.text.substring(nextDiff.text.length()) +  
132.             nextDiff.text;  
133.         pointer.remove(); // Delete nextDiff.  
134.         nextDiff = pointer.hasNext() ? pointer.next() : null;  
135.         changes = true;  
136.       }  
137.     }  
138.     prevDiff = thisDiff;  
139.     thisDiff = nextDiff;  
140.     nextDiff = pointer.hasNext() ? pointer.next() : null;  
141.   }  
142.   // If shifts were made, the diff needs reordering and another shift sweep.  
143.   if (changes) {  
144.     diff_cleanupMerge(diffs);  
145.   }  
146. }

Python Code

1. def diff_cleanupMerge(diffs):  
2.   # Reorder and merge like edit sections.  Merge equalities.  
3.   # Any edit section can move as long as it does not cross an equality.  
4.   diffs.append((DIFF_EQUAL, ''))  # Add a dummy entry at the end.  
5.   pointer = 0  
6.   count_delete = 0  
7.   count_insert = 0  
8.   text_delete = ''  
9.   text_insert = ''  
10.   while pointer < len(diffs):  
11.     if diffs[pointer][0] == DIFF_INSERT:  
12.       count_insert += 1  
13.       text_insert += diffs[pointer][1]  
14.       pointer += 1  
15.     elif diffs[pointer][0] == DIFF_DELETE:  
16.       count_delete += 1  
17.       text_delete += diffs[pointer][1]  
18.       pointer += 1  
19.     elif diffs[pointer][0] == DIFF_EQUAL:  
20.       # Upon reaching an equality, check for prior redundancies.  
21.       if count_delete != 0 or count_insert != 0:  
22.         if count_delete != 0 and count_insert != 0:  
23.           # Factor out any common prefixies.  
24.           commonlength = diff_commonPrefix(text_insert, text_delete)  
25.           if commonlength != 0:  
26.             x = pointer - count_delete - count_insert - 1  
27.             if x >= 0 and diffs[x][0] == DIFF_EQUAL:  
28.               diffs[x] = (diffs[x][0], diffs[x][1] +  
29.                           text_insert[:commonlength])  
30.             else:  
31.               diffs.insert(0, (DIFF_EQUAL, text_insert[:commonlength]))  
32.               pointer += 1  
33.             text_insert = text_insert[commonlength:]  
34.             text_delete = text_delete[commonlength:]  
35.           # Factor out any common suffixies.  
36.           commonlength = diff_commonSuffix(text_insert, text_delete)  
37.           if commonlength != 0:  
38.             diffs[pointer] = (diffs[pointer][0], text_insert[-commonlength:] +  
39.                 diffs[pointer][1])  
40.             text_insert = text_insert[:-commonlength]  
41.             text_delete = text_delete[:-commonlength]  
42.         # Delete the offending records and add the merged ones.  
43.         if count_delete == 0:  
44.           diffs[pointer - count_insert : pointer] = [  
45.               (DIFF_INSERT, text_insert)]  
46.         elif count_insert == 0:  
47.           diffs[pointer - count_delete : pointer] = [  
48.               (DIFF_DELETE, text_delete)]  
49.         else:  
50.           diffs[pointer - count_delete - count_insert : pointer] = [  
51.               (DIFF_DELETE, text_delete),  
52.               (DIFF_INSERT, text_insert)]  
53.         pointer = pointer - count_delete - count_insert + 1  
54.         if count_delete != 0:  
55.           pointer += 1  
56.         if count_insert != 0:  
57.           pointer += 1  
58.       elif pointer != 0 and diffs[pointer - 1][0] == DIFF_EQUAL:  
59.         # Merge this equality with the previous one.  
60.         diffs[pointer - 1] = (diffs[pointer - 1][0],  
61.                               diffs[pointer - 1][1] + diffs[pointer][1])  
62.         del diffs[pointer]  
63.       else:  
64.         pointer += 1  
65.   
66.       count_insert = 0  
67.       count_delete = 0  
68.       text_delete = ''  
69.       text_insert = ''  
70.   
71.   if diffs[-1][1] == '':  
72.     diffs.pop()  # Remove the dummy entry at the end.  
73.   
74.   # Second pass: look for single edits surrounded on both sides by equalities  
75.   # which can be shifted sideways to eliminate an equality.  
76.   # e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC  
77.   changes = False  
78.   pointer = 1  
79.   # Intentionally ignore the first and last element (don't need checking).  
80.   while pointer < len(diffs) - 1:  
81.     if (diffs[pointer - 1][0] == DIFF_EQUAL and  
82.         diffs[pointer + 1][0] == DIFF_EQUAL):  
83.       # This is a single edit surrounded by equalities.  
84.       if diffs[pointer][1].endswith(diffs[pointer - 1][1]):  
85.         # Shift the edit over the previous equality.  
86.         diffs[pointer] = (diffs[pointer][0],  
87.             diffs[pointer - 1][1] +  
88.             diffs[pointer][1][:-len(diffs[pointer - 1][1])])  
89.         diffs[pointer + 1] = (diffs[pointer + 1][0],  
90.                               diffs[pointer - 1][1] + diffs[pointer + 1][1])  
91.         del diffs[pointer - 1]  
92.         changes = True  
93.       elif diffs[pointer][1].startswith(diffs[pointer + 1][1]):  
94.         # Shift the edit over the next equality.  
95.         diffs[pointer - 1] = (diffs[pointer - 1][0],  
96.                               diffs[pointer - 1][1] + diffs[pointer + 1][1])  
97.         diffs[pointer] = (diffs[pointer][0],  
98.             diffs[pointer][1][len(diffs[pointer + 1][1]):] +  
99.             diffs[pointer + 1][1])  
100.         del diffs[pointer + 1]  
101.         changes = True  
102.     pointer += 1  
103.   
104.   # If shifts were made, the diff needs reordering and another shift sweep.  
105.   if changes:  
106.     diff_cleanupMerge(diffs)

이 경우의 위치를 바꾸는 것은 약간의 도움이 되고, 완전히 안전하지만, 더 큰 문제는 두 개의 전혀 비슷하지 않은 문자여들 사이의 차이점이 종종 '채프(chaff, 원뜻, 왕겨, 쭉정이)'라고 불리는 작은 편집 동일 지역으로 자주 어질러 진다. 위의 예제의 경우 예상되는 결과는 끝에있는 구두점만을 남기고 모든 'Text1'의 글자가 삭제되고, 모든 'Text2'의 문자가 삽입되는 것이다. 하지만 대부분의 알고리즘은 잡동사니 결과들을 보존하려고 할 것이고, 결과적으로 엉망이 되어 버린다.

이 문제는 문자 기반의 차이점 비교에서 매우 두드러진다. 왜냐하면, 작은 알파벳과 숫자를 가진 문자 집합은 반드시 공통성이 나타나기 때문이다. 위의 예제에서의 단어 기반의 차이점 비교의 경우 차이점을 더 두드러지게 나타낼 수 있으나, 아마도 잘못 선별한 " the "와 같은 것이 있을 것이다. 더 긴 문자열들은 더 많은 공유된 단어들을 가지게 된다. 위의 예제의 경우 선 기반 차이점 비교가 가장 이상적일 것이다. 하지만, 심지어 선 기반 차이점 비교 역시 비어있는 선분이라던지 다른 전형적인 선들에 대해 잘못된 선별에 취약하다(가령, 소스 코드에서 "} else {"와 같은 선).

쭉정이 문제는 실제로는 두 다른 문제들 중 하나이다: 효율성 또는 의미론. 이들 각 문제들은 각각 다른 해결책을 요구한다.

3.1. 효율성

만약 차이점의 출력 결과가 컴퓨터의 사용을 위한 것(가령, 델타 압축 기법 또는 패치 표시 프로그램의 입력)이라면, 다음의 응용 또는 저장 방식에 따라서, 각 편집 연산은 그것과 연관된 어느 정도 고정된 계산 오버헤드와 편집하려는 거리에 있는 문자들의 갯수 오버헤드를 를 가지고 있을 것이다. 예를 들어, 50개의 단일 문자 편집들은 단일의 50개 문자를 가진 편집을 처리하는 것보다 더 많은 공간을 차지하거나 다음 응용을 위해서 처리하는 것보다 더 긴 시간이 걸릴 것이다. 트레이드오프가 평가되면, 편집 연산의 계산적 또는 공간적 비용은 동일한 갯수의 문자 변경 비용으로 명시될 수 있을 것이다. 만약, 이 비용이 0이라면, 거기에는 오버헤드가 없는 것이다. 예를 들어서, 만약 이 비용이 10 문자라고 하면, 변경하려는 전체 문자의 개수를 9개까지 증가시키는 것은, 편집 연산을 1번으로 감소시키는 것이 되고, 결과적으로 연산 비용을 낮추게 된다. 그런 까닭에 차이점 비교의 전체 비용은 o * c + n이 된다. 여기에서 o는 편집 연산의 수, c는 문자의 개념에서 각 편집 연산의 상수 비용, 그리고 n은 변경하려고 하는 전체 문자의 수가 된다. 아래 세 가지 예제들은(임의로  c는 4로 설정함) 편집하려는 문자들의 수를 증가시키는 것이 얼마나 편집 연산의 수를 줄이고, 전체 차이점 비교 연산의 비용을 줄이는 지 보인다.

먼저, 존재하는 삽입과 삭제에 의해서 양쪽이 둘러 쌓여진 어떠한 동일성 영역(equality, 변경되지 않은채로 있는 문자열)은 그것이 쪼개었을 때 차이점 비교 연산에서 이득이 되려면 c 문자열 길이보다 짧거나 같아야 한다.

	연산들	문자들	비용
Text1:   ABXYZCD
Text2:   12XYZ34
Diff:       AB12XYZCD34	4 * 4	+ 8	= 24
Split:      AB12XYZXYZCD34	6 * 4	+ 14	= 38
Merge:  ABXYZCD12XYZ34	2 * 4	+ 14	= 22

둘째로, 한쪽은 이미 존재하는 삽입과 삭제에의해 둘러 쌓여지고, 다른쪽은 삽입 혹은 삭제에 의해서 둘러 쌓여진  동일성 영역은 그것이 쪼개었을 때 차이점 비교 연산에서 이득이 되려면 c 문자열의 절반 길이보다 짧거나 같아야 한다.

	연산들	문자들	비용
Text1:   XCD
Text2:   12X34
Diff:       12XCD34	3 * 4	+ 6	= 18
Split:      12XXCD34	5 * 4	+ 8	= 28
Merge:  XCD12X34	2 * 4	+ 8	= 16

이 두가지 조건은 데이터에 대해서 단일 처리단계를 만들고 만약 잘라진 문자열이 그것을 둘러싸고 있는 편집의 종류가 바뀌었다면 이전의 동일성 영역을 재평가 하기 위해서 백트레킹 하는 방법에 의해서 빠르게 계산될 것이다. 다른 처리 단계는 편집 연산들을 재정렬 하고, 하나로 합병시키는 단게이다.

JavaScript Code

1. function diff_cleanupEfficiency(diffs) {  
2.   // Reduce the number of edits by eliminating operationally trivial equalities.  
3.   var changes = false;  
4.   var equalities = [];  // Stack of indices where equalities are found.  
5.   var lastequality = '';  // Always equal to equalities[equalities.length-1][1]  
6.   var pointer = 0;  // Index of current position.  
7.   // Is there an insertion operation before the last equality.  
8.   var pre_ins = false;  
9.   // Is there a deletion operation before the last equality.  
10.   var pre_del = false;  
11.   // Is there an insertion operation after the last equality.  
12.   var post_ins = false;  
13.   // Is there a deletion operation after the last equality.  
14.   var post_del = false;  
15.   while (pointer < diffs.length) {  
16.     if (diffs[pointer][0] == DIFF_EQUAL) {  // equality found  
17.       if (diffs[pointer][1].length < Diff_EditCost &&  
18.           (post_ins || post_del)) {  
19.         // Candidate found.  
20.         equalities.push(pointer);  
21.         pre_ins = post_ins;  
22.         pre_del = post_del;  
23.         lastequality = diffs[pointer][1];  
24.       } else {  
25.         // Not a candidate, and can never become one.  
26.         equalities = [];  
27.         lastequality = '';  
28.       }  
29.       post_ins = post_del = false;  
30.     } else {  // an insertion or deletion  
31.       if (diffs[pointer][0] == DIFF_DELETE) {  
32.         post_del = true;  
33.       } else {  
34.         post_ins = true;  
35.       }  
36.       /* 
37.        * Five types to be split: 
38.        * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del> 
39.        * <ins>A</ins>X<ins>C</ins><del>D</del> 
40.        * <ins>A</ins><del>B</del>X<ins>C</ins> 
41.        * <ins>A</del>X<ins>C</ins><del>D</del> 
42.        * <ins>A</ins><del>B</del>X<del>C</del> 
43.        */  
44.       if (lastequality && ((pre_ins && pre_del && post_ins && post_del) ||  
45.                            ((lastequality.length < Diff_EditCost / 2) &&  
46.                             (pre_ins + pre_del + post_ins + post_del) == 3))) {  
47.         // Duplicate record  
48.         diffs.splice(equalities[equalities.length - 1], 0,  
49.                      [DIFF_DELETE, lastequality]);  
50.         // Change second copy to insert.  
51.         diffs[equalities[equalities.length - 1] + 1][0] = DIFF_INSERT;  
52.         equalities.pop();  // Throw away the equality we just deleted;  
53.         lastequality = '';  
54.         if (pre_ins && pre_del) {  
55.           // No changes made which could affect previous entry, keep going.  
56.           post_ins = post_del = true;  
57.           equalities = [];  
58.         } else {  
59.           equalities.pop();  // Throw away the previous equality;  
60.           pointer = equalities.length ? equalities[equalities.length - 1] : -1;  
61.           post_ins = post_del = false;  
62.         }  
63.         changes = true;  
64.       }  
65.     }  
66.     pointer++;  
67.   }  
68.   
69.   if (changes) {  
70.     diff_cleanupMerge(diffs);  
71.   }  
72. }

Java Code

1. public void diff_cleanupEfficiency(LinkedList<Diff> diffs) {  
2.   // Reduce the number of edits by eliminating operationally trivial  
3.   // equalities.  
4.   if (diffs.isEmpty()) {  
5.     return;  
6.   }  
7.   boolean changes = false;  
8.   Stack<Diff> equalities = new Stack<Diff>();  // Stack of equalities.  
9.   String lastequality = null;  // Always equal to equalities.lastElement().text  
10.   ListIterator<Diff> pointer = diffs.listIterator();  
11.   // Is there an insertion operation before the last equality.  
12.   boolean pre_ins = false;  
13.   // Is there a deletion operation before the last equality.  
14.   boolean pre_del = false;  
15.   // Is there an insertion operation after the last equality.  
16.   boolean post_ins = false;  
17.   // Is there a deletion operation after the last equality.  
18.   boolean post_del = false;  
19.   Diff thisDiff = pointer.next();  
20.   Diff safeDiff = thisDiff;  // The last Diff that is known to be unsplitable.  
21.   while (thisDiff != null) {  
22.     if (thisDiff.operation == Operation.EQUAL) {  
23.       // equality found  
24.       if (thisDiff.text.length() < Diff_EditCost && (post_ins || post_del)) {  
25.         // Candidate found.  
26.         equalities.push(thisDiff);  
27.         pre_ins = post_ins;  
28.         pre_del = post_del;  
29.         lastequality = thisDiff.text;  
30.       } else {  
31.         // Not a candidate, and can never become one.  
32.         equalities.clear();  
33.         lastequality = null;  
34.         safeDiff = thisDiff;  
35.       }  
36.       post_ins = post_del = false;  
37.     } else {  
38.       // an insertion or deletion  
39.       if (thisDiff.operation == Operation.DELETE) {  
40.         post_del = true;  
41.       } else {  
42.         post_ins = true;  
43.       }  
44.       /* 
45.        * Five types to be split: 
46.        * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del> 
47.        * <ins>A</ins>X<ins>C</ins><del>D</del> 
48.        * <ins>A</ins><del>B</del>X<ins>C</ins> 
49.        * <ins>A</del>X<ins>C</ins><del>D</del> 
50.        * <ins>A</ins><del>B</del>X<del>C</del> 
51.        */  
52.       if (lastequality != null  
53.           && ((pre_ins && pre_del && post_ins && post_del)  
54.               || ((lastequality.length() < Diff_EditCost / 2)  
55.                   && ((pre_ins ? 1 : 0) + (pre_del ? 1 : 0)  
56.                       + (post_ins ? 1 : 0) + (post_del ? 1 : 0)) == 3))) {  
57.         // Walk back to offending equality.  
58.         while (thisDiff != equalities.lastElement()) {  
59.           thisDiff = pointer.previous();  
60.         }  
61.         pointer.next();  
62.   
63.         // Replace equality with a delete.  
64.         pointer.set(new Diff(Operation.DELETE, lastequality));  
65.         // Insert a coresponding an insert.  
66.         pointer.add(thisDiff = new Diff(Operation.INSERT, lastequality));  
67.   
68.         equalities.pop();  // Throw away the equality we just deleted.  
69.         lastequality = null;  
70.         if (pre_ins && pre_del) {  
71.           // No changes made which could affect previous entry, keep going.  
72.           post_ins = post_del = true;  
73.           equalities.clear();  
74.           safeDiff = thisDiff;  
75.         } else {  
76.           if (!equalities.empty()) {  
77.             // Throw away the previous equality (it needs to be reevaluated).  
78.             equalities.pop();  
79.           }  
80.           if (equalities.empty()) {  
81.             // There are no previous questionable equalities,  
82.             // walk back to the last known safe diff.  
83.             thisDiff = safeDiff;  
84.           } else {  
85.             // There is an equality we can fall back to.  
86.             thisDiff = equalities.lastElement();  
87.           }  
88.           while (thisDiff != pointer.previous()) {  
89.             // Intentionally empty loop.  
90.           }  
91.           post_ins = post_del = false;  
92.         }  
93.   
94.         changes = true;  
95.       }  
96.     }  
97.     thisDiff = pointer.hasNext() ? pointer.next() : null;  
98.   }  
99.   
100.   if (changes) {  
101.     diff_cleanupMerge(diffs);  
102.   }  
103. }

Python Code

1. def diff_cleanupEfficiency(diffs):  
2.   # Reduce the number of edits by eliminating operationally trivial equalities.  
3.   changes = False  
4.   equalities = []  # Stack of indices where equalities are found.  
5.   lastequality = ''  # Always equal to equalities[len(equalities)-1][1]  
6.   pointer = 0  # Index of current position.  
7.   pre_ins = False  # Is there an insertion operation before the last equality.  
8.   pre_del = False  # Is there a deletion operation before the last equality.  
9.   post_ins = False  # Is there an insertion operation after the last equality.  
10.   post_del = False  # Is there a deletion operation after the last equality.  
11.   while pointer < len(diffs):  
12.     if diffs[pointer][0] == DIFF_EQUAL:  # equality found  
13.       if (len(diffs[pointer][1]) < Diff_EditCost and  
14.           (post_ins or post_del)):  
15.         # Candidate found.  
16.         equalities.append(pointer)  
17.         pre_ins = post_ins  
18.         pre_del = post_del  
19.         lastequality = diffs[pointer][1]  
20.       else:  
21.         # Not a candidate, and can never become one.  
22.         equalities = []  
23.         lastequality = ''  
24.   
25.       post_ins = post_del = False  
26.     else:  # an insertion or deletion  
27.       if diffs[pointer][0] == DIFF_DELETE:  
28.         post_del = True  
29.       else:  
30.         post_ins = True  
31.           
32.       # Five types to be split:  
33.       # <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>  
34.       # <ins>A</ins>X<ins>C</ins><del>D</del>  
35.       # <ins>A</ins><del>B</del>X<ins>C</ins>  
36.       # <ins>A</del>X<ins>C</ins><del>D</del>  
37.       # <ins>A</ins><del>B</del>X<del>C</del>  
38.         
39.       if lastequality and ((pre_ins and pre_del and post_ins and post_del) or  
40.                            ((len(lastequality) < Diff_EditCost / 2) and  
41.                             (pre_ins + pre_del + post_ins + post_del) == 3)):  
42.         # Duplicate record  
43.         diffs.insert(equalities[len(equalities) - 1],  
44.                      (DIFF_DELETE, lastequality))  
45.         # Change second copy to insert.  
46.         diffs[equalities[len(equalities) - 1] + 1] = (DIFF_INSERT,  
47.             diffs[equalities[len(equalities) - 1] + 1][1])  
48.         equalities.pop()  # Throw away the equality we just deleted  
49.         lastequality = ''  
50.         if pre_ins and pre_del:  
51.           # No changes made which could affect previous entry, keep going.  
52.           post_ins = post_del = True  
53.           equalities = []  
54.         else:  
55.           if len(equalities):  
56.             equalities.pop()  # Throw away the previous equality  
57.           if len(equalities):  
58.             pointer = equalities[len(equalities) - 1]  
59.           else:  
60.             pointer = -1  
61.           post_ins = post_del = False  
62.         changes = True  
63.     pointer += 1  
64.   
65.   if changes:  
66.     diff_cleanupMerge(diffs)  

'diff_cleanupMerge' 함수에 대해서는 이전의 코드를 살펴보기 바란다.

이것은 이 문제에 대한 좋은 출발점이지만, 세번째 종류의 상황을 발견하지 못하기 때문에 완전한 해결책은 아니다.

	연산들	문자들	비용
Text1:   ABCD
Text2:   A1B2C3D4
Diff:       A1B2C3D4	4 * 4	+ 4	= 20
Split:      A1BB2CC3DD4	10 * 4	+ 10	= 50
Merge:  ABCD1B2C3D4	2 * 4	+ 10	= 18

이 경우 혹은 이와 유사한 경우, 각 쪼개진 문자열들이 전체 비용을 오히려 더 높이지만 쪼개진 문자열들이 합쳐질 때, 낮은 전체 비용을 야기한다. 이 형태의 최적화를 계산하는 것은 선택된 차이 비교 영역에서 연산으로 나타나기 때문에(첫번째 두 경우의 O(n)과는 대조적으로), 그들 스스로 비용을 줄이기 보다 더 비용을 높이게 된다.

3.2. 의미론

3.2.1. 의미상 쭉정이

차이점 비교의 출력이 사람이 사용하기 위해 설계한 경우(시각적으로 표시하기와 같이), 문제는 바뀐다. 이 경우에 목적은 좀 더 의미있는 나누기를 제공하는 것이 목적이다. 다음의 두 예제들을 살펴보자.

Text 1: Quicq fyre	Text 1: Slow fool
Text 2: Quick fire	Text 2: Quick fire
Diff:   Quicqk fyire	Diff:   SlowQuick foolire
Split:  Quicqk f fyire	Split:  SlowQuick f foolire
Merge:  Quicq fyk fire	Merge:  Slow foolQuick fire

수학적으로, 이 예제들은 매우 유사하다. 그들은 가운데에 동일성 영역(" f")를 가지고 있고, 그들은 동일한 편집 연산의 수를 가지고 있다. 첫번째 예제가 그것의 초기의 diff 단계에서(두 오타를 수정하는 것과 관련 있는 부분) 동일성 영역을 쪼개고 합친 후 보다는 사람에게 좀 더 의미가 와닿는다. 반면에, 두번째 예제(큰 편집 영역을 포함하고 있는 부분)는 그것의 초기의 diff 단계에서 별로 의미가 없고, 동일성 영역을 쪼개고 합친 후에야 훨씬 더 명확하다. 이 두 에제의 주요한 차이점은 동일성 영역을 감싼고 있는 부분에서의 변화의 양이다.

의미상 쭉정이를 제거하기 위한 한가지 해결책은 자신의 양쪽에 있는 삽입과 삭제보다 작거나 같은 동일성 영역을 무시하는 것이다. 그러한 동일성 영역이 발견되었을 때, 그것은 하나의 삭제와 덧붙임으로 쪼개진다. 다음으로 남아있는 동일성 영역들에 의해 쪼개어지지 않은 모든 삭제와 덧붙임들을 정렬하고 합병하는 것이다. 다음은 이러한 단계들을 보이기 위해 일부러 만든 예제이다:

Text 1:    Hovering

Text 2:    My government

Diff:         HMy goveringment

Split 1:    HMy goverinngment

Split 2:    HMy goveroverinngment

Merge:   HoveringMy government

차이점 비교(Diff) 결과에서 보면, "over"의 경우 4 문자를 가지고 있고, 오직 5개(HMy_g)와 1개(i)의 문자의 변화로 둘러쌓여 있으므로 그것은 남는다. 하지만, "n"의 경우 1 문자를 가지고 있고, 1개(i)와 5개(gment)의 문자의 변화로 둘러 쌓여 있다. 그런 까닭에, "n"은 쪼개진다. 동일성 영역이 쪼개지면, 다음 단계는 이전의 동일성 영역을 재평가 하기 위해서 백트래킹을 해야 한다. 왜냐하면, 이전의 동일성 영역의 문맥(context)가 변경되었기 때문이다. "over"의 경우 이제 5개와 8개의 문자의 변화로 둘러싸이게 되고, 이 역시 쪼개지게 된다. 마침내 모든 조각들이 합쳐지고, 쉽게 이해할 수 있는 차이점 비교 결과로 보이게 된다.

JavaScript Code

1. function diff_cleanupSemantic(diffs) {  
2.   // Reduce the number of edits by eliminating semantically trivial equalities.  
3.   var changes = false;  
4.   var equalities = [];  // Stack of indices where equalities are found.  
5.   var lastequality = null;  // Always equal to equalities[equalities.length-1][1]  
6.   var pointer = 0;  // Index of current position.  
7.   // Number of characters that changed prior to the equality.  
8.   var length_changes1 = 0;  
9.   // Number of characters that changed after the equality.  
10.   var length_changes2 = 0;  
11.   while (pointer < diffs.length) {  
12.     if (diffs[pointer][0] == DIFF_EQUAL) {  // equality found  
13.       equalities.push(pointer);  
14.       length_changes1 = length_changes2;  
15.       length_changes2 = 0;  
16.       lastequality = diffs[pointer][1];  
17.     } else {  // an insertion or deletion  
18.       length_changes2 += diffs[pointer][1].length;  
19.       if (lastequality !== null && (lastequality.length <= length_changes1) &&  
20.           (lastequality.length <= length_changes2)) {  
21.         //alert('Splitting: "' + lastequality + '"');  
22.         // Duplicate record  
23.         diffs.splice(equalities[equalities.length - 1], 0,  
24.                      [DIFF_DELETE, lastequality]);  
25.         // Change second copy to insert.  
26.         diffs[equalities[equalities.length - 1] + 1][0] = DIFF_INSERT;  
27.         // Throw away the equality we just deleted.  
28.         equalities.pop();  
29.         // Throw away the previous equality (it needs to be reevaluated).  
30.         equalities.pop();  
31.         pointer = equalities.length ? equalities[equalities.length - 1] : -1;  
32.         length_changes1 = 0;  // Reset the counters.  
33.         length_changes2 = 0;  
34.         lastequality = null;  
35.         changes = true;  
36.       }  
37.     }  
38.     pointer++;  
39.   }  
40.   
41.   if (changes) {  
42.     diff_cleanupMerge(diffs);  
43.   }  
44. }

Java Code

1. public void diff_cleanupSemantic(LinkedList<Diff> diffs) {  
2.   // Reduce the number of edits by eliminating semantically trivial equalities.  
3.   if (diffs.isEmpty()) {  
4.     return;  
5.   }  
6.   boolean changes = false;  
7.   Stack<Diff> equalities = new Stack<Diff>();  // Stack of qualities.  
8.   String lastequality = null;  // Always equal to equalities.lastElement().text  
9.   ListIterator<Diff> pointer = diffs.listIterator();  
10.   // Number of characters that changed prior to the equality.  
11.   int length_changes1 = 0;  
12.   // Number of characters that changed after the equality.  
13.   int length_changes2 = 0;  
14.   Diff thisDiff = pointer.next();  
15.   while (thisDiff != null) {  
16.     if (thisDiff.operation == Operation.EQUAL) {  
17.       // equality found  
18.       equalities.push(thisDiff);  
19.       length_changes1 = length_changes2;  
20.       length_changes2 = 0;  
21.       lastequality = thisDiff.text;  
22.     } else {  
23.       // an insertion or deletion  
24.       length_changes2 += thisDiff.text.length();  
25.       if (lastequality != null && (lastequality.length() <= length_changes1)  
26.           && (lastequality.length() <= length_changes2)) {  
27.         //System.out.println("Splitting: '" + lastequality + "'");  
28.         // Walk back to offending equality.  
29.         while (thisDiff != equalities.lastElement()) {  
30.           thisDiff = pointer.previous();  
31.         }  
32.         pointer.next();  
33.   
34.         // Replace equality with a delete.  
35.         pointer.set(new Diff(Operation.DELETE, lastequality));  
36.         // Insert a corresponding an insert.  
37.         pointer.add(new Diff(Operation.INSERT, lastequality));  
38.   
39.         equalities.pop();  // Throw away the equality we just deleted.  
40.         if (!equalities.empty()) {  
41.           // Throw away the previous equality (it needs to be reevaluated).  
42.           equalities.pop();  
43.         }  
44.         if (equalities.empty()) {  
45.           // There are no previous equalities, walk back to the start.  
46.           while (pointer.hasPrevious()) {  
47.             pointer.previous();  
48.           }  
49.         } else {  
50.           // There is a safe equality we can fall back to.  
51.           thisDiff = equalities.lastElement();  
52.           while (thisDiff != pointer.previous()) {  
53.             // Intentionally empty loop.  
54.           }  
55.         }  
56.   
57.         length_changes1 = 0;  // Reset the counters.  
58.         length_changes2 = 0;  
59.         lastequality = null;  
60.         changes = true;  
61.       }  
62.     }  
63.     thisDiff = pointer.hasNext() ? pointer.next() : null;  
64.   }  
65.   
66.   if (changes) {  
67.     diff_cleanupMerge(diffs);  
68.   }  
69. }

Python Code

1. def diff_cleanupSemantic(diffs):  
2.   # Reduce the number of edits by eliminating semantically trivial equalities.  
3.   changes = False  
4.   equalities = []  # Stack of indices where equalities are found.  
5.   lastequality = None  # Always equal to equalities[-1][1]  
6.   pointer = 0  # Index of current position.  
7.   length_changes1 = 0  # Number of chars that changed prior to the equality.  
8.   length_changes2 = 0  # Number of chars that changed after the equality.  
9.   while pointer < len(diffs):  
10.     if diffs[pointer][0] == DIFF_EQUAL:  # equality found  
11.       equalities.append(pointer)  
12.       length_changes1 = length_changes2  
13.       length_changes2 = 0  
14.       lastequality = diffs[pointer][1]  
15.     else:  # an insertion or deletion  
16.       length_changes2 += len(diffs[pointer][1])  
17.       if (lastequality != None and (len(lastequality) <= length_changes1) and  
18.           (len(lastequality) <= length_changes2)):  
19.         # Duplicate record  
20.         diffs.insert(equalities[-1], (DIFF_DELETE, lastequality))  
21.         # Change second copy to insert.  
22.         diffs[equalities[-1] + 1] = (DIFF_INSERT,  
23.             diffs[equalities[-1] + 1][1])  
24.         # Throw away the equality we just deleted.  
25.         equalities.pop()  
26.         # Throw away the previous equality (it needs to be reevaluated).  
27.         if len(equalities) != 0:  
28.           equalities.pop()  
29.         if len(equalities):  
30.           pointer = equalities[-1]  
31.         else:  
32.           pointer = -1  
33.         length_changes1 = 0  # Reset the counters.  
34.         length_changes2 = 0  
35.         lastequality = None  
36.         changes = True  
37.     pointer += 1  
38.   
39.   if changes:  
40.     diff_cleanupMerge(diffs)

'diff_cleanupMerge' 함수에 대해서는 이전의 코드를 살펴보기 바란다.

이 해결책은 완전하지 않다. 이것은 좁은 시야를 가지고 있다. 즉 이것은 평가된 각 동일성 영역의 바로 이웃한 문자열 밖에는 볼 수 없다. 그 결과과 약간의 쭉정이의 그룹이 남아 있을 수 있다:

Text 1:  It was a dark and stormy night.

Text 2:  The black can in the cupboard.

Diff:       ItThe wblas a darck cand sin the cupboarmy nightd.

Split:      ItThe  wblaas a darck cand  sin tthe cupbooarrmy nightd.

Merge:  It was a darThe black cand stormy night in the cupboard.

더 종합적인 해결책은 아마도 문제의 동일성 영역으로부터 차이점의 가중 평균을 계산하는 방법일 것이다.

3.2.2. 의미상 정렬

의미가 있는 차이점 비교 결과들을 만드는 것과 다른 문제로 논리적 분절들로 편집 경계를 정렬하는 것이 있다. 다음의 차이점 결과들을 보자.

Text 1: That cartoon.

Text 2: That cat cartoon.

Diff 1: That cat cartoon.

Diff 2: That cat cartoon.

Diff 3: That cat cartoon.

Diff 4: That cat cartoon.

Diff 5: That cat cartoon.

Diff 6: That cat cartoon.

모든 6개의 차이점 결과들을 적합하고, 최소한의 길이를 가지고 있다. 차이점 결과 1과 6은 차이점 비교 알고리즘들로부터 도출된 결과로 보인다. 하지만, 차이점 결과 3과 4는 차이점의 의미론적 의미를 추출한 것으로 보인다.

해결책은 양편이 동일성 영역으로 둘러싸인 삽입 또는 삭제의 위치를 알아낸 후에 그들을 옆길로 미끄러뜨리려고 시도하는 것이다. 만약 앞선 동일성 영역의 마지막 토큰이 편집의 마지막 토큰과 같다면, 편집은 왼쪽으로 미끄러질 것이다. 마찬가지로, 만약 편집의 첫번째 토큰이 다음의 동일성 영역의 첫 토큰과 같다면, 편집은 오른쪽으로 미끄러질 것이다. 각 가능한 경우에 대해서 그들의 경계가 논리적ㅇ로 나타나는 지에 대한 여부에 따라서 점수가 매겨질 수 있다. 사용 가능한 방식을 말하자면 다음과 같다:

• 1점: 만약 경계가 알파벳이나 숫자가 아닌 문자와 인접한 경우
• 2점: 만약 경계가 공백과 인접한 경우
• 3점: 만약 경계가 엔터키 문자와 인접한 경우
• 4점: 만약 경게가 공백인 선과 인접한 경우
• 5점: 만약 경계가 전체 동일성 영역의 문자들을 모두 소비한 경우

이 점수 매기는 방식은 차이점 결과 1, 2, 5, 6에 대해서는 0점을 주고 3과 4에 대해서는 4점을 준다.

JavaScript Code

1. function diff_cleanupSemanticLossless(diffs) {  
2.   // Look for single edits surrounded on both sides by equalities  
3.   // which can be shifted sideways to align the edit to a word boundary.  
4.   // e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.  
5.   // Define some regex patterns for matching boundaries.   
6.   var punctuation = /[^a-zA-Z0-9]/;  
7.   var whitespace = /\s/;  
8.   var linebreak = /[\r\n]/;  
9.   var blanklineEnd = /\n\r?\n$/;  
10.   var blanklineStart = /^\r?\n\r?\n/;  
11.   
12.   function diff_cleanupSemanticScore(one, two) {  
13.     // Given two strings, compute a score representing whether the internal  
14.     // boundary falls on logical boundaries.  
15.     // Scores range from 5 (best) to 0 (worst).  
16.     // Closure, makes reference to regex patterns defined above.  
17.     if (!one || !two) {  
18.       // Edges are the best.  
19.       return 5;  
20.     }  
21.   
22.     // Each port of this function behaves slightly differently due to  
23.     // subtle differences in each language's definition of things like  
24.     // 'whitespace'.  Since this function's purpose is largely cosmetic,  
25.     // the choice has been made to use each language's native features  
26.     // rather than force total conformity.  
27.     var score = 0;  
28.     // One point for non-alphanumeric.  
29.     if (one.charAt(one.length - 1).match(punctuation) ||  
30.         two.charAt(0).match(punctuation)) {  
31.       score++;  
32.       // Two points for whitespace.  
33.       if (one.charAt(one.length - 1).match(whitespace) ||  
34.           two.charAt(0).match(whitespace)) {  
35.         score++;  
36.         // Three points for line breaks.  
37.         if (one.charAt(one.length - 1).match(linebreak) ||  
38.             two.charAt(0).match(linebreak)) {  
39.           score++;  
40.           // Four points for blank lines.  
41.           if (one.match(blanklineEnd) || two.match(blanklineStart)) {  
42.             score++;  
43.           }  
44.         }  
45.       }  
46.     }  
47.     return score;  
48.   }  
49.   
50.   var pointer = 1;  
51.   // Intentionally ignore the first and last element (don't need checking).  
52.   while (pointer < diffs.length - 1) {  
53.     if (diffs[pointer - 1][0] == DIFF_EQUAL &&  
54.         diffs[pointer + 1][0] == DIFF_EQUAL) {  
55.       // This is a single edit surrounded by equalities.  
56.       var equality1 = diffs[pointer - 1][1];  
57.       var edit = diffs[pointer][1];  
58.       var equality2 = diffs[pointer + 1][1];  
59.   
60.       // First, shift the edit as far left as possible.  
61.       var commonOffset = diff_commonSuffix(equality1, edit);  
62.       if (commonOffset) {  
63.         var commonString = edit.substring(edit.length - commonOffset);  
64.         equality1 = equality1.substring(0, equality1.length - commonOffset);  
65.         edit = commonString + edit.substring(0, edit.length - commonOffset);  
66.         equality2 = commonString + equality2;  
67.       }  
68.   
69.       // Second, step character by character right, looking for the best fit.  
70.       var bestEquality1 = equality1;  
71.       var bestEdit = edit;  
72.       var bestEquality2 = equality2;  
73.       var bestScore = diff_cleanupSemanticScore(equality1, edit) +  
74.           diff_cleanupSemanticScore(edit, equality2);  
75.       while (edit.charAt(0) === equality2.charAt(0)) {  
76.         equality1 += edit.charAt(0);  
77.         edit = edit.substring(1) + equality2.charAt(0);  
78.         equality2 = equality2.substring(1);  
79.         var score = diff_cleanupSemanticScore(equality1, edit) +  
80.             diff_cleanupSemanticScore(edit, equality2);  
81.         // The >= encourages trailing rather than leading whitespace on edits.  
82.         if (score >= bestScore) {  
83.           bestScore = score;  
84.           bestEquality1 = equality1;  
85.           bestEdit = edit;  
86.           bestEquality2 = equality2;  
87.         }  
88.       }  
89.   
90.       if (diffs[pointer - 1][1] != bestEquality1) {  
91.         // We have an improvement, save it back to the diff.  
92.         if (bestEquality1) {  
93.           diffs[pointer - 1][1] = bestEquality1;  
94.         } else {  
95.           diffs.splice(pointer - 1, 1);  
96.           pointer--;  
97.         }  
98.         diffs[pointer][1] = bestEdit;  
99.         if (bestEquality2) {  
100.           diffs[pointer + 1][1] = bestEquality2;  
101.         } else {  
102.           diffs.splice(pointer + 1, 1);  
103.           pointer--;  
104.         }  
105.       }  
106.     }  
107.     pointer++;  
108.   }  
109. }

Java Code

1. public void diff_cleanupSemanticLossless(LinkedList<Diff> diffs) {  
2.   // Look for single edits surrounded on both sides by equalities  
3.   // which can be shifted sideways to align the edit to a word boundary.  
4.   // e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.  
5.   String equality1, edit, equality2;  
6.   String commonString;  
7.   int commonOffset;  
8.   int score, bestScore;  
9.   String bestEquality1, bestEdit, bestEquality2;  
10.   // Create a new iterator at the start.  
11.   ListIterator<Diff> pointer = diffs.listIterator();  
12.   Diff prevDiff = pointer.hasNext() ? pointer.next() : null;  
13.   Diff thisDiff = pointer.hasNext() ? pointer.next() : null;  
14.   Diff nextDiff = pointer.hasNext() ? pointer.next() : null;  
15.   // Intentionally ignore the first and last element (don't need checking).  
16.   while (nextDiff != null) {  
17.     if (prevDiff.operation == Operation.EQUAL &&  
18.         nextDiff.operation == Operation.EQUAL) {  
19.       // This is a single edit surrounded by equalities.  
20.       equality1 = prevDiff.text;  
21.       edit = thisDiff.text;  
22.       equality2 = nextDiff.text;  
23.   
24.       // First, shift the edit as far left as possible.  
25.       commonOffset = diff_commonSuffix(equality1, edit);  
26.       if (commonOffset != 0) {  
27.         commonString = edit.substring(edit.length() - commonOffset);  
28.         equality1 = equality1.substring(0, equality1.length() - commonOffset);  
29.         edit = commonString + edit.substring(0, edit.length() - commonOffset);  
30.         equality2 = commonString + equality2;  
31.       }  
32.   
33.       // Second, step character by character right, looking for the best fit.  
34.       bestEquality1 = equality1;  
35.       bestEdit = edit;  
36.       bestEquality2 = equality2;  
37.       bestScore = diff_cleanupSemanticScore(equality1, edit)  
38.           + diff_cleanupSemanticScore(edit, equality2);  
39.       while (edit.length() != 0 && equality2.length() != 0  
40.           && edit.charAt(0) == equality2.charAt(0)) {  
41.         equality1 += edit.charAt(0);  
42.         edit = edit.substring(1) + equality2.charAt(0);  
43.         equality2 = equality2.substring(1);  
44.         score = diff_cleanupSemanticScore(equality1, edit)  
45.             + diff_cleanupSemanticScore(edit, equality2);  
46.         // The >= encourages trailing rather than leading whitespace on edits.  
47.         if (score >= bestScore) {  
48.           bestScore = score;  
49.           bestEquality1 = equality1;  
50.           bestEdit = edit;  
51.           bestEquality2 = equality2;  
52.         }  
53.       }  
54.   
55.       if (!prevDiff.text.equals(bestEquality1)) {  
56.         // We have an improvement, save it back to the diff.  
57.         if (bestEquality1.length() != 0) {  
58.           prevDiff.text = bestEquality1;  
59.         } else {  
60.           pointer.previous(); // Walk past nextDiff.  
61.           pointer.previous(); // Walk past thisDiff.  
62.           pointer.previous(); // Walk past prevDiff.  
63.           pointer.remove(); // Delete prevDiff.  
64.           pointer.next(); // Walk past thisDiff.  
65.           pointer.next(); // Walk past nextDiff.  
66.         }  
67.         thisDiff.text = bestEdit;  
68.         if (bestEquality2.length() != 0) {  
69.           nextDiff.text = bestEquality2;  
70.         } else {  
71.           pointer.remove(); // Delete nextDiff.  
72.           nextDiff = thisDiff;  
73.           thisDiff = prevDiff;  
74.         }  
75.       }  
76.     }  
77.     prevDiff = thisDiff;  
78.     thisDiff = nextDiff;  
79.     nextDiff = pointer.hasNext() ? pointer.next() : null;  
80.   }  
81. }  
82.   
83. private int diff_cleanupSemanticScore(String one, String two) {  
84.   // Given two strings, compute a score representing whether the internal  
85.   // boundary falls on logical boundaries.  
86.   // Scores range from 5 (best) to 0 (worst).  
87.   if (one.length() == 0 || two.length() == 0) {  
88.     // Edges are the best.  
89.     return 5;  
90.   }  
91.   
92.   // Each port of this function behaves slightly differently due to  
93.   // subtle differences in each language's definition of things like  
94.   // 'whitespace'.  Since this function's purpose is largely cosmetic,  
95.   // the choice has been made to use each language's native features  
96.   // rather than force total conformity.  
97.   int score = 0;  
98.   // One point for non-alphanumeric.  
99.   if (!Character.isLetterOrDigit(one.charAt(one.length() - 1))  
100.       || !Character.isLetterOrDigit(two.charAt(0))) {  
101.     score++;  
102.     // Two points for whitespace.  
103.     if (Character.isWhitespace(one.charAt(one.length() - 1))  
104.         || Character.isWhitespace(two.charAt(0))) {  
105.       score++;  
106.       // Three points for line breaks.  
107.       if (Character.getType(one.charAt(one.length() - 1)) == Character.CONTROL  
108.           || Character.getType(two.charAt(0)) == Character.CONTROL) {  
109.         score++;  
110.         // Four points for blank lines.  
111.         if (BLANKLINEEND.matcher(one).find()  
112.             || BLANKLINESTART.matcher(two).find()) {  
113.           score++;  
114.         }  
115.       }  
116.     }  
117.   }  
118.   return score;  
119. }  
120.   
121. private Pattern BLANKLINEEND  
122.     = Pattern.compile("\\n\\r?\\n\\Z", Pattern.DOTALL);  
123. private Pattern BLANKLINESTART  
124.     = Pattern.compile("\\A\\r?\\n\\r?\\n", Pattern.DOTALL);

Python Code

1. def diff_cleanupSemanticLossless(diffs):  
2.   # Look for single edits surrounded on both sides by equalities  
3.   # which can be shifted sideways to align the edit to a word boundary.  
4.   # e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.  
5.   
6.   def diff_cleanupSemanticScore(one, two):  
7.     # Given two strings, compute a score representing whether the  
8.     # internal boundary falls on logical boundaries.  
9.     # Scores range from 5 (best) to 0 (worst).  
10.     # Closure, but does not reference any external variables.  
11.   
12.     if not one or not two:  
13.       # Edges are the best.  
14.       return 5  
15.   
16.     # Each port of this function behaves slightly differently due to  
17.     # subtle differences in each language's definition of things like  
18.     # 'whitespace'.  Since this function's purpose is largely cosmetic,  
19.     # the choice has been made to use each language's native features  
20.     # rather than force total conformity.  
21.     score = 0  
22.     # One point for non-alphanumeric.  
23.     if not one[-1].isalnum() or not two[0].isalnum():  
24.       score += 1  
25.       # Two points for whitespace.  
26.       if one[-1].isspace() or two[0].isspace():  
27.         score += 1  
28.         # Three points for line breaks.  
29.         if (one[-1] == "\r" or one[-1] == "\n" or  
30.             two[0] == "\r" or two[0] == "\n"):  
31.           score += 1  
32.           # Four points for blank lines.  
33.           if (re.search("\\n\\r?\\n$", one) or  
34.               re.match("^\\r?\\n\\r?\\n", two)):  
35.             score += 1  
36.     return score  
37.   
38.   pointer = 1  
39.   # Intentionally ignore the first and last element (don't need checking).  
40.   while pointer < len(diffs) - 1:  
41.     if (diffs[pointer - 1][0] == DIFF_EQUAL and  
42.         diffs[pointer + 1][0] == DIFF_EQUAL):  
43.       # This is a single edit surrounded by equalities.  
44.       equality1 = diffs[pointer - 1][1]  
45.       edit = diffs[pointer][1]  
46.       equality2 = diffs[pointer + 1][1]  
47.   
48.       # First, shift the edit as far left as possible.  
49.       commonOffset = diff_commonSuffix(equality1, edit)  
50.       if commonOffset:  
51.         commonString = edit[-commonOffset:]  
52.         equality1 = equality1[:-commonOffset]  
53.         edit = commonString + edit[:-commonOffset]  
54.         equality2 = commonString + equality2  
55.   
56.       # Second, step character by character right, looking for the best fit.  
57.       bestEquality1 = equality1  
58.       bestEdit = edit  
59.       bestEquality2 = equality2  
60.       bestScore = (diff_cleanupSemanticScore(equality1, edit) +  
61.           diff_cleanupSemanticScore(edit, equality2))  
62.       while edit and equality2 and edit[0] == equality2[0]:  
63.         equality1 += edit[0]  
64.         edit = edit[1:] + equality2[0]  
65.         equality2 = equality2[1:]  
66.         score = (diff_cleanupSemanticScore(equality1, edit) +  
67.             diff_cleanupSemanticScore(edit, equality2))  
68.         # The >= encourages trailing rather than leading whitespace on edits.  
69.         if score >= bestScore:  
70.           bestScore = score  
71.           bestEquality1 = equality1  
72.           bestEdit = edit  
73.           bestEquality2 = equality2  
74.   
75.       if diffs[pointer - 1][1] != bestEquality1:  
76.         # We have an improvement, save it back to the diff.  
77.         if bestEquality1:  
78.           diffs[pointer - 1] = (diffs[pointer - 1][0], bestEquality1)  
79.         else:  
80.           del diffs[pointer - 1]  
81.           pointer -= 1  
82.         diffs[pointer] = (diffs[pointer][0], bestEdit)  
83.         if bestEquality2:  
84.           diffs[pointer + 1] = (diffs[pointer + 1][0], bestEquality2)  
85.         else:  
86.           del diffs[pointer + 1]  
87.           pointer -= 1  
88.     pointer += 1