Heuristic Approach for Flexible DIFF Implementation

Question

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.

Answer 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}).