Generate test cases for levenshtein distance implementation with quickCheck

Question

As part of me learning about quickCheck I want to build a test generator for a levenshtein edit distance implementation. The obvious approach I think is to start with two equal strings and a random non-reducable series of insert/delete/traspose actions, apply that to one of the strings and assert that the levenshtein distance is the length of the random series.

I am quite stuck with this can someone help?

Answer 1

Getting "non-reducible" right sounds pretty hard. I would try to find a larger number of less complicated invariants. Here are some ideas:

1. The edit distance between any string and itself is 0.
2. No two strings have a negative edit distance.
3. For an arbitrary string x, if you apply exactly one change to it, producing y, the edit distance between x and y should be 1.
4. Given two strings x and y, compute the distance d between them. Then, change y, yielding y', and compute its distance from x: it should differ from d by at most 1.
5. After applying n edits to a string x, the distance between the edited string and x should be at most n. Note that case (1) is a special case of this, where n=0, so you could omit that one for concision if you like. Or, keep it around, since case (1) may generate simpler counterexamples.
6. The function should be symmetric: the edit distance from x to y should be the same as from y to x.

If you have another, known-good implementation of the algorithm to test against, you could compare to that, and assert that you always get the same answer as it does.

The above were all just things that appealed to me without any research. You could do more: for example, encode the lower and upper bounds as defined by wikipedia.