Обнаружение кластеров «похожих» исходников

10

Предположим, у меня 400 студентов (это в большом университете), которые должны заниматься компьютерными проектами, и что они должны работать в одиночку (без группы студентов). Примером проекта может быть «реализация алгоритма быстрого преобразования Фурье в Фортране» (я знаю, это не звучит сексуально, но это упрощает мой вопрос). Я корректор, и я хочу отправить процедуры, чтобы проверить, есть ли группы студентов, которые предложили реализацию, которые «слишком похожи, чтобы быть действительно независимыми».

Это неконтролируемый поиск кластеров. Я думаю, что вопрос больше в том, какие атрибуты использовать, а не в том, какой алгоритм кластеризации использовать. Первое, что я бы сделал, - это гистограмма по буквам. В идеале, так как читеры умнее этого, я бы в конечном итоге попробовал правильно подобранные случайные перестановки букв, чтобы посмотреть, существует ли хорошее совпадение гистограммы букв (с перестановкой). Кроме того, те, кто не изучает структуру кода, а только предельное распределение букв ... какое решение у вас есть? Существуют ли программы или пакеты, предназначенные для этой проблемы? (на самом деле в мои старые времена преподаватели информатики утверждали, что у них есть такой инструмент, но теперь я подозреваю, что у них было что-то очень простое)

Думаю, у юриста из разработчиков программного обеспечения тоже есть проблемы такого типа (не с 1000 студентами, а с двумя большими кодами ... что еще сложнее)?

hypothesis-testing clustering Робин Жирар
источник

Ответы:

4

Очевидный шаг предварительной обработки - объединить файлы, которые действительно идентичны.

После этого ключ нормализации . В какой-то момент студенты начнут рефакторинг кода, переименование переменных и тому подобное. Или перефразируйте комментарии. Буквенная гистограмма слишком сильно зависит от этого (плюс она будет охватывать много языковых свойств).

Общепринятым методом является использование специфичного для языка синтаксического анализатора и преобразование исходного кода в абстрактное синтаксическое дерево. Тогда извлеките особенности из этого. И, возможно, анализировать комментарии отдельно параллельно.

Тогда есть основанный на линии подход "самой длинной общей подпоследовательности". Если у вас достаточно хорошее сходство в отдельных строках, вы можете искать самую длинную общую подпоследовательность из любых двух файлов. Это также приведет к ряду совпадений.

ВЫЙТИ - Anony-Mousse
источник
Просто хотел добавить, что самую длинную общую подпоследовательность можно эффективно найти с помощью суффикс-деревьев или суффикс-массивов.
2012 г.
Спасибо Anony, мне очень нравится дух твоего ответа (и проголосовал за него). Это звучит как настоящая многомерная статистика с «преобразованием данных» и поиском экстремальных паттернов. Какое расстояние вы бы поставили на эти деревья?
Робин Жирар
Я не эксперт по сходству представлений AST. Я считаю, что существует понятие «симуляции» в том смысле, что одно дерево является особым видом поддерева другого. Я думаю, что для сравнения AST вам нужно выровнять их и подсчитать относительные различия. Возможно, не принимается во внимание порядок ветвей, поэтому тривиальные перестановки кода не изменяют результаты. Имейте в виду, что вы можете дойти до точки, где вы получите ложные срабатывания, потому что есть только n способов эффективного решения проблемы, и вы получите ложные срабатывания только потому, что они нашли правильное решение ...
Имеет QUIT - Anony-Mousse
0

Из мира анти-плагиата я раньше сталкивался с понятием «Изоморфизм графов». Может быть, вы тоже можете посмотреть на это.

LCS - возможна также самая длинная общая подпоследовательность. Но попробуйте сравнить все эти решения и посмотреть, что лучше :)

Исми Наджми
источник
Добро пожаловать на этот сайт! Не могли бы вы дать некоторые ссылки на вышеупомянутую работу, и, возможно, более подробную информацию, чтобы читатели могли получить лучшее представление о том, как изоморфизм графов или LCS может решить проблему под рукой?
ЧЛ