Итак, я пытаюсь придумать ответвление алгоритма Левенштейна, в котором я отслеживаю, какие преобразования я сделал в строке (вставил a или заменил a на b).
Пример:
В основном, скажем, я вычисляю расстояние редактирования для «bbd» и «bcd».
Расстояние редактирования будет равно 1, а преобразование будет "подстилой b вместо c".
Вопрос: Как мне подойти к этой проблеме, поскольку реализации, которые я видел, не заботятся о том, чтобы знать, что это за операция, а только об общей стоимости?
Вы можете использовать этот модуль - там есть функция editops, которая возвращает список с операциями, необходимыми для преобразования одной строки в другую.
Пример:
Levenshtein.editops("FBBDE", "BCDASD")
[('delete', 0, 0), ('replace', 2, 1), ('insert', 4, 3), ('insert', 4, 4), ('replace', 4, 5)]
Из документов:
Найдите последовательность операций редактирования, преобразующих одну строку в другую.
editops (исходная_строка, конечная_строка) editops (edit_operations, source_length, destination_length)
Результатом является список троек (операция, spos, dpos), где операция принимает одно из следующих значений: «равно», «заменить», «вставить» или «удалить»; spos и dpos - это позиция символов в первой (исходной) и второй (целевой) строках. Это операции над отдельными персонажами. Фактически, возвращенный список не содержит «равно», но все связанные функции принимают оба списка с «равными» и без них.
