Токенизированный алгоритм Майерса (diff)

Выполнили: Аникиев Ян Вячеславович, Голубев Никита Алексеевич, Ниневский Камиль Николаевич, Шишихин Павел Алексеевич

При работе с цифровыми данными регулярно встает задача поиска различий между файлами, которую можно решать, к примеру, утилитой git diff для поиска различий между старой версией кода и новой. При использовании такого рода утилит возникает ряд проблем: программа должна быть эффективна и по памяти, и по времени работы, а также должна быть гибкой в плане того, как следует интерпретировать информацию. Так, например, не всегда однозначно, стоит искать разницу построчно (например, искать только новые, или измененные, или удаленные строки кода, как единое целое) или посимвольно (например, если в строке изменили только один символ, то целесообразнее показать, что изменился ровно один символ, а не вывести измененную строку целиком).

В основе работы лежит несколько ключевых идей: сам алгоритм Майерса для поиска различий в информации, а также токенизация. Например, за счет токенизации можно, не меняя алгоритм, искать различие как и в смысле строк, так и в смысле символов, с минимальными затратами на разработку. При этом сложность токенизаторов ничем не ограничивается. Более того, можно использовать токенизаторы для языков программирования, чтобы находить различия в типах переменных, сигнатурах функций и т.д. Таким образом, используя знание о структуре информации в файле, мы можем давать более осмысленную и наглядную информацию пользователю программы.

Архив с материалами (ZIP, 5,82 Мб)

- В архиве содержатся групповой отчет и презентация

Ссылка на репозиторий на GitHub