# Automated tests for differencing algorithm

We are designing a differencing algorithm (based on Longest Common Subsequence) that compares a source text and a modified copy to extract the new content (i.e. content that is only in the modified copy). I'm currently compiling a library of test case data.

We need to be able to run automated tests that verify the test cases, but we don't want to verify strict accuracy. Given the heuristic nature of our algorithm, we need our test pass/failures to be fuzzy. We want to specify a threshold of overlap between the desired result and the actual result (i.e. the content that is extracted).

I have a few sketches in my mind as to how to solve this, but has anyone done this before? Does anyone have guidance or ideas about how to do this effectively?

-
Automated tests typically deal with static data. If your source text is static, and your modified copy is static, shouldn't the end result always be the same? – bwalk2895 Jul 9 '12 at 15:57
If I were verifying for strict accuracy, yes. But due to the heuristic nature of the algorithm and volatility of the data, we don't want that. We want to set an acceptable threshold that will verify complete inclusion of new content and minimal extra noise. – Matthew Rodatus Jul 9 '12 at 16:27

As @kevin cline has pointed out there are two different constraints. I'll call these the accuracy and the efficiency constraints.

Checking the accuracy constraint should be straightforward. Basically, all you need to do is test that you can recreate the original data. That should be straightforward as you can use tools like Patch as kevin suggests.

But the efficiency constraint is trickier. I think that setting a threshold is a bad idea. Suppose that you set the thresholds at 10% lower the the algorithms current performance.

1. What happens if the algorithm's efficiency drops by 1% as a result of a change? Your tests won't tell you about it.
2. What if the algorithm's efficiency is increase by 1%, will you notice?
3. What happens if the algorithm is improved by 20%, and then degraded by 10%, you are still well above your initial thresholds, so the test won't help you.

The problem is that the efficiency constraints is not a pass/fail concern. Trying to force it into a pass/fail test with a threshold is not a good idea.

I think you should treat this like performance testing. For each revision, run all the tests and collect the efficiency data. Plot all the data on a graph showing the changing efficiency with different revisions. Whenever the efficiency on a test declines, automatically send an e-mail to someone who can make the judgement call on whether its acceptable or not.

-

It seems you have a hard constraint to produce a correct set of differences, and a goal to produce a minimal set of differences.

To verify the constraint, you need to merge the differences into one of the inputs and see if you obtain the other input. Fortunately, this has already been done. All you have to do is output the differences in the format expected by GNU patch.

To test the second, you just need to ensure that the output is not getting unacceptably large. Since you can change the program so that one set of differences gets smaller while another gets larger, it will be up to you to define a measure of goodness and a threshold of acceptability.

-
Good insight that there are two constraints here. I need complete inclusion of new content (which is a simple yes/no determination) and minimal extra noise (for which I need the threshold). Thanks. – Matthew Rodatus Jul 9 '12 at 16:28