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

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

СОДЕРЖАНИЕ

плагиат поиск программирование

ВВЕДЕНИЕ

Актуальность магистерской диссертации       

Понятие плагиата

Специфика понятия «плагиат» в программировании: окончательный вывод о заимствовании делает человек

         Постановка задачи

.1 Необходимость дополнительной проверки на основе структурного анализа кодов

.2 Общая схема работы модулей инструментальной системы поиска плагиата

         Теоретические основы поиска плагиата в исходных кодах программ

.1 Классификация методов поиска плагиата в программировании

.2 Атрибутные методы поиска плагиата

.3 Структурные методы поиска плагиата

.3.1 Строковое выравнивание

.3.2 Метод поиска на XML-представлении

.3.3 Использование приближения Колмогоровской сложности

.3.4 Метод идентификационных меток

.3.5 Нейросетевые методы обнаружения плагиата

.4 Другие методы

         Методы поиска плагиата в произвольных текстах

.1 Локальные методы

.1.1 LongSent

.1.2 Методы на основе меры TF

.1.3 Методы, использующие понятия шинглов

.1.4 Методы, использующие семантические сети

.2 Глобальные методы

.2.1 Методы на основе меры TF-IDF

.2.2 I-Match метод

.2.3 Метод «опорных» слов

.3 Метод шинглов

.3.1 Канонизация текстов

.3.2 Разбиение на шинглы

.3.3 Вычисление хешей шинглов

.4 Дистанция (расстояние) Левенштейна

.4.1 Алгоритм Вагнера - Фишера

.5. Наибольшая общая последовательность (longest common subsequence, LCS) 3.6 Вычисление хеш-функции

.6.1 Параметры вычисление хеш-функции: полином-генератор, разрядность и стартовое слово

.6.2 Популярные и стандартизованные полиномы

.7 Виды представления исходного кода

.8 Представление исходного кода в виде токенов

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

.1 Обзор программ поиска плагиата в программировании

.2 Обзор сервисов поиска плагиата

.3 Обзор программ поиска плагиата в произвольных текстах

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

.1 Общая схема поиска

.1.1 Cхема поиска для исходных кодов

.1.2 Основной структурный метод для анализа исходных кодов

.1.2.1 Достоинства и недостатки

.1.3 Дополнительный атрибутный метод для исходных текстов

.1.3.1 Достоинства и недостатки

.2.1 Cхема поиска для произвольных текстов (в том числе и программ)

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

.1 Интерфейс модуля поиска плагиата в исходных кодах программ

.1.1 Главное окно модуля поиска плагиата методами анализа исходных кодов

.1.2 Окно групповых режимов анализа

.2 Взаимодействие модуля поиска плагиата методами анализа исходных кодов

.2.1 Взаимодействие модуля с архивом работ и базой языков (добавление файла в базу)

.2.2 Взаимодействие модуля с архивом работ и базой языков (частотный анализ, автоматический частотный анализ)

.2.3 Взаимодействие модуля с архивом работ и базой языков (автоматический анализ последовательностей операторов)

.2.4. Взаимодействие модуля с архивом работ и базой языков (анализ последовательностей операторов, просчет всех пиков)

.2.5 Взаимодействие модуля с архивом работ и базой языков (удаление файла/языка из базы)

.2.6 Взаимодействие модуля с базой языков (добавление языка в базу)

.2.7 Пакетный режим анализа (1->n)

.2.8 Полный анализ (n->n)

.2.9 Поиск первоисточника и списка первоисточников

.2.10 Некоторые особенности модуля

.3 Описание отчетов по анализу плагиата

.3.1 Критерии автоматического заключения о наличии плагиата при пакетном и полном анализе

.3.2 Алгоритм поиска первоисточника для файла или списка первоисточников при полном анализе

.3.3 Сводный отчет

.3.4 Итоговый отчет

.3.5 Экспорт итогового протокола в Excel

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ

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

ВВЕДЕНИЕ

Актуальность магистерской диссертации

В учебных заведениях многие курсовые и лабораторные работы студентов состоят из описательной (текстовой) и программной части. Поэтому актуально создание приложений, позволяющих обнаружить списывание и текста и программного кода. В диссертации сделан акцент не столько на развитии конкретного метода поиска плагиата в исходных кодах программ студентов ([1-2]) или на развитии средств автоматизации такого поиска при большом объеме базы данных студентов (как это сделано в работе автора на степень бакалавра), сколько на реализации методов более глубокого анализа материала разными взаимно дополняющими методами (дистанция Левенштейна, Дамерау, метод шинглов, LCS). Это весьма важно, так как показал опыт применения только автоматизированных методов, без наличия дополнительных инструментов трудно сделать правильный вывод о наличии заимствований. Такой пример неполного анализа будет приведен в диссертации ниже в разделе 2.1.

Актуальность изучаемой проблемы подтверждается достаточно большим числом публикаций, в которых рассматриваются различные подходы, методы реализации и конкретные инструментальные средства поиска плагиата в работах студентов [18-25]. Новизна работы заключается в том, что в ней объединены в рамках единых инструментальных средств как алгоритмы поиска плагиата в программных кодах, так и в произвольных текстах (не только программах).

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

·        Методы анализа произвольных текстов и исходных кодов программ с точки зрения наличия идентичных фрагментов;

·        Разработка набора инструментов анализа исходных кодов программ из двух взаимно дополняющих модулей (рисунок 1): первый анализирует исходный код методами анализа исходных кодов (частотного анализа и анализа токенизированной последовательности операторов) в программных модулях студентов на основе пополняемой текстовой базы данных (БД), а второй позволяет анализировать этот же исходный код методами анализа произвольных текстов;

·        Реализация во втором модуле алгоритма поиска заимствованных фрагментов в исходных кодах программ, интегрирующего структурный анализ кодов (на основе исходного либо токенизированного представления), метода шинглов, дистанции Левенштейна и нахождения наибольшей общей подпоследовательности (longest common subsequence, LCS) для произвольных текстов. Если второй модуль рассматривает произвольный текст как исходный код программы (в модуле не установлен флажок «Текст»), то он использует ту же самую пополняемую БД работ студентов, которую формирует первый модуль.

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

Рисунок 1. Реализованные в инструментальной системе методы

Понятие плагиата

Понятие плагиата достаточно широко и нечетко, более того, многие понимают плагиат по-разному в зависимости от области, в которой они работают. Поэтому сошлемся на определения того, как понимается плагиат в различных предметных областях, приведенные в работе [3].

·  Плагиат - буквальное заимствование из чужого литературного произведения без указания источника [4].

·  Плагиат (от лат. plagio - похищаю) - вид нарушения прав автора или изобретателя. Состоит в незаконном использовании под своим именем чужого произведения (научного, литературного, музыкального) или изобретения, рационализаторского предложения (полностью или частично) без указания источника заимствования [5].

·  Плагиат - присвоение плодов чужого творчества: опубликование чужих произведений под своим именем без указания источника или использование без преобразующих творческих изменений, внесённых заимствователем [6].

·  Плагиат - умышленное присвоение авторства на чужое произведение науки, литературы или искусства. Не считается плагиатом заимствование темы или сюжета произведения либо научных идей, составляющих его содержание, без заимствования формы их выражения.

·  Плагиат - вид нарушения авторских прав [7], состоит в незаконном использовании под своим именем чужого произведения (научного, литературного, музыкального) или изобретения, рационализаторского предложения (полностью или частично) без указания источника заимствования [8] . Принуждение к соавторству также рассматривается как плагиат [9].

Для того чтобы избежать плагиата при написании текстов, важно соблюдать простые правила:

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

·              приводить в кавычках высказывания или отрывки из произведений других авторов;

Специфика понятия «плагиат» в программировании: окончательный вывод о заимствовании делает человек

В программировании понятие плагиата кажется не столь очевидным, учитывая, что для достаточно простых или типовых задач в инструментальных средах имеется достаточно большое число шаблонов, которыми рекомендуется пользоваться. И часто даже профессиональные программисты (а не только студенты) пользуются готовыми шаблонами. В качестве примера сошлемся на огромный набор готовых к использованию шаблонов сайтов, которые выложены в сети по лицензии GPL. Если анализировать чисто программный код таких сайтов, самостоятельно реализованных web-разработчиками с использованием, например, CMS Joomla или WordPress, то можно заподозрить их в плагиате. Хотя на самом деле никакого плагиата здесь нет. А практически вся собственная работа программиста просто вынесена в информацию, хранимую в базе данных. Аналогично состоит дело и при использовании таких инструментов программирования Visual Studio, Delphi или Eclipse.

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

1      
ПОСТАНОВКА ЗАДАЧИ

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

Целями магистерской диссертации являются:

·  Развитие инструментальных средств и методов анализа плагиата в части реализации возможностей дополнительной и более глубокой проверки на основе структурного анализа кодов.

·        Усовершенствование инструментальных средств и расширение методов поиска потенциального плагиата с помощью метрик Левенштейна, Дамерау и метода шинглов.

.1 Необходимость дополнительной проверки на основе анализа структурного анализа кодов

Разработанные ранее (в дипломе на степень бакалавра) методы автоматического анализа исходных кодов программ иногда не позволяют выявлять факт частичного заимствования текстов. В качестве подтверждения этого тезиса покажем это на примере сравнения двух программ из базы данных работ студентов. Хотя оба метода (частотного анализа текста и анализа последовательности операторов) показывают, что плагиата нет (рисунок 2, a), но, если посмотреть (рисунок 2, b) на наиболее длинную совпадающую последовательность операторов (рисунок 2, c), выделенную красным цветом в текстах программ (эта возможность была специально добавлена в ходе работы над магистерской диссертацией), то хорошо виден факт, по крайней мере, частичного заимствования кода, вплоть до одинакового порядка операторов и идентичного обозначения переменных.

Рисунок 2. Пример явного частичного заимствования исходного кода, не выявленный автоматическими методами

.2 Общая схема работы модулей инструментальной системы поиска плагиата

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

2      
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОИСКА ПЛАГИАТА В ИСХОДНЫХ КОДАХ ПРОГРАММ

.1 Классификация методов поиска плагиата в программировании

Для поиска плагиата на практике некоторым образом задаётся функция близости («метрика») и некоторый порог, по которому можно определить насколько вероятно, что часть программного кода была заимствована. Поиск плагиата в программировании может основываться на анализе характеристик кодов программ. Любая программа имеет определенную иерархию структур, которые могут быть выявлены, измерены и использованы в качестве таких характеристик. Применительно к доказательству факта заимствования, эти характеристики должны слабо меняться в случае модификации программы или включения фрагментов одной программы в другую.

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

Принято выделять два основных подхода к оценке близости программ (и соответственно разработке алгоритмов поиска плагиата): атрибутный (attribute-counting) и структурный. Впрочем, такое деление несколько условно. Существуют также методы, сочетающие в себе оба подхода [11].

2.2 Атрибутные методы поиска плагиата

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

Можно комбинировать несколько признаков, так чтобы программа была представлена не одним числом, а некоторым набором. Две программы могут считаться похожими, если соответствующие числа из их наборов совпадают или близки. В разное время для описания программ были предложены такие атрибуты, как количество операторов и операндов и другие. Таким образом, оценка близости программ сводится к сравнению чисел или векторов, которые получаются путем несложного анализа непосредственно исходного кода. Основным недостатком атрибутных техник является то, что несвязанные между собой параметры программы плохо описывают ее в целом, и при таком подходе разные программы получают близкие характеристики. Атрибутные методы активно развивались в 80-х годах XX столетия, но постепенно отошли на второй план.

.3 Структурные методы поиска плагиата

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

Чтобы отбросить лишнюю информацию и выделить нужные зависимости, программу предварительно переводят в более компактное представление. Как правило, сами по себе атрибутные методы малоэффективны, структурные методы превосходят их по качеству. Недостатком структурных методов является их сложность и вычислительная трудоемкость. Классическим примером структурного подхода является построение дерева программы с последующим сравнением деревьев для разных программ. Трудоемкость такого метода кубическая, что не даёт возможности сколько-нибудь эффективно его применять для большого числа достаточно длинных программ. Кроме того, структурные методы обычно опираются на синтаксис конкретного языка программирования. Адаптация метода для другого языка требует значительных усилий. Сложность реализации алгоритмов, сравнивающих структуру программ, является платой за их точность.

.3.1 Строковое выравнивание

Пусть есть две программы, представим их в виде строк токенов a и b соответственно (возможно различной длины). Теперь можно воспользоваться методом локального выравнивания строк. Выравнивание двух строк получается с помощью вставки в них пробелов таким образом, чтобы их длины стали одинаковыми. Для этого меньшую последовательность необходимо разбить на блоки и произвести оптимальное выравнивание (то есть такое, при котором будет максимальное количество совпадений при сравнении выравненных строк a и b). Алгоритм очень зависим от токенизации кода программы, что делает его зависимым от языка программирования.

.3.2 Метод поиска на XML-представлении

Представление программы в виде дерева (рисунок 3) отражает ее полезные для поиска плагиата свойства (такие как логика управления), и не учитывает бесполезные (например, порядок следования независимых операторов). Метод поиска плагиата основан на представлении программы в виде дерева, описание которого хранится в формате XML. Использование стандартных инструментов для работы с XML значительно упрощает архитектуру детектора плагиата. Программы, написанные на процедурных языках, таких как Pascal и С, хорошо структурированы, поэтому получить их XML-представление легко. Для оценки близости двух программ используются числовые матрицы, построенные на основе XML описаний.

Рисунок 3 Представление программы в виде дерева

.3.3 Использование приближения Колмогоровской сложности

В алгоритме используется расстояние между последовательностями, основанное на теории информации (an information based sequence distance):

где К(х) - Колмогоровская сложность последовательности х. Она показывает сколько информации содержит последовательность х. По определению, К(х) - длина самой короткой программы, которая на пустой ввод печатает х, К(х|у) - количество информации, полученной х от у, если пусто, то оно равно К(х); (К(х) - К(х|у)) - сколько у "знает" о х. По определению, К(х|у) - это длина самой короткой программы, которая на ввод у печатает х.

2.3.4 Метод идентификационных меток

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

.3.5 Нейросетевые методы обнаружения плагиата

Поиск плагиата можно свести к задаче классификации. Как известно, нейронные сети - это один из лучших инструментов для решения задачи аппроксимации функций, и в частности, классификации.

Нейронную сеть (рисунок 4) можно представить как черный ящик, на вход которому подается известная информация, а на выходе выдается информация, которую хотелось бы узнать.

Рисунок 4 Нейронная сеть

.4 Другие методы

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

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

3      
МЕТОДЫ ПОИСКА ПЛАГИАТА В ПРОИЗВОЛЬНЫХ ТЕКСТАХ

Если говорить о методах выявления плагиата в произвольных текстах, то часто вместо слова «плагиат» используют термин «нечеткий дубликат». Эти методы можно разделить на два больших класса. Алгоритмы, которые используют определенные знания о всей рассматриваемой коллекции документов, называют глобальными, в противном случае - локальными.

.1 Локальные методы

Рассмотрим, для начала, локальные алгоритмы. Основная идея таких методов сводится к синтаксическому анализу документа. На основе этого анализа документу ставится в соответствие определенное количество сигнатур.

.1.1 LongSent

Простейшим примером может служить алгоритм, который вычисляет хеш-функцию (MD5, SHA-2, CRC32) от конкантенации двух самых длинных предложений в документе. Это и будет являться его сигнатурой. Точность такого алгоритма достаточно большая, но он обладает существенным изъяном в безопасности. Такой алгоритм легко обмануть. Достаточно откорректировать всего лишь два самых длинных предложения.

.1.2 Методы на основе меры TF

Более эффективным способом нахождения нечетких дубликатов может стать метод, основанный на понятии TF (term frequency - частота слова). TF - это отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом оценивается важность слова в пределах отдельного документа. Для каждого слова в документе вычисляется его вес, равный отношению числа вхождения этого слова к общему количеству слов документа. Далее сцепляются n упорядоченных слов с наибольшим значением веса и вычисляется хеш-функция. Такой подход позволяет улучшить ситуацию, но для решения реальных задач этот способ не подходит.

.1.3 Методы, использующие понятия шинглов

Один из первых методов, который был применен на практике (компанией AltaVista), основывался на понятие шинглов. Данный подход был предложен A. Broder [40]. Этот метод детально будет рассмотрен в разделе 4.3.

.1.4 Методы, использующие семантические сети

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

.2 Глобальные методы

.2.1 Методы на основе меры TF-IDF

Дальнейшее развитие метода, использующего меру TF, стал алгоритм, анализирующий документы всей коллекции. В нем используются мера TF-IDF. IDF (inverse document frequency - обратная частота документа) - инверсия частоты, с которой некоторое слово встречается в документах коллекции.

где |d| - количество документов в коллекции;  - количество документов, в которых встречается терм t_t.

Вес широкоупотребительных слов можно сократить при учете IDF, то есть мера TF-IDF состоит из произведения TF и IDF. В мере TF-IDF больший вес будет у тех слов, которые часто использовались в одном документе и реже - в другом. Соответственно, при вычислении веса для каждого терма, алгоритм использует формулу TF * IDF. После этого в строку в алфавитном порядке сортируются 6 слов, которые имеют наибольшее значение веса. Контрольная сумма CRC32 полученной строки вычисляется в качестве сигнатуры документа.

Существуют различные модификации формулы вычисления веса слова. В поисковых системах широко известно семейство функций BM25. Одна из распространенных форм этой функции приведена ниже.

где f(q_i , D) - это частота слова q_i в документе D, |D| - это длина документа (количество слов в нём), а avgdl - средняя длина документа в коллекции. k₁ и b - свободные коэффициенты, обычно их выбирают как k₁ = 2.0 и b = 0.75. IDF(q_i) - обратная документная частота слова q_i .

3.2.2 I-Match метод

Еще один сигнатурный метод в 2002 году предложил A. Chowdhury [42]. Идея подхода тоже заключалась на знании всей коллекции документов. Предложенную методику автор усовершенствовал в 2004 году [43,44]. Ключевая идея данного метода основывалась на вычислении дактилограммы I-Match для демонстрации содержания документов. Изначально для исходной коллекции документов строился словарь L, который включает слова со средними значениями IDF. Именно они позволяли добиться наиболее точных показателей при выявлении нечетких дубликатов. Отбрасывались при этом те слова, которые имели большие и маленькие значения IDF. После этого для каждого документа создавалось множество U различных слов, состоящих в нем, и высчитывалось пересечение U и словаря L. Экспериментальным методом вычислялся минимальный порог и если размер пересечения превышал его, то список входящих в пересечение слов упорядочивался. Далее нужно посчитать I-Match сигнатуру (хеш-функция SHA1).

Следовательно, здесь мы видим следующую ситуацию: два документа будут считаться одинаковыми, если у них совпадут I-Match сигнатуры. В отличие от алгоритма, предложенного A. Broder., данный метод имеет больший потенциал. Он демонстрирует значительно улучшенную вычислительную способность. Опять же, если сравнивать с алгоритмом A. Broder, еще одним достоинством в пользу этого алгоритма становится то, что он значительно эффективнее проявляет себя при сравнении небольших по объему документов.

К сожалению, у данного алгоритма есть и свой недостаток - при небольшом изменении содержания он показывает свою неустойчивость. Чтобы исключить данный недостаток, авторы решили подвергнуть алгоритм изменению и усовершенствовать его. Была предложена новая техника многократного случайного перемешивания основного словаря. Суть модификаций заключается в следующем: к основному словарю L создаются K различных словарей L1-LK, которые образуются методом случайного удаления из исходного словаря определенной закрепленной части p слов. Эта небольшая группа p слов составляет приблизительно 30%-35% от исходного объема L. Для каждого документа вместо одной, вычисляется (K+1) I-Match сигнатур по алгоритму, который описан выше. Получается, что документ демонстрируется как вектор размерности (K+1). В таком случае два документа между собой будут считаться одинаковыми, если одна из координат у них совпадает. На практике, в качестве самых оптимальных значений параметров хорошо зарекомендовали себя такие показатели: p = 0.33 и K = 10.

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

.2.3 Метод «опорных» слов

Существует еще один способ выявления почти дубликатов, основанный на сигнатурном подходе. Данный метод тоже заключается в использовании лексических принципов, то есть на основе словаря. Метод был предложен С. Ильинским и др. [46] и получил название - метод «опорных» слов. Рассмотрим более детально принцип данного алгоритма.

Изначально из индекса по правилу, описанному ниже, мы выбираем множество из N слов, называемых «опорными». В данном случае, N определяется экспериментально. В дальнейшем, каждый документ выглядит N-мерным двоичным вектором, в котором i-я координата равна 1, если i-е «опорное» слово имеет в документе относительную частоту выше определенного порога (устанавливаемого отдельно для каждого «опорного» слова) и равна 0 в противном случае. Этот двоичный вектор и является сигнатурой документа. Соответственно, два документа считаются идентичными при совпадении сигнатур. При построении множества «опорных» слов используются следующие соображения:

. Множество слов должно охватывать максимально возможное число документов.

. Число слов в наборе должно быть минимальным.

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

.3 Метод шинглов

Наибольшую известность поиска плагиата в произвольных текстах получил метод «шинглов» [35-37]. Алгоритм шинглов - алгоритм, разработанный для поиска копий и дубликатов рассматриваемого текста в документе, мощный инструмент, призванный бороться с проявлениями плагиата.

Уди Манбер в 1994г. первым в мире выразил идею поиска дубликатов, а в 1997г. Андрей Бродер оптимизировал и довел её до логического завершения, дав имя данной системе - «алгоритм шинглов».

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

Разберем, через какие этапы проходит текст, подвергшийся сравнению:

1.      Канонизация текста и удаление «стоп-символов» и «стоп-слов»;

2.      Разбиение на шинглы;

3.      Вычисление хешей шинглов;

.        Сравнение, определение результата.

.3.1 Канонизация текстов

Канонизация текста приводит оригинальный текст к единой нормальной форме. Текст очищается от «стоп-символов» и «стоп-слов» (предлогов, союзов, знаков препинания, HTML тегов, и прочего не нужного «мусора»), который не должен участвовать в сравнении. В некоторых случаях так же предлагается удалять из текста прилагательные, так как они не несут смысловой нагрузки. Так же на этапе канонизации текста можно приводить существительные к именительному падежу, единственному числу, либо оставлять от них только корни. На выходе имеем текст, очищенный от «мусора», и готовый для сравнения. (Рисунок 5)

Рисунок 5. Алгоритм работы этапа канонизации в методе шинглов

3.3.2 Разбиение на шинглы

Шинглы - выделенные подпоследовательности слов. Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по N штук (длина шингла). Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов. Действия по каждому из пунктов выполняются для каждого из сравниваемых текстов. (Рисунок 6)

Рисунок 6. Алгоритм разбиения на шинглы

.3.3 Вычисление хешей шинглов

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

.4 Дистанция (расстояние) Левенштейна

Большая часть современных алгоритмов поиска плагиата построена на вычислении расстояния Левенштейна [27] или расстояния Дамерау - Левенштейна [28]. Определение расстояния Левенштейна (редакционного расстояния) основано на понятии «редакционное предписание» [29-34].

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) - удалить, I (англ. insert) - вставить, R (replace - заменить, M (match) - совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

Найти только расстояние Левенштейна - более простая задача, чем найти ещё и редакционное предписание.

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

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

Существуют обобщения понятия «Расстояние Левенштейна», при которых операции имеют разные цены.

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии, разную вероятность разных ошибок при вводе текста и т.д. В общем случае:

·              w(a, b) - цена замены символа a на символ b

·              w(ε, b) - цена вставки символа b

·              w(a, ε) - цена удаления символа a

Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при

·              w(a, а) = 0

·              w(a, b) = 1 при a≠b

·              w(ε, b) = 1

·              w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера - Фишера. Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау - Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80% ошибок при наборе текста человеком являются транспозициями.

Пусть S₁ и S₂ - две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние (расстояние Левенштейна) d(S₁, S₂) можно подсчитать по следующей рекуррентной формуле

где функция m(a,b) равна нулю, если a=b и единице в противном случае; min(a,b,c) возвращает наименьший из аргументов.

Здесь шаг по i символизирует удаление (D) из первой строки, по j - вставку (I) в первую строку, а шаг по обоим индексам символизирует замену символа (R) или отсутствие изменений (M).

Очевидно, справедливы следующие утверждения:

Рассмотрим формулу более подробно. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной i, нужно совершить i операций удаления, а чтобы получить строку длиной j из пустой, нужно произвести j операций вставки.

Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

·              Две замены одного и того же символа - неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).

·              Две замены разных символов можно менять местами

·              Два стирания или две вставки можно менять местами

·              Вставка символа с его последующим стиранием - неоптимально (можно их обе отменить)

·              Стирание и вставку разных символов можно менять местами

·              Вставка символа с его последующей заменой - неоптимально (излишняя замена)

·              Вставка символа и замена другого символа меняются местами

·              Замена символа с его последующим стиранием - неоптимально (излишняя замена)

·              Стирание символа и замена другого символа меняются местами

Пусть S₁ кончается на символ «a», S₂ кончается на символ «b». Есть три варианта:

1.      Символ «а», на который кончается S₁, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые (i - 1) символов S₁ в S₂ (на что потребовалось D(i - 1, j) операций), значит, всего потребовалось D(i - 1, j)+1 операций.

2.      Символ «b», на который кончается S₂, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили S₁ в первые (j - 1) символов S₂, после чего добавили «b». Аналогично предыдущему случаю, потребовалось D(i, j - 1)+1 операций.

.        Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то, чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа - его замена. Заменять его 2 или больше раз неоптимально. Значит,

1.       Если a=b, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили D(i - 1, j - 1) операций.

2.      Если a≠b, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить D(i - 1, j - 1) операций, значит, всего потребуется D(i - 1, j - 1)+1 операций.

.4.1 Алгоритм Вагнера - Фишера

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя выше приведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:

для всех i от 0 до M

для всех j от 0 до N

вычислить D(i, j)

вернуть D(M,N)

Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:

D(0,0) = 0

для всех j от 1 до N(0,j) = D(0,j-1) + цена вставки символа S2[j]

для всех i от 1 до M(i,0) = D(i-1,0) + цена удаления символа S1[i]

для всех j от 1 до N(i,j) = min((i-1, j) + цена удаления символа S1[i],(i, j-1) + цена вставки символа S2[j],(i-1, j-1) + цена замены символа S1[i] на символ S2[j]

)

вернуть D(M,N)

(Напоминаем, что элементы строк нумеруются с первого, а не с нулевого.)

Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:

·              если минимально (D(i-1, j) + цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)

·              если минимально (D(i, j-1) + цена вставки символа S2[j]), добавляем вставку символа S2[j] и идём в (i, j-1)

·              если минимально (D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)

Здесь (i, j) - клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

Этот алгоритм называется алгоритмом Вагнера- Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году[38].

3.5 Наибольшая общая последовательность (longest common subsequence, LCS)

Задача нахождения наибольшей общей подпоследовательности (longest common subsequence, LCS) - задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), в том числе для поиска плагиата.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что LCS может быть несколько.

3.6 Вычисление хеш-функции

В программе в качестве хеш-функции используется Циклический избыточный код (CRC-32). Алгоритм реализации CRC-32 взят из известной библиотеки #"787347.files/image015.gif">, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей N равно 2^N, что совпадает с числом всех двоичных последовательностей длины N.

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

где

R(x) - многочлен, представляющий значение CRC.

P(x) - многочлен, коэффициенты которого представляют входные данные.

G(x) - порождающий многочлен.

N - степень порождающего многочлена.

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2^N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хеш-функции в контексте каждого конкретного применения.

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

.6.1 Параметры вычисление хеш-функции: полином-генератор, разрядность и стартовое слово

В качестве примера рассмотрим схему формирования контрольной суммы CRC-8. Порождающий многочлен g(x) = x8+x5+x4+1. Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе.

Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров - информационных ячеек, используемых для вычисления численного значения хеш-функции. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 - битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

И последний параметр, важный при описании определенной методики - начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC.

.6.2 Популярные и стандартизованные полиномы

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

Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check reduntancy code.

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993-2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16, 24 и 32 бит, и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния. Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга. Использование другого полинома - CRC-32C - позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения могут быть даже выше - поэтому в наши дни он тоже пользуется популярностью. К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

В Википедии (#"787347.files/image018.gif">

Рисунок 7 Пример работы программы Turnitin tool

Механизм работы программы следующий: документ разбивается на фрагменты, которые сравниваются с содержимым базы данных при помощи статистического алгоритма. Поиск плагиата происходит на базе сравнения исходного текста с миллионами страниц контента в Интернете и внутренних баз данных.

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

Plagiarism-Finder 1.0.9 (#"787347.files/image019.gif">

Рисунок 8 Интерфейс программы Plagiarism-Finder

Длительность анализа зависит от требуемой точности, мощности ПК и качества канала выхода в Интернет. Анализ курсовой, содержащей 35 страниц (20 тыс. слов, 125 тыс. знаков), с широкополосным доступом DSL займет примерно 2 мин (выборочный контроль), 6 мин понадобится для так называемого среднего контроля (используется по умолчанию) и 40 мин - для проведения тщательной проверки. Документ должен быть представлен в цифровой форме. Plagiarism-Finder импортирует документы в форматах PDF (Acrobat Reader), DOC (Microsoft Word), HTML, TXT (Plain Text) или RTF (Rich TextFormat). Практически любой текстовый процессор позволяет представить документ в одном из данных форматов. При этом пользователь ПК может даже не иметь программы Microsoft Word. Программа ищет похожие тексты и выдает ссылки, однако вывод о том, плагиат это или нет, рекомендуется делать при визуальном сравнении текстов экспертом.

.3 Обзор программ поиска плагиата в произвольных текстах

Обзор программ поиска плагиата в произвольных текстах[17]:

Advego Plagiatus - программа для проверки текста на уникальность, осуществляет поиск в internet частичных или полных копий текста документа. Программа показывает степень уникальности текста в процентном соотношении, так же указывает источники не уникального текста, позволяет проверять текст на уникальность указанного URL. Программа требует установки на компьютер.

Praide unique content analyzer - программа для проверки уникальности контента. Требует установки. Параметры разбора позволяют изменять количество слов и фрагментах, количество слов перекрытия.

Double Content Finder - небольшая программа проверки текста на уникальность.

CopyCatch Gold (#"787347.files/image020.gif">

Рисунок 9 Интерфейс CopyChecker

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

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

5.1 Общая схема поиска

Основная идея поиска плагиата в работе - это использование взаимодополняющих методов поиска, применяемых как к произвольным текстам, так и только для исходных кодов.

.1.1 Cхема поиска для исходных кодов

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

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

5.1.2 Основной структурный метод для анализа исходных кодов

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

Рисунок 10 Первый этап поиска одинаковой последовательности операторов

Этот процесс продолжается до тех пор, пока не будет сравнен первый оператор второй последовательности с последним оператором первой (рисунок 11).

Рисунок 11 Второй этап поиска одинаковой последовательности операторов

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

Полученная информация изображается в виде гистограммы для каждого файла в базе сданных работ, на абсциссе которой откладывается величина смещения одной последовательности операторов относительно другой, а на ординате - количество совпадений операторов при таком смещении (рисунок 12).

Рисунок 12 Гистограмма результатов поиска одинаковой последовательности операторов

Пик, наблюдаемый на рисунке, возник из-за того, что в этих программах встречаются одинаковые фрагменты. Для «основных» пиков на графике выводится на экран код проверяемой программы и уже сданной работы из базы с выделенными фрагментами, соответствующими пику. Признать такое заимствование плагиатом или нет, решает преподаватель, основываясь на величине фрагмента, его роли в программе, схожести стиля программирования.

5.1.2.1 Достоинства и недостатки

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

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

.1.3 Дополнительный атрибутный метод для исходных текстов

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

Как и в первом методе, программы представляются в виде строк токенов. Далее анализируются частоты появления операторов программе. Частота определяется как количество появлений конкретного оператора, деленное на количество появлений всех операторов. Частоты отображаются в виде гистограммы. На абсциссе отложены порядковые номера операторов, а на ординате - частоты появлений этих операторов (рисунок 13). Идея такого способа идентификации плагиата опубликована в работе [10].

Рисунок 13 Диаграмма частотного анализа операторов

По такой гистограмме можно судить о количестве циклов, условных операторов и арифметических операций в каждой из программ. Например, пики, наблюдаемые в районе 60-63 соответствуют арифметическим операторам “:=”, “+” и “-” соответственно. Очевидно, что в обоих кодах используется большое количество таких операторов и частоты их появления примерно равны.

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

5.1.3.1 Достоинства и недостатки

Основными достоинствами метода является высокая скорость вычислений частот, что позволяет практически мгновенно в автоматическом режиме отобрать «подозрительные» работы, а затем в режиме один против одного проверить их с помощью основного структурного метода. Возможность сравнения количества определенных операторов, например операторов присваивания.

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

.2.1 Cхема поиска для произвольных текстов (в том числе и программ)

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

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

.1 Интерфейс модуля поиска плагиата в исходных кодах программ

.1.1 Главное окно модуля поиска плагиата методами анализа исходных кодов

Программа реализована на языке программирования - Delphi. В верхней части диалогового окна (рисунок 14) находятся кнопки для вызова функций добавления файла в базу, добавления языка в базу, удаления из базы файла/языка и компонент для выбора текущего языка.

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

В средней части окна находятся кнопки основных функций для анализа кода программ. Кнопка «Частотный анализ» позволяет сравнить частоты появления операторов двух выбранных файлов (слева анализируемый файл, справа - выбранный файл из базы). Ниже расположена кнопка «Авто» для режима один против всех (сравнение файла, выбранного слева со всеми файлами в базе). Кнопки (появляются после выбора режима «Авто») «<<» и «>>» позволяют осуществлять навигацию по файлам в базе, выстроенным по возрастанию вероятности плагиата. Стоит напомнить, что тексты программ, написанные одним м тем же автором, даже при полном совпадении не считаются плагиатом, поэтому в автоматическом режиме поиска все работы автора выбранного текста программы, принудительно получают значение вероятности плагиата 1%, чтобы облегчить работу преподавателя. В любом из режимов можно просмотреть информацию о выбранных файлах, нажав соответствующую кнопку.

Кнопка «Анализ посл. опер.» позволяет выполнить анализ совпадений последовательностей операторов выбранных текстов программ. Если отмечено «Только непрерывн. посл.», то производится анализ только максимальной последовательности операторов, иначе учитываются все, в том числе и случайные совпадения этих последовательностей. Кнопка «Просчитать все пики» позволяет переходить от максимальной последовательности совпадений к любой другой, вывести соответствующие ей участки программ и сохранить отчет. Так же как и для частотного анализа, для анализа последовательности операторов предусмотрен автоматический режим.

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

Результаты анализа кода программы выводится в виде графика на стандартном компоненте Chart (для частотного анализа на двух) и относительная оценка вероятности плагиата на компонент ProgressBar.

Для целей диплома бакалавра были добавлены кнопки «Сводный анализ», «Итоговый отчет» и «Групповые режимы анализа». При нажатии кнопки «Групповые режимы анализа» открывается соответствующее новое окно (рисунок 15).

6.1.2 Окно групповых режимов анализа

Окно групповых режимов анализа (рисунок 15) используется при выполнении анализа одного файла сразу с несколькими файлами (группой при пакетном режиме) или всех файлов со всеми файлами (при полном анализе). Выделено четыре подраздела в этом окне:

·  «Выполнить» для осуществления операций анализа

·        «Показать» для показа отчетов и анализа результатов

·        «Служебные действия» для выполнения вспомогательных операций удаления отчетов

·        «Настроить критерии плагиата» для задания пороговых значений методов, при превышении которых выносится заключение о возможности плагиата

Рисунок 15 Окно групповых режимов анализа

.2 Взаимодействие модуля поиска плагиата методами анализа исходных кодов

.2.1 Взаимодействие модуля с архивом работ и базой языков (добавление файла в базу)

Взаимодействие модуля с архивом работ и базой языков (добавление файла в базу) показано на рисунке 16.

) Копирование исследуемого кода  в архив работ студентов.

) Создание файла описания исследуемого файла.

) Добавление имени файла в список файлов этого языка.

) Нормализация исследуемого кода.

) Составление файла последовательности операторов исследуемой работы из нормализованного кода по базе операторов языка.

Рисунок 16 Взаимодействие модуля с архивом работ и базой языков

.2.2 Взаимодействие модуля с архивом работ и базой языков (частотный анализ, автоматический частотный анализ)

Взаимодействие программы с архивом работ и базой языков (частотный анализ, автоматический частотный анализ) показано на рисунке 17:

) По файлу операторов исследуемой работы составление последовательности частот появления операторов.

) Для всех файлов данного языка, кроме работ этого же автора, вычисление частот появления операторов и их сравнение.

) Составление временного файла результатов сравнения частот появления операторов.

) По запросам преподавателя восстановление исходных кодов для файлов с максимальным процентом совпадения частот появления операторов.

Рисунок 17 Взаимодействие модуля с архивом работ и базой языков

.2.3 Взаимодействие модуля с архивом работ и базой языков (автоматический анализ последовательностей операторов)

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

) Составление временного файла, содержащего проценты отношений максимальной длины совпадений к количеству операторов исследуемого файла.

) По запросам преподавателя восстановление исходных кодов файлов по полученному временному файлу.

.2.4. Взаимодействие модуля с архивом работ и базой языков (анализ последовательностей операторов, просчет всех пиков)

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

) Сортировка строчек в этом файле в порядке убывания.

) По запросам преподавателя восстановление исходных кодов файлов с выделением строк, соответствующих пикам (цепочкам совпадений), по полученному временному файлу.

) Создание отчета и сохранение его в файл.

6.2.5 Взаимодействие модуля с архивом работ и базой языков (удаление файла/языка из базы)

1) Если выбран файл для удаления, то из базы работ удаляется сам файл с исходным кодом, файл описания, файл последовательности операторов, а списка  файлов этого языка удаляется его имя.

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

) Удаляется файл операторов этого языка, список файлов и из файла известных языков стирается имя этого файла.

.2.6 Взаимодействие модуля с базой языков (добавление языка в базу)

Взаимодействие модуля с базой языков (добавление языка в базу) показано на рисунке 18:

) Нормализация файла с операторами языка.

) Занесение списка операторов в базу языков программирования.

) Создание файла для списка файлов этого языка.

) Добавление названия нового языка в файл известных языков.

Рисунок 18 Взаимодействие модуля с базой языков

6.2.7 Пакетный режим анализа (1->n)

При пакетном режиме анализа (режим сравнения  программ 1->n) - режим, при котором текст одной из программ (в левом окне) автоматически (без участия пользователя) сравнивается двумя методами (частотным анализом и анализом последовательности операторов) с каждой из программ в списке (файле Batch.txt) и последующей автоматической записью этого сравнения в сводный отчет.

.2.8 Полный анализ (n->n)

При полном анализе (режим сравнения n->n) - режим, при котором текст каждой из программ в базе данных (файле списка файлов для данного языка, например, DelphiF.txt) сравнивается двумя методами (частотным анализом и анализом последовательности операторов) с каждой из программ в базе данных (файле списка файлов для данного языка, например, DelphiF.txt) и последующей автоматической записью этого сравнения в итоговый отчет.

.2.9 Поиск первоисточника и списка первоисточников

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

.2.10 Некоторые особенности модуля

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

Для повышения надежности и скорости работы программы на медленных ПК, следует исключать из добавляемых файлов стандартные части, свойственные данному языку программирования, а так же из базы операторов языка программирования те оператоы, которые обычно используются в качестве разделителей (например, в C++ обычно разделяют текст программы с помощью «////////////////////////»).

6.3 Описание отчетов по анализу плагиата

.3.1 Критерии автоматического заключения о наличии плагиата при пакетном и полном анализе

Ввиду того,  что при пакетном и полном анализе человек не включен в процесс принятия решения о наличии плагиата, предложены следующие эмпирические критерии:

. Для частотного анализа сравнивается число типов операторов в двух файлах. Вычисляются два числа: число типов операторов, которые по частоте вхождения полностью совпали, и число типов операторов, разница в частоте вхождения которых отличается не более, чем на 1%. Второе число введено для того, чтобы иметь возможность учитывать практически идентичные, но  не полностью совпадающие частоты вхождения типов операторов. Вывод о наличии плагиата по частоте операторов делается в том случае, если хотя бы для одного из сравниваемых файлов процент одинаковых со вторым файлом типов операторов превосходит выбранное пользователем значение (по умолчанию 70%). Эта доля выбирается пользователем в окне групповых режимов анализа и может иметь следующие значения (в процентах): 30,40,50,60,70,80,90. Если эта доля не выбрана, то предполагается критерий - 70%. То есть устанавливается, что если в двух сравниваемых программах доля практически идентичных по количеству вхождений типов операторов превышает 70% от общего числа типов операторов в одной из программ, то делается вывод о наличии плагиата.

. Для анализа последовательности совпавших типов операторов критерий заключения о наличии плагиата устанавливается исходя из доли длины совпавшей последовательности экземпляров операторов к числу экземпляров операторов в программе. Эта доля выбирается пользователем в окне групповых режимов анализа и может иметь следующие значения (в процентах): 10,20,30,40,50. Если эта доля не выбрана, то предполагается критерий - 50%. То есть устанавливается, что если в двух сравниваемых программах совпадающая последовательность экземпляров операторов превышает половину программы.

.3.2 Алгоритм поиска первоисточника для файла или списка первоисточников при полном анализе

Алгоритм поиска такого файла достаточно прост. В сводном отчете просматриваются все файлы с признаками плагиата по обоим критериям (по частотному анализу и по анализу последовательности операторов) и ищется файл с наиболее ранней датой создания (с учетом времени суток). Если подозрительных файлов в сводном отчете нет, то сам изучаемый файл является первоисточником. Пример результата такого поиска показан на рисунке 19.

Рисунок 19 Окно результата поиска первоисточника для 1 файла

Аналогичным образом получается список первоисточников при полном анализе: просматриваются сводные отчеты для всех файлов (рисунок 20): в полученном отчете в каждой строке первое имя - изучаемый файл, второе имя - первоисточник. В списке для каждого из файлов полного анализа приведен соответствующий первоисточник.

Рисунок 20 Окно результата поиска первоисточников при полном анализе

6.3.3 Сводный отчет

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

Сводный отчет (или сразу множество сводных отчетов) формируется тремя способами:

·  Вручную в результате сравнения двух программ (1->1) двумя методами (частотным анализом и анализом последовательности операторов) и последующей записи этого сравнения в сводный отчет;

·        Автоматически в результате применения пакетного режима сравнения  программ (1->n), при котором текст одной из программ (в левом окне) сравнивается двумя методами (частотным анализом и анализом последовательности операторов) с каждой из программ в списке (файле Batch.txt) и последующей автоматической записью этого сравнения в сводный отчет;

·        Автоматически в результате применения режима полного анализа программ (n->n), при котором текст каждой из программ (в файле списка файлов для данного языка, например, DelphiF.txt) сравнивается двумя методами (частотным анализом и анализом последовательности операторов) с каждой из программ в списке (файле списка файлов для данного языка, например, DelphiF.txt) и последующей автоматической записью этого сравнения в сводный отчет.

Сводный отчет имеет следующую структуру:

ПОЛНОЕ ИМЯ ФАЙЛА и ГОД ЕГО НАПИСАНИЯ

КРИТЕРИИ ПЛАГИАТА:

Доля длины (в %) совпавшей последовательности операторов ко всей длине программы -> <значение>%

% практически идентичных типов операторов при частотном анализе -> <значение>%

<список файлов с детализацией >

КОЛИЧЕСТВО СОПОСТАВЛЕНЫХ ФАЙЛОВ =

ПОДОЗРИТЕЛЬНЫЕ ФАЙЛЫ:

<список файлов >

ФАЙЛЫ БЕЗ УЧЕТА ГОДОВ:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ =

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ =

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

ОДИНАКОВЫЙ ГОД:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ =

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ =

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

ПЛАГИАТ ВЗЯТ ИЗ ПРЕДЫДУЩИХ ГОДОВ:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ =

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ =

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

Данные в сводном отчете структурированы следующим образом:

1. Полный детализированный список файлов (<список файлов с детализацией >), с которыми выполнялось сравнение.

2.      ПОДОЗРИТЕЛЬНЫЕ ФАЙЛЫ. В этом разделе приводится список файлов (<список файлов с детализацией подозрения на плагиат>), в которых обнаружена возможность плагиата.

.        БЕЗ УЧЕТА ГОДОВ. Резюме по подозрительным файлам без учета годов из написания.

.        ОДИНАКОВЫЙ ГОД. Резюме по подозрительным файлам, которые написаны в один год. Проверяется возможность плагиата на одном году обучения.

5.      ПЛАГИАТ ВЗЯТ ИЗ ПРЕДЫДУЩИХ ГОДОВ. Резюме по подозрительным файлам, которые написаны в предыдущие годы по сравнению с годом написания исследуемой программы. Проверяется возможность плагиата, при котором студенты воспользовались трудами предыдущих курсов обучения.

Каждая строка <Список файлов с детализацией> имеет структуру, в которой сведены сведении по результатам частотного анализа и анализа последовательности операторов.

Сведения по результатам частотного анализа:

·  Имя файла, год написания

·        Группа. Если поле не заполнено, то пишется  'ГРПНЗВСТ '

·        Автор. Если поле не заполнено, то пишется 'АВТОРНЗВСТ '

·        Число экземпляров операторов в 1 файле

·        Число экземпляров операторов во 2 файле

·        Число типов операторов в 1 файле

·        Число типов операторов в 2 файле

·        Число типов операторов с равной долей вхождений в обоих файлах

·        % типов операторов совпадают для 1 файла

·        % типов операторов совпадают для 2 файла

·        Число типов операторов с равной долей вхождений в обоих файлах

·        % типов операторов удовлетворяют условию (разница в доле <1%) для 1 файла

·        % типов операторов удовлетворяют условию (разница в доле <1%) для 2 файла

·        Признак того, что плагиат есть (1) или нет (0) по критерию частоты операторов

Сведения по результатам анализа последовательности операторов:

·  Имя файла, год написания

·        Группа. Если поле не заполнено, то пишется  'ГРПНЗВСТ '

·        Автор. Если поле не заполнено, то пишется 'АВТОРНЗВСТ '

·        Число экземпляров операторов в 1 файле

·        Число экземпляров операторов во 2 файле

·        Длина максимального совпадения последовательных экземпляров операторов в файлах

·        Процент от числа всех экземпляров операторов в 1 файле

·        Процент от числа всех экземпляров операторов в 2 файле

·        Признак того, что плагиат есть (1) или нет (0) по критерию анализа последовательности операторов

Фрагмент сводного отчета по реальной базе данных работ студентов:

СВОДНЫЙ ОТЧЕТ ПО ФАЙЛУ Arh\Unit1.pas-39.txt ГОД 2007

КРИТЕРИИ ПЛАГИАТА:

Доля длины (в %) совпавшей последовательности операторов ко всей длине программы -> 50% (по умолчанию)

% практически идентичных типов операторов при частотном анализе -> 70% (по умолчанию)

\Unit2.pas-202.txt 2004 _ВВ-5-00 Комодин 405 19 34 13 0 0,00 0,00 0 2,94 7,69 0 Arh\Unit2.pas-202.txt 2004 _ВВ-5-00 Комодин 405 19 8 1,9753 42,1053 0\Kam_Lab_2004.pas-272.txt 2004 _ВВ-5-00 Комодин 405 99 34 23 0 0,00 0,00 0 14,71 21,74 0 Arh\Kam_Lab_2004.pas-272.txt 2004 _ВВ-5-00 Комодин 405 99 11 2,7160 11,1111 0\Unit1.pas-670.txt 2004 _ВВ-5-00 Капанин 405 218 34 29 0 0,00 0,00 0 23,53 27,59 0 Arh\Unit1.pas-670.txt 2004 _ВВ-5-00 Капанин 405 218 11 2,7160 5,0459 0\Kop_Lab_2004.pas-318.txt 2004 _ВВ-5-00 Капанин 405 126 34 26 0 0,00 0,00 0 23,53 30,77 0 Arh\Kop_Lab_2004.pas-318.txt 2004 _ВВ-5-00 Капанин 405 126 17 4,1975 13,4921 0\Unit1.pas-70.txt 2004 _ВВ-5-01 АВТОРНЗВСТ 405 131 34 26 0 0,00 0,00 0 26,47 34,62 0 Arh\Unit1.pas-70.txt 2004 _ВВ-5-01 АВТОРНЗВСТ 405 131 11 2,7160 8,3969 0\Unit1.pas-840.txt 2004 ГРПНЗВСТ АВТОРНЗВСТ 405 218 34 29 0 0,00 0,00 0 23,53 27,59 0 Arh\Unit1.pas-840.txt 2004 ГРПНЗВСТ АВТОРНЗВСТ 405 218 11 2,7160 5,0459 0\Unit1.pas-59.txt 2004 _ВВ-5-01 АВТОРНЗВСТ 405 156 34 27 0 0,00 0,00 0 29,41 37,04 0 Arh\Unit1.pas-59.txt 2004 _ВВ-5-01 АВТОРНЗВСТ 405 156 13 3,2099 8,3333 0\Cezar.pas-287.txt 2004 _ВВ-61-00 Якушина 405 111 34 15 0 0,00 0,00 0 11,76 26,67 0 Arh\Cezar.pas-287.txt 2004 _ВВ-61-00 Якушина 405 111 5 1,2346 4,5045 0

…

КОЛИЧЕСТВО СОПОСТАВЛЕНЫХ ФАЙЛОВ = 282

ПОДОЗРИТЕЛЬНЫЕ ФАЙЛЫ:\Unit2.pas-670.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit3.pas-318.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit4.pas-161.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit5.pas-371.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit2.pas-327.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit3.pas-696.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit4.pas-843.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit5.pas-717.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit2.pas-246.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit3.pas-824.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit4.pas-278.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit5.pas-481.txt 2007 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit2.pas-680.txt 2004 ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit1.pas-279.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ  ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit1.pas-805.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ\Unit1.pas-818.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ\Unit1.pas-141.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ  ПЛАГИАТ_ПО_СОВПАДЕНИЮ\Unit1.pas-713.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ\Unit1.pas-979.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ\Unit1.pas-154.txt 2007 ПЛАГИАТ_ПО_ЧАСТОТЕ_ОПЕРАТОРОВ

БЕЗ УЧЕТА ГОДОВ:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ = 12

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ = 16

ВСЕГО ПОДОЗРЕНИЙ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ ПЛАГИАТА = 3

ОДИНАКОВЫЙ ГОД:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ = 9

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ = 15

ВСЕГО ПОДОЗРЕНИЙ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ ПЛАГИАТА = 3

ПЛАГИАТ ВЗЯТ ИЗ ПРЕДЫДУЩИХ ГОДОВ:

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ = 3

ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ = 1

ВСЕГО ПОДОЗРЕНИЙ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ ПЛАГИАТА = 0

.3.4 Итоговый отчет

Итоговый отчет формируется тремя способами:

·  Вручную путем записи в любой момент времени резюме (одной строкой) по текущему сводному отчету для выбранного файла в итоговый отчет;

·        Автоматически в результате применения пакетного режима  (1->n) путем записи в итоговый отчет после окончания анализа всего пакета резюме (одной строкой) по полученному  сводному отчету для выбранного файла;

·        Автоматически в результате применения режима полного анализа программ (n->n), путем записи в итоговый отчет после окончания полного анализа для каждого из файлов резюме (одной строкой) по полученному сводному отчету.

Описание структуры итогового отчета:

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

В итоговом отчете приводится список проанализированных файлов, для каждого из которых указывается:

·  имя файла и год написания;

·        число подозрительных файлов по частоте операторов по всем годам;

·        число подозрительных файлов по совпадению операторов по всем годам;

·        число подозрительных файлов по обоим критериям по всем годам;

(ЭТА ИНФОРМАЦИЯ ДЛЯ АНАЛИЗА ОБЩЕЙ КАРТИНЫ ПЛАГИАТА БЕЗ УЧЕТА ГОДОВ)

·  число подозрительных файлов по частоте операторов по этому же году;

·        число подозрительных файлов по совпадению операторов по этому же году;

·        число подозрительных файлов по обоим критериям по этому же году;

(ЭТА ИНФОРМАЦИЯ ДЛЯ АНАЛИЗА КАРТИНЫ ПЛАГИАТА НА ОДНОМ ГОДУ ОБУЧЕНИЯ)

·  число подозрительных файлов по частоте операторов по предыдущим годам;

·        число подозрительных файлов по совпадению операторов по предыдущим годам;

·        число подозрительных файлов по обоим критериям по предыдущим годам;

(ЭТА ИНФОРМАЦИЯ ДЛЯ АНАЛИЗА КАРТИНЫ ПЛАГИАТА, КОГДА СПИСЫВАЮТ С ПРЕДЫДУЩИХ ЛЕТ)

·  суммарное число файлов, с которыми выполнялось сравнение.

КОЛИЧЕСТВО ИССЛЕДОВАННЫХ ФАЙЛОВ =

Приводится список файлов с плагиатом, взятым из предыдущих лет обучения:

КОЛИЧЕСТВО ФАЙЛОВ с плагиатом, взятым из предыдущих лет обучения:=

Приводится список файлов с плагиатом, на одном году обучения:

КОЛИЧЕСТВО ФАЙЛОВ с плагиатом на одном году обучения:=

Фрагмент итогового отчета по реальной базе данных работ студентов:

ИТОГОВЫЙ ОТЧЕТ

КРИТЕРИИ ПЛАГИАТА:

Доля длины (в %) совпавшей последовательности операторов ко всей длине программы -> 50% (по умолчанию)

% практически идентичных типов операторов при частотном анализе -> 70% (по умолчанию)

Arh\Unit2.pas-202.txt 2004 1 37 1 1 8 1 0 1 0 282\Kam_Lab_2004.pas-272.txt 2004 3 1 1 3 1 1 0 0 0 282\Unit1.pas-670.txt 2004 2 1 1 2 1 1 0 0 0 282\Kop_Lab_2004.pas-318.txt 2004 3 14 1 3 2 1 0 0 0 282\Unit1.pas-70.txt 2004 2 0 0 1 0 0 0 0 0 282\Unit1.pas-840.txt 2004 2 1 1 2 1 1 0 0 0 282

…\Unit1.pas-154.txt 2007 18 13 0 14 12 0 3 1 0 282\Unit1.pas-39.txt 2007 12 16 3 9 15 3 3 1 0 282

КОЛИЧЕСТВО ИССЛЕДОВАННЫХ ФАЙЛОВ = 283

==============================

Список файлов с явным подозрением на плагиат:

файлы, в которых есть заимствованный код из предыдущих лет

Arh\Unit2.pas-202.txt 2004 1 37 1 1 8 1 0 1 0 282\Unit1.pas-140.txt 2007 5 0 0 4 0 0 1 0 0 282\Unit1.pas-143.txt 2007 19 6 6 12 5 5 1 0 0 282\Unit2.pas-31.txt 2006 0 6 0 0 0 0 0 3 0 282\ZUnit1.pas-0.txt 2011 5 2 2 3 2 2 2 0 0 282\ZUnit1.pas-4.txt 2011 6 0 0 3 0 0 3 0 0 282\ZUnit1.pas-6.txt 2011 2 0 0 0 0 0 2 0 0 282\ZUnit1.pas-8.txt 2011 0 13 0 0 0 0 0 13 0 282\Unit1.pas-773.txt 2008 22 7 1 4 1 1 17 6 0 282\zki6RSA.pas-329.txt 2005 1 13 0 1 0 0 0 1 0 282

….\Unit1.pas-979.txt 2007 16 13 0 14 12 0 0 1 0 282\Unit1.pas-154.txt 2007 18 13 0 14 12 0 3 1 0 282\Unit1.pas-39.txt 2007 12 16 3 9 15 3 3 1 0 282

КОЛИЧЕСТВО ФАЙЛОВ С ПЛАГИАТОМ ИЗ ПРЕДЫДУЩИХ ЛЕТ = 168

==============================

Список файлов с подозрением на плагиат, но с неизветным авторством

файлы, в которых есть заимствованный код на одном году обучения

В данном случае нельзя достоверно определить, кто писал сам, а кто списывал.

Arh\Unit2.pas-202.txt 2004 1 37 1 1 8 1 0 1 0 282\Kam_Lab_2004.pas-272.txt 2004 3 1 1 3 1 1 0 0 0 282\Unit1.pas-670.txt 2004 2 1 1 2 1 1 0 0 0 282\Kop_Lab_2004.pas-318.txt 2004 3 14 1 3 2 1 0 0 0 282\Unit1.pas-70.txt 2004 2 0 0 1 0 0 0 0 0 282\Unit1.pas-840.txt 2004 2 1 1 2 1 1 0 0 0 282

...\Unit1.pas-879.txt 2007 10 14 1 8 13 1 2 1 0 282\Unit1.pas-713.txt 2007 13 14 1 9 13 1 2 1 0 282\Unit1.pas-438.txt 2007 5 14 1 5 13 1 0 1 0 282\Unit1.pas-979.txt 2007 16 13 0 14 12 0 0 1 0 282\Unit1.pas-154.txt 2007 18 13 0 14 12 0 3 1 0 282\Unit1.pas-39.txt 2007 12 16 3 9 15 3 3 1 0 282

КОЛИЧЕСТВО ФАЙЛОВ С ПЛАГИАТОМ НА ОДНОМ ГОДУ ОБУЧЕНИЯ = 236

.3.5 Экспорт итогового протокола в Excel

В таблице 2 (получена после экспорта в Excel) приведены данные в абсолютных величинах (верхняя часть) и в относительных величинах (в нижней части). Абсолютные величины - это число работ студентов в данном году с определенным признаком. Относительные величины приводятся в процентах к числу работ студентов в данном году.

Пояснение к названиям столбцов:

·  С - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ БЕЗ УЧЕТА ГОДОВ

·        D - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ БЕЗ УЧЕТА ГОДОВ

·        E - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ БЕЗ УЧЕТА ГОДОВ

·        F - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ В ОДНОМ И ТОМ ЖЕ ГОДУ

·        G - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ В ОДНОМ И ТОМ ЖЕ ГОДУ

·        H - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ В ОДНОМ И ТОМ ЖЕ ГОДУ

·        I - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО ЧАСТОТЕ ОПЕРАТОРОВ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ

·        J - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ПО СОВПАДЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ

·        K - ВСЕГО ПОДОЗРЕНИЙ НА ПЛАГИАТ ОДНОВРЕМЕННО ПО ОБОИМ КРИТЕРИЯМ ПРИ СРАВНЕНИИ С ПРОГРАММАМИ ПРЕДЫДУЩИХ ЛЕТ

Таблица 2 Таблица обработки базы данных, структурированных по годам и признакам плагиата

Относительные значения в виде столбиковых диаграмм показаны на рисунке 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).

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

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

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

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

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

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

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

*************** 1 Файл: ***************(Static3!=NULL) Static3->Create("Результат",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(495,5,880,20),this);= new CEdit();(Edit3!=NULL) Edit3->Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_MULTILINE, CRect(60,530,590,550),this,IDC_EDIT3);= new CStatic();(Static1!=NULL) Static1->Create("Ключ",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(10,530,60,550),this);= new CButton();(Button1!=NULL) Button1->Create("Шифрование",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(60,560,230,580),this,IDC_BUTTON1);= new CButton();(Button2!=NULL) Button2->Create("Выход",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,600,780,620),this,IDC_BUTTON2);= new CButton();(Button3!=NULL) Button3->Create("Таблица Вижинера",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,530,780,550),this,IDC_BUTTON3);= new CButton();(Button4!=NULL) Button4->Create("Расшифровать ключом",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(240,560,410,580),this,IDC_BUTTON4);= new CButton();(Button6!=NULL) Button6->Create("<<",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(400,250,490,300),this,IDC_BUTTON6);

*************** 2 Файл: ***************(Static2!=NULL) Static2->Create("Исходный текст",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(10,5,395,20),this);3 = new CStatic(); // это заголовок правого окна - "Результат"

if (Static3!=NULL) Static3->Create("Результат",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(495,5,880,20),this);3 = new CEdit(); // аналогично Edit1 - это текстовое поле для ключа

if (Edit3!=NULL) Edit3->Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_MULTILINE, CRect(60,530,590,550),this,IDC_EDIT3);1 = 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);2 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON2

if (Button2!=NULL) Button2->Create("Выход",WS_CHILD|WS_VISIBLE|SS_CENTER, CRect(610,600,780,620),this,IDC_BUTTON2);3 = new CButton(); // создаем объект и рисуем его функцией Create и связываем с константой IDC_BUTTON3

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

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

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

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

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

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

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

.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 Выбор длины шинглов

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

3.      Красс А. Обзор автоматических детекторов плагиата в программах. #"787347.files/image042.gif">