Детектор плагиата программного кода на основе сравнения AST-деревьев

Смысл работы заключается в переходе от наивного текстового анализа к исследованию логической структуры программы. Обычные диффы и текстовый поиск легко обмануть заменой имён идентификаторов или добавлением пустых строк. Синтаксический разбор выявляет каркас алгоритма и позволяет доказать факт копирования даже после поверхностной маскировки кода.

Парсинг и каноническая нормализация дерева

Работу с кодом начинают со встроенного модуля ast в стандартной библиотеке Python. Функция ast.parse превращает исходный текст в древовидную структуру узлов, где операторы, вызовы функций и присваивания становятся отдельными объектами. На этом этапе необходимо очистить дерево от несущественных шумов, чтобы дальнейшее сопоставление опиралось на чистую семантику.

• Удаление комментариев и строк документации происходит автоматически при синтаксическом разборе модуля ast, что сразу исключает один из каналов маскировки.
• Замена имён локальных переменных и аргументов функций на единые универсальные идентификаторы стирает разницу между исходным решением и вариантом с переименованными полями.
• Устранение информации о номерах строк и позициях символов переводит дерево в абстрактную форму, независимую от форматирования текста.

Выбор алгоритма вычисления дистанции

Сравнение деревьев требует выбора математического аппарата. Классический алгоритм Чжана — Шаша определяет минимальную стоимость операций вставки, удаления и переименования узлов для превращения одного дерева в другое. Его временная сложность в худшем случае составляет O(n1 * n2 * d1 * d2), где n — количество узлов, а d — глубина дерева. Для скриптов из 200 узлов такой расчёт выполняется за доли секунды, но для файлов на тысячи строк алгоритм потребует оптимизации.

В качестве практической альтернативы часто рассматривают сериализацию нормализованного дерева в плоский список токенов обходом в глубину. После обхода к полученной последовательности применяют классическое расстояние Левенштейна или сходство Жаккара на n-граммах поддеревьев. В проекте предстоит сопоставить эти подходы по точности и скорости работы на реальных примерах.

Критерии оценки проекта преподавателем

Преподаватель информатики оценивает работу по технической обоснованности решений. Главные критерии включают глубину проработки дерева и устойчивость детектора к типовым техникам обхода.

• Понимание объектной модели модуля ast и корректная фильтрация второстепенных атрибутов узлов показывают владение языком на уровне системного программирования.
• Обоснование вычислительной сложности выбранного алгоритма метрики подтверждает теоретическую подготовку по разделу алгоритмов и структур данных.
• Качество экспериментальной выборки и расчёт метрик точности на синтетических тестах демонстрируют завершённость прикладного исследования.

Сбор тестового корпуса и проведение экспериментов

Для проверки работоспособности программы нужен контролируемый набор данных. Использовать случайные файлы из интернета бессмысленно, так как на них невозможно точно измерить процент ложных срабатываний. Оптимальный массив данных формируют на основе решений типовых олимпиадных задач или задач с платформ вроде LeetCode и Яндекс Контест.

Корпус должен содержать три группы пар скриптов. Первая группа включает заведомо независимые решения одной задачи с разными алгоритмами. Вторая группа содержит исходный код и его копию, изменённую вручную через переименование переменных, перестановку независимых операторов и замену циклов for на while. Третья группа состоит из полностью идентичных файлов с разным стилем отступов.