АНАЛИЗ И ОПТИМИЗАЦИЯ РАБОТЫ СИСТЕМЫ ПОИСКА ПЛАГИАТА В ПРОГРАММНОМ КОДЕ

ANALYSIS AND OPTIMIZATION OF THE OPERATION OF THE PLAGIATOR SEARCH SYSTEM IN THE PROGRAM CODE

Tatiana Ogneva

student, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

Anna Kazachkova

Senior Lecturer, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

АННОТАЦИЯ

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

ABSTRACT

This article contains an analysis of the system of searching plagiarism in program code. The dependencies between program length pairs, similarity coefficients and working time of the system are studied using large number of solutions, the conclusions are drawn.

Ключевые слова: выявление плагиата в программном коде, расстояние Левенштейна, выравнивание строк, анализ данных.

Keywords: source code plagiarism detection, Levenstein distance, string alignment, data analysis.

Задача поиска плагиата в программном коде особенно актуальна в настоящее время для образовательного процесса, особенно для систем автоматической проверки задач. Существуют различные методы поиска плагиата в программном коде, каждый из них имеет свои достоинства и недостатки. Поэтому построение и исследование таких систем является важной задачей.

В данной работе рассматривается система проверки программного кода на наличие заимствований, основанная на методах расстояние Левенштейна и выравнивание строк [1].

Система была протестирована на программных кодах из системы автоматической проверки задач на сайте school.sgu.ru (всего 185 задач и 4900 решений к ним). Данный контестер используется для обучения программированию школьников и студентов и содержит более 800 задач начального и среднего уровней сложности.

Для оптимизации работы системы было проведено исследование времени проверки. В функцию попарной проверки программ были добавлены измерение времени с помощью библиотеки timeit и сохранение полученных результатов. Таким образом с помощью библиотеки pandas [2] был создан датасет с 17767 парами. Для каждой из пар записаны следующие сведения (представлены в соответствующих столбцах датасета):

• task - номер задачи;
• stud_1 - идентификатор первого студента;
• stud_2 - идентификатор второго студента;
• len_1 - длина обработанного решения первого студента;
• len_2 - длина обработанного решения второго студента;
• lev_coef - коэффициент схожести, рассчитанный с использованием метода Левенштейна;
• align_coef - коэффициент схожести, рассчитанный с помощью метода выравнивания;
• lev_time - время, затраченное на расчеты по методу Левенштейна;
• align_time - время, затраченное на расчеты по методу выравнивания.

Для исследования датасета и представления результатов использовались библиотеки pandas, pandas_profiling, numpy, matplotlib и seaborn.

Для каждой пары решений были подсчитаны и добавлены следующие сведения (представлены в соответствующих столбцах датасета):

• max_len - максимальная длина решения (из двух имеющихся);
• min_len - минимальная длина решения (из двух имеющихся);
• sum_len - сумма длин решений.

Далее для всех столбцов, кроме столбцов task, stud_1, stud_2 были посчитаны следующие характеристики: 

• минимальное значение;
• максимальное значение;
• среднее арифметическое;
• медиана.

Результаты для всех колонок представлены в таблице 1.

Таблица 1.

Числовые характеристики для некоторых столбцов датасета

Были выдвинуты гипотезы о зависимости между коэффициентами, рассчитанными каждым из методов, и временем выполнения обоих методов. Для наглядности результаты исследований визуализировались с помощью библиотек matplotlib и seaborn [3]. Визуализация представлена на рисунке 1. Видно, что в обоих случаях зависимость близка к линейной.

Рисунок 1. Попарные зависимости для времени выполнения и коэффициентов

Была выдвинута гипотеза о зависимости между коэффициентом схожести и временем выполнения для каждого из методов. Визуализация представлена на рисунке 2. Видно, что зависимости нет.

Рисунок 2. Зависимость между коэффициентом схожести и временем выполнения

Была выдвинута гипотеза о зависимости между максимальной длиной программы и временем выполнения для каждого из методов. Визуализация представлена на рисунке 3. Видно, что для метода выравниваний зависимости нет, для метода Левенштейна почти нет.

Рисунок 3. Зависимость между максимальной длиной программы и временем выполнения

Была выдвинута гипотеза о зависимости между минимальной длиной программы и временем выполнения для каждого из методов. Визуализация представлена на рисунке 4. Видно, что для метода выравниваний зависимости нет, для метода Левенштейна точки не расположены ниже какой-то кривой.

Рисунок 4. Зависимость между минимальной длиной программы и временем выполнения

Была выдвинута гипотеза о зависимости между суммарной длиной программ и временем выполнения для каждого из методов. Визуализация представлена на рисунке 5. Видно, что для метода выравниваний зависимости нет, для метода Левенштейна точки не расположены около какой-то кривой.

Рисунок 5. Зависимость между суммой длин программ и временем выполнения

Для исследования линейной зависимости между столбцами была построена корреляционная матрица. Для наглядности она была визуализирована с помощью теплокарты. Визуализация представлена на рисунке 6.

Рисунок 6. Теплокарта корреляционной матрицы столбцов датасета

Можно сделать следующие выводы:

1. Время выполнения с помощью разных методов похоже — коэффициент корреляции 0.86.
2. Самая высокая зависимость между временем для метода Левенштейна и суммарной длины.
3. Затем идет зависимость между временем для метода Левенштейна и максимальной длиной.
4. Между методом Левенштейна и минимальной длиной тоже есть зависимость, чуть меньше, чем в предыдущих случаях.
5. Следующая — зависимость между временем выполнения для метода Левенштейна и длинами программ.
6. Для метода выравниваний коэффициенты меньше 0.8, зависимости почти нет.

Список литературы:

1. Огнева Т.А. Использование методов “Расстояние Левенштейна и выравнивания строк для поиска плагиата в программном коде // Научное сообщество студентов: Междисциплинарные исследования: сб. ст. по мат. CXXXI междунар. студ. науч.-практ. конф. № 24(131). URL: https://sibac.info/archive/meghdis/24(131).pdf (дата обращения: 18.12.2022)
2. Wes MacKinney and the Pandas Development Team pandas: powerful Python data analysis toolkit Release 1.4.2
3. Лемешевский С. В. Графическая визуализация данных, С. 1-9, 21