Программная реализация модуля PlagiatSearch поиска плагиата методами сравнения произвольных текстов

18,18%

18,18%

81,82%

45,45%

9,09%

98,00%

93,00%

85,00%

96,00%

91,00%

82,00%

71,00%

76,00%

21,00%

97,30%

59,46%

48,65%

83,78%

37,84%

35,14%

67,57%

29,73%

10,81%

100,00%

25,00%

25,00%

0,00%

0,00%

0,00%

100,00%

25,00%

25,00%

100,00%

0,00%

0,00%

0,00%

0,00%

0,00%

100,00%

0,00%

0,00%

70,59%

52,94%

17,65%

52,94%

29,41%

17,65%

52,94%

35,29%

0,00%

Относительные значения в виде столбиковых диаграмм показаны на рисунке 21:

Рисунок 21 Относительные значения в виде столбиковых диаграмм

6.3.5.1 Исследование итогового протокола по полученным диаграммам Excel

Проанализируем полученные результаты. При этом мы не будем учитывать годы 2002, 2006,2009,2010,2011, так как мы имеем недостаточное количество работ по этим годам. Будем учитывать только 2004, 2005, 2007,2008 год.

· С - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ БЕЗ УЧЕТА ГОДОВ: незначительный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

· D - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ БЕЗ УЧЕТА ГОДОВ: ярко выраженный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

· E - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ БЕЗ УЧЕТА ГОДОВ: ярко выраженный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

· F - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ В ОДНОМ И ТОМ ЖЕ ГОДУ: ярко выраженный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году. Видимо курс был либо очень «дружный» либо очень слабый, и поэтому студенты активно списывали друг у друга.

· G - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ В ОДНОМ И ТОМ ЖЕ ГОДУ: ярко выраженный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году. Видимо, курс был либо очень «дружный» либо очень слабый, и поэтому студенты активно списывали друг у друга.

· H - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ В ОДНОМ И ТОМ ЖЕ ГОДУ: ярко выраженный пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году. Видимо, курс был либо очень «дружный» либо очень слабый, и поэтому студенты активно списывали друг у друга.

· I - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ: пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

· J - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ: пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

· K - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ: пик процента подозрительных программ к общему числу проанализированных программ наблюдается в 2007 году.

6.3.6 Экспорт списка первоисточников в Excel

Ниже (таблица 10 в Приложении 5) приведен список первоисточников в первоначальном виде и без дубликатов, полученный после экспорта в Excel. Красным цветом выделены (но здесь показаны не все) программы студентов, которые явно (с большой долей вероятности) были списаны с других программ.

6.3.6.1 Исследование списка первоисточников в Excel

Число первоисточников без дубликатов - 211, а число изучаемых файлов - 283. Отсюда можно сделать вывод о том, что хотя плагиат присутствует в работах студентов, но он достаточно невелик (около 25%). B 75% случаев студент сам пишет программы.

Полученное число первоисточников равное 211 хорошо согласуется с другими данными проведенного анализа. А именно, если посмотрим на сумму в столбце E, равную 144: в этом столбце приведены данные о числе работ, в которых найдены признаки плагиата по двум критериям. Учтем, что фактически число работ с плагиатом здесь учтены дважды, поэтому реальное число списанных работ равно 72. Если вычесть это число из общего числа работ, то как раз и получим полученное число первоисточников равное 211.

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

6.4 Пример работы модуля

Примеры работа программы даны на основе базы работ студентов по предмету «Защита информации», сданных в ВУЗе. База содержит не все работы прошлых лет, а только некоторые, сохранившиеся у преподавателя, однако это не помешало обнаружить плагиат.

6.4.1 Пример 1 анализа последовательности операторов

Пример 1 анализа последовательности операторов приведен на рисунке 22.

Рисунок 22 Пример 1 анализа последовательности операторов

Отчет программы:

Максимальное совпадение последовательности операторов в файлах обнаружено в 1 файле с 50 по 71 строку, во 2 файле c 59 по 81 строку.

*************** 1 Файл: ***************

if (Static3!=NULL) Static3->Create("Результат",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(495,5,880,20),this);

Edit3 = new CEdit();

if (Edit3!=NULL) Edit3->Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_MULTILINE, CRect(60,530,590,550),this,IDC_EDIT3);

Static1 = new CStatic();

if (Static1!=NULL) Static1->Create("Ключ",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(10,530,60,550),this);

Button1 = new CButton();

if (Button1!=NULL) Button1->Create("Шифрование",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(60,560,230,580),this,IDC_BUTTON1);

Button2 = new CButton();

if (Button2!=NULL) Button2->Create("Выход",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,600,780,620),this,IDC_BUTTON2);

Button3 = new CButton();

if (Button3!=NULL) Button3->Create("Таблица Вижинера",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,530,780,550),this,IDC_BUTTON3);

Button4 = new CButton();

if (Button4!=NULL) Button4->Create("Расшифровать ключом",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(240,560,410,580),this,IDC_BUTTON4);

Button6 = new CButton();

if (Button6!=NULL) Button6->Create("<<",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(400,250,490,300),this,IDC_BUTTON6);

*************** 2 Файл: ***************

if (Static2!=NULL) Static2->Create("Исходный текст",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(10,5,395,20),this);

Static3 = new CStatic(); // это заголовок правого окна - "Результат"

if (Static3!=NULL) Static3->Create("Результат",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(495,5,880,20),this);

Edit3 = new CEdit(); // аналогично Edit1 - это текстовое поле для ключа

if (Edit3!=NULL) Edit3->Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_MULTILINE, CRect(60,530,590,550),this,IDC_EDIT3);

Static1 = new CStatic(); // аналогично для Static2 - это поле "Ключ" справа от текстового поля для ключа

if (Static1!=NULL) Static1->Create("Ключ",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(10,530,60,550),this);

// Кнопка Шифрование - делается аналогично предыдущим элеменат, только создается объекст CButton

Button1 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON1

if (Button1!=NULL) Button1->Create("Шифрование",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(60,560,230,580),this,IDC_BUTTON1);

Button2 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON2

if (Button2!=NULL) Button2->Create("Выход",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,600,780,620),this,IDC_BUTTON2);

Button3 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON3

if (Button3!=NULL) Button3->Create("Генерация ключа",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,530,780,550),this,IDC_BUTTON3);

Button4 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON4

if (Button4!=NULL) Button4->Create("Расшифровать ключом",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(240,560,410,580),this,IDC_BUTTON4);

+++ Информация о файлах +++

_______________ 1 Файл: _______________

С

Группа: ВВ-5-02

Тема: Крипт2

Автор: Боловинцев

Дополнительная информация:

Путь: C:\Documents and Settings\Владимир\Рабочий стол\BAZA\Лабы\VV-5-02\bolovincev\Crypt2\Crypt.cpp

Размер: 7288 Байт

Изменен: 18.04.2006 13:00:44

_______________ 2 Файл: _______________

С

Группа: ВВ-5-02

Тема: крипт1

Автор: Ахметов

Дополнительная информация:

Путь: C:\Documents and Settings\Владимир\Рабочий стол\BAZA\Лабы\VV-5-02\KomissandAhmetov\мис зки\1Crypt(comment)\Crypt(comment)\Crypt.cpp

Размер: 17448 Байт

Изменен: 24.03.2006 14:53:34

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

6.4.2 Пример 2 автоматического анализа частот появления операторов

Пример 2 автоматического анализа частот появления операторов показан на рисунке 23.

Рисунок 23 Пример 2 автоматического анализа частот появления операторов

7 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДУЛЯ PLAGIATSEARCH ПОИСКА ПЛАГИАТА МЕТОДАМИ СРАВНЕНИЯ ПРОИЗВОЛЬНЫХ ТЕКСТОВ

7.1 Интерфейс модуля PlagiatSearch поиска плагиата методами сравнения произвольных текстов

7.1.1 Главное окно модуля PlagiatSearch поиска плагиата методами сравнения произвольных текстов

Модуль PlagiatSearch поиска плагиата методами сравнения произвольных текстов реализован на языке программирования - Delphi. В верхней части диалогового окна (рисунок 24) находится панель меню (1), ниже панель быстрого доступа к наиболее важным функциям меню (2), в правом верхнем углу после выполнения некоторых действий. Главное окно в средней части - это тексты сравниваемых текстовых файлов с номерами строк (3). В самом низу находятся информация с некоторыми комментариями по выполненным действиям (4). Важным элементом интерфейса является checkbox `Текст' в левой верхней части окна: если флажок установлен, то сравниваемые файлы рассматриваются как произвольные тексты (рисунок 24, a) и тогда их выбор можно осуществлять либо через опцию меню “Файл” или через пиктораммы `1' или `2' на панели быстрого доступа (5).

Меню «Файл» позволяет выполнять основные функции работы с файлами: открыть сравниваемые файлы (6), сравнить по Левенштейну (7) и методом шинглов (8). Для исходных кодов можно также выполнить операцию токенизации (смотрите раздел 4.8). Меню «Просмотр» предлагает удобные средства перемещения по файлу («Перемещается по измененным частям сравниваемых файлов» и на указанные строки в файлах). Меню «Опции и параметры» позволяют задать параметры сравнения файлов по Левенштейну (игнорировать - Регистры и пробелы), задать весовые коэффициенты Дамерау и размер шинглов. Меню «Методы сравнения» задает один из реализованных алгоритмов вычисления дистанции Левенштейна (O(NP) [29] или O(ND) [28]).

Если флажок не установлен (как на рисунке 24, b), то сравниваемые файлы рассматриваются как тексты исходных кодов и тогда выбор возможен только из базы данных исходных кодов (8). При этом можно выбрать язык программирования (9).

Рисунок 24 Главное окно модуля PlagiatSearch поиска плагиата методами сравнения произвольных текстов

Первый и основной алгоритм O(NP) [29], реализованный в дипломе и являющийся модификацией алгоритма Вагнера-Фишера, позволяет в большинстве случаев почти в два раза сократить время выполнения по сравнению с алгоритмом O(ND) [28]. Пусть A и B будет две последовательности длины M и N соответственно, где без потери общности N >=M, и пусть D - длина кратчайшего сценария редактирования между ними (shortest edit script). Параметр P, связанный с D - это количество удалений в таком сценарии, P = D/2 ?(N ?M)/2. Алгоритм нахождения кратчайшего расстояния редактирования A и B имеет в худшем случае время выполнения O(NP) и чьи ожидаемое время O (N +PD). Алгоритм прост и является очень эффективным, особенно когда A похож на B. То есть, как раз в случае подозрений на плагиат.

Второй алгоритм O(ND) [28], реализованный в дипломе и являющийся модификацией алгоритма Вагнера-Фишера, имеет ожидаемое время выполнения O(ND), где N - сумма длин последовательностей A и B, а D - длина кратчайшего сценария редактирования между ними.

7.1.2 Меню «Анализ» и его возможности для поиска плагиата в произвольных текстах

Меню «Анализ» (рисунок 25) становится доступным и применяется после выполнения сравнения произвольных текстов по Левенштейну.

Рисунок 25 Меню «Анализ»

Это меню включает следующие опции:

· Вычислить расстояние Левенштейна;

Результат вычисления этого расстояния может интерпретироваться следующим образом: если оно мало, то можно предположить, что второй файл получается из первого файла за минимальное число действий (удаление-изменение-добавление).

· Вычислить расстояние Дамерау;

Результат вычисления этого расстояния может интерпретироваться следующим образом: если оно мало, то можно предположить, что второй файл получается из первого файла за минимальное число действий с весовыми коэффициентами (удаление-изменение-добавление). В отличие от простого расстояния Левенштейна расстояние Дамерау позволяет учитывать при поиске плагиата разный вес действий. Например, можно считать, что «добавление» имеет меньшее значение с точки зрения поиска плагиата, чем изменение. Поэтому в этом случае весовой коэффициент операции «добавления» должен быть больше, чем весовой коэффициент операции «изменение». Чем больше операций «добавление» при сравнении файлов и вычислении для них расстояния Дамерау, тем больше будет значение расстояния Дамерау. Следовательно, тем менее похожими можно считать сравниваемые файлы.

· Вычислить длину LCS (наибольшей общей подпоследовательности, longest common subsequence)

· Показать все совпадающие строки

Смысл введения этой опции следующий: показать, для каждой строки в файле 1 ее дубликаты, которые есть во втором файле. В информационном окне наличие дубликатов представляется следующим образом: если для строки файла 1 есть идентичные строки в файле 2, то они указаны в квадратных скобах через знак равенства. Например, для строки с номером 71 в файле 1 есть идентичная строка в файле 2 с номером 34: [71]=[34] . Кроме того, после выполнения операции поиска совпадающих строк вычисляется длина и место максимального непрерывного фрагмента совпадающих строк (Максимальная длина в строках непрерывного фрагмента совпадающих строк ->5 со строки 33) и фокус в главном окне модуля переводится на это место (рисунок 26). В нашем случае этот фрагмент начинается со строки 33 и имеет длину 5 строк.

Рисунок 26 Поиск всех совпадающих строк в файлах и показ максимального непрерывного фрагмента совпадающих строк

Пример результата в информационном окне показан ниже (синим цветом).

Совпадающие строки в файле 1 и в файле 2:

[2]=[2] [2]=[4] [2]=[7] [2]=[23] [2]=[26] [2]=[28] [2]=[30] [2]=[32] [2]=[38]

[3]=[3]

[4]=[2] [4]=[4] [4]=[7] [4]=[23] [4]=[26] [4]=[28] [4]=[30] [4]=[32] [4]=[38]

[8]=[2] [8]=[4] [8]=[7] [8]=[23] [8]=[26] [8]=[28] [8]=[30] [8]=[32] [8]=[38]

[9]=[8]

[13]=[22]

[33]=[18]

[34]=[19]

[35]=[20]

[36]=[21]

[37]=[22]

[41]=[2] [41]=[4] [41]=[7] [41]=[23] [41]=[26] [41]=[28] [41]=[30] [41]=[32] [41]=[38]

[42]=[2] [42]=[4] [42]=[7] [42]=[23] [42]=[26] [42]=[28] [42]=[30] [42]=[32] [42]=[38]

[43]=[24]

[45]=[2] [45]=[4] [45]=[7] [45]=[23] [45]=[26] [45]=[28] [45]=[30] [45]=[32] [45]=[38]

[51]=[2] [51]=[4] [51]=[7] [51]=[23] [51]=[26] [51]=[28] [51]=[30] [51]=[32] [51]=[38]

[52]=[31]

[55]=[34]

[61]=[2] [61]=[4] [61]=[7] [61]=[23] [61]=[26] [61]=[28] [61]=[30] [61]=[32] [61]=[38]

[63]=[37]

[65]=[34]

[67]=[37]

[71]=[34]

[76]=[2] [76]=[4] [76]=[7] [76]=[23] [76]=[26] [76]=[28] [76]=[30] [76]=[32] [76]=[38]

[77]=[2] [77]=[4] [77]=[7] [77]=[23] [77]=[26] [77]=[28] [77]=[30] [77]=[32] [77]=[38]

[78]=[2] [78]=[4] [78]=[7] [78]=[23] [78]=[26] [78]=[28] [78]=[30] [78]=[32] [78]=[38]

[79]=[37]

[82]=[34]

[85]=[2] [85]=[4] [85]=[7] [85]=[23] [85]=[26] [85]=[28] [85]=[30] [85]=[32] [85]=[38]

[86]=[37]

[88]=[34]

[90]=[37]

[91]=[2] [91]=[4] [91]=[7] [91]=[23] [91]=[26] [91]=[28] [91]=[30] [91]=[32] [91]=[38]

[93]=[34]

[101]=[37]

[102]=[2] [102]=[4] [102]=[7] [102]=[23] [102]=[26] [102]=[28] [102]=[30] [102]=[32] [102]=[38]

[109]=[2] [109]=[4] [109]=[7] [109]=[23] [109]=[26] [109]=[28] [109]=[30] [109]=[32] [109]=[38]

[125]=[2] [125]=[4] [125]=[7] [125]=[23] [125]=[26] [125]=[28] [125]=[30] [125]=[32] [125]=[38]

[131]=[2] [131]=[4] [131]=[7] [131]=[23] [131]=[26] [131]=[28] [131]=[30] [131]=[32] [131]=[38]

[132]=[2] [132]=[4] [132]=[7] [132]=[23] [132]=[26] [132]=[28] [132]=[30] [132]=[32] [132]=[38]

[134]=[37]

[135]=[2] [135]=[4] [135]=[7] [135]=[23] [135]=[26] [135]=[28] [135]=[30] [135]=[32] [135]=[38]

[139]=[34]

[151]=[2] [151]=[4] [151]=[7] [151]=[23] [151]=[26] [151]=[28] [151]=[30] [151]=[32] [151]=[38]

[154]=[37]

[155]=[2] [155]=[4] [155]=[7] [155]=[23] [155]=[26] [155]=[28] [155]=[30] [155]=[32] [155]=[38]

[156]=[39]

Всего найдено совпадающих строк в файле 1 и в файле 2 ->215

Максимальная длина в строках непрерывного фрагмента совпадающих строк ->5 со строки 33

· Показать все удаленные в файле 1 строки, которые были добавлены в файле 2.

Смысл введения этой опции следующий: некоторые удаленные из файла 1 строки могут быть просто перемещены в другое место в файле 2. При сравнении файлов по Левенштейну это подозрительное с точки зрения поиска плагиата действие не будет обнаружено. В информационном окне это представляется следующим образом: если для удаленной строки файла 1 есть добавленные строки в файле 2, то они указаны в квадратных скобах через знак равенства. Например, для удаленной строки с номером 52 в файле 1 есть добавленная строка в файле 2 с номером 31: [52]=[31].

Пример результата в информационном окне показан ниже (синим цветом).

Удаленные строки в файле 1 среди добавленных в файле 2:

[41]=[2] [41]=[4] [41]=[7] [41]=[23] [41]=[26] [41]=[28] [41]=[30] [41]=[32] [41]=[38]

[51]=[2] [51]=[4] [51]=[7] [51]=[23] [51]=[26] [51]=[28] [51]=[30] [51]=[32] [51]=[38]

[52]=[31]

[55]=[34]

[61]=[2] [61]=[4] [61]=[7] [61]=[23] [61]=[26] [61]=[28] [61]=[30] [61]=[32] [61]=[38]

[63]=[37]

[65]=[34]

[67]=[37]

[71]=[34]

[76]=[2] [76]=[4] [76]=[7] [76]=[23] [76]=[26] [76]=[28] [76]=[30] [76]=[32] [76]=[38]

[77]=[2] [77]=[4] [77]=[7] [77]=[23] [77]=[26] [77]=[28] [77]=[30] [77]=[32] [77]=[38]

[78]=[2] [78]=[4] [78]=[7] [78]=[23] [78]=[26] [78]=[28] [78]=[30] [78]=[32] [78]=[38]

[79]=[37]

[82]=[34]

[85]=[2] [85]=[4] [85]=[7] [85]=[23] [85]=[26] [85]=[28] [85]=[30] [85]=[32] [85]=[38]

[86]=[37]

[88]=[34]

[90]=[37]

[91]=[2] [91]=[4] [91]=[7] [91]=[23] [91]=[26] [91]=[28] [91]=[30] [91]=[32] [91]=[38]

[93]=[34]

[101]=[37]

[102]=[2] [102]=[4] [102]=[7] [102]=[23] [102]=[26] [102]=[28] [102]=[30] [102]=[32] [102]=[38]

[109]=[2] [109]=[4] [109]=[7] [109]=[23] [109]=[26] [109]=[28] [109]=[30] [109]=[32] [109]=[38]

[125]=[2] [125]=[4] [125]=[7] [125]=[23] [125]=[26] [125]=[28] [125]=[30] [125]=[32] [125]=[38]

[135]=[2] [135]=[4] [135]=[7] [135]=[23] [135]=[26] [135]=[28] [135]=[30] [135]=[32] [135]=[38]

[139]=[34]

[151]=[2] [151]=[4] [151]=[7] [151]=[23] [151]=[26] [151]=[28] [151]=[30] [151]=[32] [151]=[38]

[154]=[37]

Всего найдено удаленных строк в файле 1 среди добавленных в файле 2 ->132

7.1.3 Информационное окно модуля PlagiatSearch поиска плагиата в произвольных текстах с результатами вычисления дистанции Левенштейна

Результаты вычисления дистанции Левенштейна в информационном окне имеют следующую структуру (покажем на конкретном примере):

Расстояние Левенштейна =254

Число строк: в файле 1 =332; в файле 2 =227

Совпадает : 73;

Изменено : 146;

Добавлено : 8;

Удалено : 113;

Комментарий к средней части главного окна:

Совпадает (N, белый), Изменено (M, зеленый), Добавлено (A, голубой), Удалено (D, красный)

Решение (по Левенштейну)

[1]N [2]N [3]N [4]N [5]N [6]N [7]M [8]N [9]N [10]N

[11]N [12]N [13]N [14]N [15]M [16]M [17]M [18]M [19]M [20]M

[21]D [22]D [23]D [24]D [25]N [26]N [27]M [28]M [29]M [30]M

[31]M [32]M [33]M [34]M [35]N [36]N [37]N [38]N [39]N [40]N

[41]N [42]N [43]N [44]N [45]N [46]N [47]N [48]M [49]N [50]D

[51]D [52]D [53]D [54]D [55]D [56]D [57]D [58]N [59]N [60]N

[61]N [62]N [63]M [64]D [65]D [66]N [67]N [68]A [69]N [70]N

[71]M [72]M [73]D [74]N [75]D [76]D [77]D [78]D [79]D [80]D

[81]D [82]N [83]M [84]A [85]N [86]D [87]D [88]D [89]D [90]D

[91]D [92]D [93]D [94]D [95]D [96]D [97]D [98]D [99]D [100]D

[101]D [102]D [103]D [104]D [105]D [106]D [107]D [108]D [109]N [110]M

[111]M [112]M [113]M [114]M [115]M [116]M [117]D [118]D [119]D [120]D

[121]D [122]D [123]D [124]N [125]D [126]D [127]D [128]D [129]D [130]D

[131]N [132]N [133]M [134]N [135]N [136]N [137]N [138]N [139]N [140]N

[141]N [142]N [143]N [144]N [145]N [146]N [147]N [148]M [149]M [150]M

[151]M [152]M [153]M [154]M [155]M [156]M [157]M [158]M [159]M [160]M

[161]M [162]M [163]M [164]M [165]M [166]M [167]M [168]M [169]D [170]D

[171]D [172]D [173]D [174]D [175]D [176]D [177]D [178]D [179]D [180]D

[181]D [182]D [183]D [184]D [185]D [186]N [187]M [188]M [189]M [190]M

[191]M [192]M [193]M [194]M [195]M [196]M [197]M [198]A [199]A [200]A

[201]N [202]M [203]M [204]M [205]A [206]N [207]N [208]M [209]N [210]M

[211]M [212]M [213]M [214]M [215]N [216]N [217]M [218]M [219]M [220]M

[221]M [222]M [223]M [224]M [225]M [226]M [227]M [228]M [229]M [230]M

[231]M [232]M [233]M [234]M [235]M [236]M [237]M [238]M [239]M [240]M

[241]M [242]M [243]D [244]D [245]D [246]D [247]N [248]M [249]M [250]D

[251]D [252]D [253]N [254]M [255]M [256]M [257]M [258]M [259]M [260]M

[261]M [262]M [263]M [264]M [265]M [266]M [267]M [268]M [269]M [270]M

[271]M [272]M [273]M [274]M [275]M [276]M [277]M [278]D [279]D [280]D

[281]D [282]D [283]D [284]D [285]D [286]D [287]D [288]D [289]D [290]D

[291]D [292]D [293]D [294]D [295]D [296]D [297]D [298]D [299]D [300]D

[301]D [302]D [303]D [304]D [305]D [306]D [307]D [308]N [309]M [310]M

[311]M [312]M [313]M [314]M [315]M [316]M [317]M [318]M [319]M [320]M

[321]M [322]M [323]M [324]M [325]M [326]M [327]M [328]M [329]M [330]M

[331]M [332]M [333]M [334]A [335]N [336]D [337]N [338]N [339]N [340]A

Результаты имеют следующий смысл: показаны последовательные действия со строками (начиная с первой и до последней), которые выполняются над строками первого текстового файла для того, чтобы получить второй текстовый файл:

· Cимволом N (и белым цветом в главном окне модуля) обозначается строка в первом файле, которая переносится во второй файл без изменений. Число таких строк - это длина наибольшей общей подпоследовательности (longest common subsequence, LCS). Также это число показано в строке «Совпадает» (в нашем примере - 73).

· Cимволом M (и зеленым цветом в главном окне модуля) обозначается строка в первом файле, которая переносится во второй файл с изменениями;

· Cимволом A (и голубым цветом в главном окне модуля) обозначается добавленная к первому файлу строка (которой, естественно, не было в первом файле, но которая была во втором файле ), которая переносится во второй файл без изменений;

· Cимволом D (и красным цветом в главном окне модуля) обозначается строка в первом файле, которая была из него удалена и которой теперь не будет во втором файле

Как нетрудно видеть, число номеров (в нашем случае - 340) в результате вычисления дистанции Левенштейна равно сумме числа строк в первом файле (в нашем примере - 332) плюс число добавленных строк (в нашем случае 8).

7.1.4 Представление результатов нахождения наибольшей общей подпоследовательности (longest common subsequence, LCS)

При вычислении дистанции Левенштейна одновременно получается наибольшая общая подпоследовательность (longest common subsequence, LCS) двух сравниваемых файлов. В основном окне модуля наибольшая общая подпоследовательность - это все строки белого цвета. То есть все строки, которые одновременно входят без каких-либо изменений в оба файла. Длина LCS - это число строк белого цвета в главном окне модуля. Также это число показано в строке «Совпадает» (в нашем примере на - 73).

7.1.5 Представление метода шинглов для сравнения произвольных текстов

Результатом сравнения файлов методом шинглов является одно число - процент одинаковых шинглов в обеих файлах. Если этот процент велик (например, 50%), то возникает подозрение на плагиат. При этом, конечно, этот процент зависит от длины шингла и показывается в информационном окне при применении метода. В реализованном модуле можно самостоятельно выбирать длину шингла (Рисунок 27).

Рисунок 27 Выбор длины шинглов

7.1.6 Применение метода шинглов для сравнения исходных кодов

Метод шинглов для сравнения исходных кодов может применяться как к самим исходным текстам (рисунок 28), так и к токенизированному представлению (рисунки 29, 30). Белым цветом показаны шинглы, которые имеют дубликаты в другом сравниваемом файле.

Рисунок 28 Сравнение исходных кодов методом шинглов

Рисунок 29 Токенизированное представление исходных кодов

Рисунок 30 Сравнение токенизированного представления исходных кодов методом шинглов

ЗАКЛЮЧЕНИЕ

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

1) Усовершенствованы инструментальные средства анализа исходных кодов программ в части реализации возможностей наглядной визуальной оценки проверяющим;

2) Реализован набор инструментов анализа исходных кодов программ, который состоит из двух взаимно дополняющих модулей: первый анализирует исходный код методами анализа исходных кодов, а второй позволяет анализировать этот же исходный код методами анализа произвольных текстов.

3) В работе предложен и реализован в виде самостоятельного модуля алгоритм поиска заимствованных фрагментов в исходных кодах программ, интегрирующий структурный анализ кодов (на основе токенов) и методы шинглов, дистанции Левенштейна и наибольшей общей подпоследовательности (longest common subsequence, LCS) для анализа произвольных текстов.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ (БИБЛИОГРАФИЧЕСКИЙ СПИСОК)

1. Макаров В.В. Идентификация заимствований в прикладных программах, ИПУ РАН, УДК 001(06), Телекоммуникационные и новые информационные технологии.

2. Макаров В.В. Идентификация дублирования и плагиата в исходном тексте прикладных программ - Москва: Институт проблем управления РАН, 1999.

3. Красс А. Обзор автоматических детекторов плагиата в программах. http://detector.spb.su/pub/Sandbox/ReviewAlgorithms/survey.pdf .

4. Синельников С.М. и др. Энциклопедия предпринимателя - Санкт-Петербург, 1994.

5. Сухарев А.Я., Крутских В.Е. Большой юридический словарь (редакция) - Москва, 2002.

6. Брокгауз, Ефрон. Малый энциклопедический словарь.

7. Большая советская энциклопедия.

8. Литературная энциклопедия.

9. Нейл К., Шанмагантан Г. http://osmag.ru , 2004-2005.

10. Иванчегло С. Методы выявления плагиата в программировании: http://www.kv.by/index2000491105.htm , 2000.

11. Лифшиц Ю., Антипов Д., Евтифеева О.А., Котов А., Красс А.Л., Лакунин М.А., Лысенко Е.А., Семенников А., Счастливцев Р.Р. Обзор алгоритмов и детекторов обнаружения плагиата в исходных кодах программ. http://detector.spb.su - Санкт-Петербург, 2006.

12. http://www.antiplagiat.ru/ , 2005-2007.

13. http://neuroshell.forekc.ru/ .

14. Etxt Антиплагиат. Программа проверки уникальности текста.

15. Double Content Finder: http://textbroker.ru/main/dcfinder.html .

16. Детектор Плагиата: http://www.detector-plagiata.ru .

17. Прохоров А. Интернет: источник плагиата или средство его выявления? http://2balla.ru/content/view/1891/87/ .

18. Крутояров Д.В. Автоматизированная система поиска заимствований в электронных изданиях, опубликованных в сети Интернет. http://www.dissercat.com/content/avtomatizirovannaya-sistema-poiska-zaimstvovanii-v-elektronnykh-izdaniyakh-opublikovannykh-v .

19. Фенстер А.Г. Выявление плагиата при проверке студенческих программ. http://info.fenster.name/ .

20. Уникальность текста и как проверить текст на уникальность. http://chvv.com.ua/kak-proverit-tekst-na-unikalnost/ .

21. Шарапов Р.В., Шарапова Е.В. Система проверки текстов на заимствования из других Источников - Муром: Муромский институт (филиал) ГОУ ВПО "Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых.

22. Болкунов И.А. Пути преодоления студенческого плагиата - Ялта: Евпаторийский педагогический факультет, РВУЗ «Крымский гуманитарный университет.

23. Нейл К., Шанмагантан Г. Web-инструмент для выявления плагиата, Открытые системы №01, 2005.

24. Евтифеева О.А., Красс А.Л., Лакунин М.А., Лысенко Е.А., Счастливцев Р.Р. Анализ поиска плагиата в исходных кодах программ - Санкт-Петербург: Санкт-Петербургский государственный университет.

25. Амонс А.А., Зайцев С.Ю., Киричек А.А. Выявление плагиата в программном коде C# - Вестник НТУУ «КПИ» Информатика, управление и вычислительная техника №53.

26. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов - Докл. Академий Наук СССР, 1965 - 845-848 с.

27. Damerau F.A. Technique for Computer Detection and Correction of Spelling Errors // Communications of the ACM. 1964. Vol. 7. No. 3. P. 171-176.

28. EUGENE W. MYERS, An O(ND) Difference Algorithm and Its Variations Department of Computer Science, University of Arizona, Tucson, AZ 85721, U.S.A.

29. Sun Wu, Udi Manber, Gene Myers, An O(NP) Sequence Comparison Algorith, Department of Computer Science University of Arizona Tucson, AZ 85721 and Webb Miller3, Department of Computer Science, The Pennsylvania State University University Park, PA 16802.August 1989

30. Hyyro H. Practical Methods for Approximate String Matching // Department of Computer Sciences, University of Tampere: PhD Thesis. Finland, 2003. 96 p.

31. Ukkonen E. Algorithms for Approximate String Matching // Information and Control. 1985. No. 64. P. 100-118.

32. Ukkonen E. Finding Approximate Patterns in Strings // Journal of Algorithms. 1985. No. 6. Р. 132-137.. Wagner R.A., Fischer M.J. The String-to-string Correction Problem // Journal of ACM. 1974. Vol. 21. No. 1. P. 168-173.

33. Черненький В.М., Гапанюк Ю.Е. МЕТОДИКА ИДЕНТИФИКАЦИИ ПАССАЖИРА ПО УСТАНОВОЧНЫМ ДАННЫМ

34. Зеленков Ю.Г., Сегалович И.В. Сравнительный анализ методов определения нечетких дубликатов для Web-документов, http://rcdl2007.pereslavl.ru/papers/paper_65_v1.pdf

35. Zweig. Syntactic clustering of the Web. Proc. of the 6th International World Wide Web Conference, April 1997.

36. U. Manber. Finding Similar Files in a Large File System. Winter USENIX Technical Conference, 1994.

37. R.A. Wagner, M.J. Fischer. The string-to-string correction problem. J. ACM 21 1 (1974). P. 168--173

38. A. Broder, S. Glassman, M. Manasse and G. Zweig. Syntactic clustering of the Web. Proc. of the 6th International World Wide Web Conference, April 1997.

39. Евсеев А.А. Анализ текстов на заимствование методом построения семантических моделей.

40. A. Broder, M. Charikar et al. Min-wise independent permutations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998

41. A. Chowdhury, O. Frieder, D. Grossman, M. McCabe. Collection statistics for fast duplicate document detection. ACM Transactions on Information Systems (TOIS), Vol. 20, Issue 2 (April 2002).

42. A.Chowdhury. Duplicate Data Detection. http://ir.iit.edu/~abdur/Research/Duplicate.html

43. A. Kolcz, A. Chowdhury, J. Alspector. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization. KDD 2004. http://ir.iit.edu/~abdur/publications/470-kolcz.pdf

44. D. Fetterly, M. Manasse, M. Najork. A Large-Scale Study of the Evolution of Web Pages, WWW2003, May 20-24, 2003, Budapest, Hungary.

45. S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich. An efficient method to detect duplicates of Web documents with the use of inverted index. WWW Conference 2002.

46. http://www.efg2.com/Lab/Mathematics/CRC.htm

47. http://www.m4-software.com/en-index.htm

48. http://www.copycatchgold.com

ПРИЛОЖЕНИЕ

Доработанная блок-схема алгоритма анализа последовательности операторов (с показом наиболее длинного совпадающего фрагмента кода)

На блок-схеме синим цветом показана доработанная часть алгоритма.

Размещено на Allbest.ru