12

I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations.

One thing that has become important is to take the list of changes and interpret them into human readable text. While the current algorithm is very efficient, it is so much so that it is difficult to expand upon.

Short Question

I was thinking about trying to use A* and a heuristic that adds penalties for "turns". The idea being to smooth out unnecessary "add, delete, add, delete, add, delete" so that it is easier to parse into something a human can read. Basically, turn my shortest path problem into a simplest path problem.

And of course not create output that is always "Delete everything, Add everything"

Does this sound reasonable?

Is there any precedence for using a heuristic in a DIFF implementation? What is the heuristic?

The Problem:

If a long sentence is deleted and another long sentence removed, but they do share at least one word, say "with". Leaving the common word alone (by not both adding and deleting it) will create the shortest path. However, this really just obfuscates the context of the change to a human trying to read a print out of the changes.

Example with current DIFF:

  • Old text: Clean: Powerwash and blow dry with shop air.
  • New text: Clean: Wipe with acetone and a lint free cloth.
  • Change Note List:
    • Change "Powerwash and blow dry" to "Wipe with acetone"
    • Change "shop air" to "acetone and a lint free cloth"

Note: "Change" is used instead of "delete 'shop air', add 'acetone'"

As you can see, the second note loses ALL context and without still looking at the full old and new text sets of text you cannot understand what it means.

Note about Punctuation:

I have delimited punctuation as separate "words" so that I would get

  • Add "("

instead of

  • Change "Repair" to "(Repair"

because this was obnoxious. However, that means that if there is even a comma in both texts (as opposed to the word "with" in the previous example) the same thing happens.

Possible Solution:

I think I could use a different path finding algorithm instead that can give me the flexibility to add weight to different change "paths" that might make more sense to a person. Maybe, I could even make traveling to nodes containing punctuation have little weight (not sure how this would effect other things).

Then I could get the previous example to list the following:

  • Change Note List:
    • Change "Powerwash and blow dry with shop air" to "Wipe with acetone and a lint free cloth"

See! Much clearer!

I know I would take a performance hit, and I might have to do a fairly major overhaul of my program, but it's more important to have the final result I want.

Bottom Line:

Again, is there any precedence for using a heuristic in a DIFF implementation, and what is it?

Other thoughts? A reasonable time investment? Other ideas? Other algorithms?

Thanks in advance!

EDIT:

I tried to clarify/solidify my question and generalize my question to adding a heuristic to my algorithm, rather than using A*. Basically the same thing in this instance, but I still think more accurate now. This post was insightful.

1

You might do in a vimdiff-like version:

Step 1: identifying added, deleted and modified sentences.

Step 2: for each modified sentence, locate the first and the last changed words, and cut anything not between these two words.

If you need to keep coherent more grammar structure, look at the internals of http://www.languagetool.org/ or another shown on this post.

About presentation: you may present both versions of that sentence one under the other. You might want to show the context for each change. For inspiration, look at latexdiff which can print the added text in blue at is final place in the final version of text, and the deleted text in footnotes (even compatible with \usepackage[para]{footmisc}).

  • This only addresses issues of display, not the main question of heuristic matching. – Adam Zuckerman Mar 27 '14 at 17:03
  • Did you read my second paragraph ? – user2987828 Mar 27 '14 at 17:04
  • I did. Could you expand upon what you are trying to explain? My first (and second) reading of it led me to think that you were still describing how to display the information, not process it. – Adam Zuckerman Mar 27 '14 at 17:06
  • I am currently able to use html to format the adds and removes, the stackexchange edit viewer is what inspired me. This is not my issue. – ptpaterson Apr 11 '14 at 3:14
  • 1
    I need to understand better how I might use a different graph search method to find the differences. The original one I have effectively creates a graph with equal weights of all edges and performs a depth first search to find all of the add/remove/keep moves to the end. I am considering adding different weights to the edges and adding a heuristic. – ptpaterson Apr 11 '14 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.