Поиск консенсуса.
Не могу найти подходящий алгоритм для следующей задачи.
Есть неизвестная строка. И есть много вариантов испорченной строки (процентов на 80). Портится строка заменами, удалениями и, реже, вставками. Получение новой испорченной строки операция дорогая, но не запредельно.
Надо с достаточным правдоподобием восстановить исходную строку.
Так как новых строк мы можем получать много, хочется иметь алгоритм, работающий на константной памяти.
Основное пожелание, что бы алгоритм был простой (хочу быстро его реализовать на малознакомой платформе что бы проверить некоторые идеи). Есть готовые функции для выравнивания двух строк, вычисление расстояния редактирования.
Посоветуйте, где такой искать?
Есть неизвестная строка. И есть много вариантов испорченной строки (процентов на 80). Портится строка заменами, удалениями и, реже, вставками. Получение новой испорченной строки операция дорогая, но не запредельно.
Надо с достаточным правдоподобием восстановить исходную строку.
Так как новых строк мы можем получать много, хочется иметь алгоритм, работающий на константной памяти.
Основное пожелание, что бы алгоритм был простой (хочу быстро его реализовать на малознакомой платформе что бы проверить некоторые идеи). Есть готовые функции для выравнивания двух строк, вычисление расстояния редактирования.
Посоветуйте, где такой искать?