RFC - fixing comparison feature

Hi,

I see lyx comparison feature broken for main two reasons:

1) it produces char-like diffs spilled across the words and sentences even for word-like changes which makes it totally unreadable for naked eye (bug #6889)
2) it's superslow on any non trivial changeset

Below is the attempt to narrow heuristics to fix 1).
Please send me your comments or objections if you have any before I start shaping the code.

Pavel
---


IV. Myers postprocessing refining the diff on non-CJK languages
   Problem:
       The previous steps create mathematically minimal but frequently unreadable diff - 
       it scatters tiny CT fragments across words and sentences. Example from bug #6889:
       instead of {unique}[single] the results looks like {u}[si]n{iqu}[gl]e.
   Approach: 
      First refine for single chars and later we switch to words (for performance reasons)
      while leaving the char-level diffs functional so small char-level typos are easily seen.

      References: 
        - LibreOffice takes the opposite route - diffs whole words (so no question of scatter). 
	- MS Word gives choice between char vs word level.

  IVa. Detector for "this word's character diff is the scattered-noise"

    * First some terminology:
       "Single continuous run" - at most one deleted block, then at most one inserted block, in that order
            - {...} - pure deletion
            - [...] - pure insertion
            - {...}[...] - deletion immediately followed by insertion (a substitution)

	    - []{} does not occur (compare always emits delete first)
	    - mixtures {}[]{}[] do not occur (compare always build whole subrange as deleted/inserted -
	           mixture always occurs with snake inside (>=1 unchanged character) eg {}[]s{}[], but
		   the it's no more continuous run.

       "Unchanged interior" - a run of unchanged characters (="survivor") that touches neither end
                              of the word - i.e. it has changed text on both sides.

       "Crumb" - an interior unchanged piece of 1-2 characters (this 3 chars threshold is the only knob
                 in our collapse detector).

    * Now the heuristics:
       Keep char-diff for: edits are single continous run (one consecutive {del}[ins] run)  OR
                           "real shared text, not coincidence" - edits are separated by substantial
		                                           (>= 3 char) unchanged stretches.
       Otherwise reject diff, collapse as whole word diff {old}[new].

    * Consequences
       1. A single contiguous edit has only boundary (prefix/suffix) survivors, so it is always kept ->
          typo fixes stay character-precise: correct[i]on.
       2. A substantial unchanged interior is kept: {d}[m]isprove{n}[d] keeps the real shared stem
          isprove even though both ends changed.
       3. A crumb triggers a whole-word collapse: {unique}[single], {beating}[boaring].
       4. The decision is per-word all-or-nothing: one interior crumb collapses the entire word, 
          because a half-cleaned word still reads as fragments.
       5. The trigger is the size of the interior unchanged survivor, not the amount of change - so a
          big change with a solid survivor is kept, while a tiny change straddling a crumb is collapsed.

    * Examples:
   ------------------------------------------------------------------------------------------------------ 
  |       old -> new        | raw character diff  | unchanged interior  | verdict  |       result        |
   ------------------------------------------------------------------------------------------------------
  | correcton -> correction | correct[i]on        | none (all boundary) | keep     | correct[i]on        |
   ------------------------------------------------------------------------------------------------------
  | disproven -> misproved  | {d}[m]isprove{n}[d] | isprove (7)         | keep     | {d}[m]isprove{n}[d] |
   ------------------------------------------------------------------------------------------------------
  | unique -> single        | {u}[si]n{iqu}[gl]e  | n (1)               | collapse | {unique}[single]    |
   ------------------------------------------------------------------------------------------------------
  | beating -> boaring      | b{e}[o]a{t}[r]ing   | a (1)               | collapse | {beating}[boaring]  |
   ------------------------------------------------------------------------------------------------------

-- 
lyx-devel mailing list
[email protected]
https://lists.lyx.org/mailman/listinfo/lyx-devel