Читая комментарии, кажется, что это проблема:
Вам дан набор пар строк одинаковой длины, и каждая пара является входом для некоторой функции в паре с выходом изфункция.Итак, для пары A, B мы знаем, что f (A) = B.Цель состоит в том, чтобы перепроектировать f () с большим набором пар A, B.
Использование расстояния Левенштейна на всем наборе, самое большее, скажет вам максимальное количество преобразований, которые должны иметь место.
Лучшим началом было бы расстояние Хэмминга (измененное, чтобы разрешить несколько символов) или сходство Жакара, чтобы определить, сколько позиций в строках не изменяется вообще для всех пар.Тогда вы остаетесь только с теми, кто действительно меняется.
Это не удастся, если буквы сместятся.
Чтобы обнаружить сдвиг, вы хотите использовать глобальное выравнивание ( Needleman-Wunsch ).Затем вы увидите что-то вроде "ABCDE"=>"xABCD", чтобы показать, что от входа до выхода произошел сдвиг влево.
В целом, я чувствую, что расстояние Левенштейна будет очень мало, чтобы помочь вам получить исходный алгоритм.