svn commit: r1062280 - /subversion/branches/diff-optimizations-bytes/BRANCH-README

[jc...@apache.org]

Author: jcorvel
Date: Sat Jan 22 21:36:02 2011
New Revision: 1062280

URL: http://svn.apache.org/viewvc?rev=1062280&view=rev
Log:
On the diff-optimizations-bytes branch:

* BRANCH-README
  Move one of the wild ideas to a "Rejected ideas" section, because it's a
  bad idea. Trying to skip a mismatching line to keep forward scanning going
  can lead to missynchronization.

Modified:
    subversion/branches/diff-optimizations-bytes/BRANCH-README

Modified: subversion/branches/diff-optimizations-bytes/BRANCH-README
URL: http://svn.apache.org/viewvc/subversion/branches/diff-optimizations-bytes/BRANCH-README?rev=1062280&r1=1062279&r2=1062280&view=diff
==============================================================================
--- subversion/branches/diff-optimizations-bytes/BRANCH-README (original)
+++ subversion/branches/diff-optimizations-bytes/BRANCH-README Sat Jan 22 21:36:02 2011
@@ -32,9 +32,6 @@ TODO:
   * revv svn_diff.h#svn_diff_fns_t             []
 
 Other wild ideas (may or may not be worth pursuing):
-  * Make prefix scanning able to skip 1 or a couple of non-matching lines, if
-    it is able to find strictly more matching lines after that, to keep the
-    prefix scanning going.
   * Take advantage of the fact that matching lines often come in batches: when
     inserting a new line into the token tree, and the previous line had a
     match, first try to match the new token with the successor of the
@@ -42,6 +39,26 @@ Other wild ideas (may or may not be wort
   * Add some balancing to the token tree in token.c#svn_diff__tree_insert_token
     to make sure it doesn't degenerate. We may want to investigate first
     whether non-balancedness is really a problem in normal use cases.
+    
+Rejected ideas:
+  * Make prefix scanning able to skip 1 or a couple of non-matching lines, if
+    it is able to find strictly more matching lines after that, to keep the
+    prefix scanning going.
+    
+    This is not a good idea, because it can lead to bad cases of
+    missynchronization (see [3]):
+    
+      bxxaxxbxx
+       || ||
+      axxbxx
+
+    instead of (longest common subsequence):
+    
+      bxxaxxbxx
+        //////
+       axxbxx
 
 [1] http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Reduce_the_problem_set
-[2] http://svn.haxx.se/dev/archive-2011-01/0005.shtml
\ No newline at end of file
+[2] http://svn.haxx.se/dev/archive-2011-01/0005.shtml
+[3] Miller, W., and Myers, E.W. "A File Comparison Program.", Software - 
+    Practice & Experience 15 (1985), pp. 1025-1040.
\ No newline at end of file