Изучая quickCheck, я хочу создать тестовый генератор для реализации удаленного редактирования levenshtein. Я думаю, что очевидный подход состоит в том, чтобы начать с двух равных строк и случайной неизвлекаемой серии действий вставки / удаления / перемещения, применить это к одной из строк и утверждать, что расстояние Левенштейна - это длина случайного ряда.
Я очень застрял в этом, может кто-нибудь помочь?
Получение «несводимого» правильного звучания звучит довольно сложно. Я бы попытался найти большее количество менее сложных инвариантов. Вот несколько идей:
x, если вы примените к ней ровно одно изменение, создав y, расстояние редактирования между x и y должно быть равно 1.x и y, вычислите расстояние d между ними. Затем измените y, получив y', и вычислите его расстояние от x: оно должно отличаться от d не более чем на 1.n изменений к строке x расстояние между редактируемой строкой и x должно быть не более n. Обратите внимание, что case (1) является частным случаем этого, где n = 0, поэтому вы можете опустить его для краткости, если хотите. Или оставьте его при себе, поскольку случай (1) может генерировать более простые контрпримеры.x до y должно быть таким же, как от y до x.Если у вас есть другая, заведомо надежная реализация алгоритма для тестирования, вы можете сравнить ее и утверждать, что вы всегда получаете тот же ответ, что и она.
Все вышеперечисленное было всего лишь тем, что мне нравилось, без каких-либо исследований. Вы могли бы сделать больше: например, закодировать нижнюю и верхнюю границы, как определено википедией .
