Поиск плагиата в решениях
Описание
На странице Дополнительные функции/Плагиат (admin_plagiarism.cgi) у администраторов олимпиады (а именно, требуются такие же привилегии, как на страницу Отчет) есть возможность посмотреть, какие из отправленных участниками олимпиады решений подозрительно похожи друг на друга и, скорее всего, получены нечестным путём.
Технические подробности
Модуль состоит из двух частей: собственно страницы admin_plagiarism.cgi, предоставляющей веб-интерфейс, и модулей Nsuts_new/Plagiarism/*, реализующих логику выявления плагиата.
admin_plagiarism.cgi
Для каждой задачи в текущем туре, по которой сданы плагиатные решения, выводит таблицу: список похожих решений и метрика их похожести («вероятность»). Метрика варьируется от 0 (решения совсем не похожи) до 1 (решения одинаковы с точностью до пробелов, комментариев и переобозначений переменных), но в таблице показаны только списки с метрикой больше заданного порога (по умолчанию 0.85).
Если список плагиата строится дольше 16 секунд, то покажется только та часть, которая успела найтись за это время, и ссылка, позволяющая увеличить отводимое время в 2 раза.
Страница принимает два «недокументированных» get-параметра:
- timeout – максимальное время в секундах, отводимое на поиск плагиата
- confidence – минимальное значения метрики похожести решений для включения их в таблицу.
Plagiarism::Plagiarism.pm
Основная функция – findPlagiarism. Вначале для каждого решения (от каждого участника рассматривается только последнее посланное по каждой задаче решение) вычисляется его хэш и отпечаток с помощью модуля Plagiarism::TaskHash.pm (по алгоритму, основанному на
описанном А. Г. Фенстером) и находятся все решения, отличающиеся только пробелами, комментариями и переименнованными переменными: им присваивается метрика 1. Затем для каждого решения с помощью Plagiarism::WinnowingMethod.pm вычисляется набор хэш-значений (по алгоритму,
найденному в интернете и называемому метод просеивания (winnowing) для метода отпечатков) и решения с общими хэш-значениями помечаются как подозрительные на плагиат. Наконец, для всех решений, подозрительных на плагиат, подозрения проверяются с помощью более медленного, но точного сравнения (подойдет любой метод сравнения «похожести» строк: длина
наибольшей общей подпоследовательности или
расстояние Левенштейна) и им назначается соответствующая метрика.
Недостатки & TODO
- Несмотря на применение различных методов, на больших турах работает довольно медленно :[
- В списке плагиата показываются и решения, сданные жюри и администраторами (нужно ли это?)
- Возможность задавать произвольный таймаут и порог метрики доступны только прописыванием get-параметров вручную
- Более наглядное предстваление результатов (двумерная таблица?, графики?)
- Все TODO и FIXME в Plagiarism::Plagiarism.pm
