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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

2.3.1 Строковое выравнивание

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

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

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

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

2.4 Другие методы

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

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

3.1.1 LongSent

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

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

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

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

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

3.2.2 I-Match метод

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

3.3 Метод шинглов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.3.4 Итоговый отчет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.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.1 Необходимость дополнительной проверки на основе анализа структурного анализа кодов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 Строковое выравнивание

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 Другие методы

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

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

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

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

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

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

3.1.1 LongSent

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

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

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

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

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

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

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

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

3.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.

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

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

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

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

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

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

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

3.3 Метод шинглов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M	M	M	I	R	M	R	D
C	O	N	N	E	C	T
C	O	N	E	H	E	A	D

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

Расстояние Левенштейна - минимальное количество действий, необходимых для преобразования одного слова в другое. В приведенном примере расстояние Левенштейна равно 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 операций.

3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «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 операций.

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

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

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

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

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

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

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

D(0,0) = 0

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

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

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

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

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

D(i,j) = min(

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

D(i, j-1) + цена вставки символа S2[j],

D(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 взят из известной библиотеки http://www.efg2.com/Lab/Mathematics/CRC.htm [46]. Первоначальная реализация (на Ассемблере) многочлена, генерирующего значение CRC-32, определена в номере журнала «Microsoft Systems Journal», March 1995, стр. 107-108.

CRCTable dd 00000000h, 77073096h, 0EE0E612Ch, 990951BAh dd 076DC419h, 706AF48Fh, 0E963A535h, 9E6495A3h dd 0EDB8832h, 79DCB8A4h, 0E0D5E91Eh, 97D2D988h dd 09B64C2Bh, 7EB17CBDh, 0E7B82D07h, 90BF1D91h dd 1DB71064h, 6AB020F2h, 0F3B97148h, 84BE41DEh dd 1ADAD47Dh, 6DDDE4EBh, 0F4D4B551h, 83D385C7h dd 136C9856h, 646BA8C0h, 0FD62F97Ah, 8A65C9ECh dd 14015C4Fh, 63066CD9h, 0FA0F3D63h, 8D080DF5h dd 3B6E20C8h, 4C69105Eh, 0D56041E4h, 0A2677172h dd 3C03E4D1h, 4B04D447h, 0D20D85FDh, 0A50AB56Bh dd 35B5A8FAh, 42B2986Ch, 0DBBBC9D6h, 0ACBCF940h dd 32D86CE3h, 45DF5C75h, 0DCD60DCFh, 0ABD13D59h dd 26D930ACh, 51DE003Ah, 0C8D75180h, 0BFD06116h dd 21B4F4B5h, 56B3C423h, 0CFBA9599h, 0B8BDA50Fh dd 2802B89Eh, 5F058808h, 0C60CD9B2h, 0B10BE924h dd 2F6F7C87h, 58684C11h, 0C1611DABh, 0B6662D3Dh dd 76DC4190h, 01DB7106h, 98D220BCh, 0EFD5102Ah dd 71B18589h, 06B6B51Fh, 9FBFE4A5h, 0E8B8D433h dd 7807C9A2h, 0F00F934h, 9609A88Eh, 0E10E9818h dd 7F6A0DBBh, 086D3D2Dh, 91646C97h, 0E6635C01h dd 6B6B51F4h, 1C6C6162h, 856530D8h, 0F262004Eh dd 6C0695EDh, 1B01A57Bh, 8208F4C1h, 0F50FC457h dd 65B0D9C6h, 12B7E950h, 8BBEB8EAh, 0FCB9887Ch dd 62DD1DDFh, 15DA2D49h, 8CD37CF3h, 0FBD44C65h dd 4DB26158h, 3AB551CEh, 0A3BC0074h, 0D4BB30E2h dd 4ADFA541h, 3DD895D7h, 0A4D1C46Dh, 0D3D6F4FBh dd 4369E96Ah, 346ED9FCh, 0AD678846h, 0DA60B8D0h dd 44042D73h, 33031DE5h, 0AA0A4C5Fh, 0DD0D7CC9h dd 5005713Ch, 270241AAh, 0BE0B1010h, 0C90C2086h dd 5768B525h, 206F85B3h, 0B966D409h, 0CE61E49Fh dd 5EDEF90Eh, 29D9C998h, 0B0D09822h, 0C7D7A8B4h dd 59B33D17h, 2EB40D81h, 0B7BD5C3Bh, 0C0BA6CADh dd 0EDB88320h, 9ABFB3B6h, 03B6E20Ch, 74B1D29Ah dd 0EAD54739h, 9DD277AFh, 04DB2615h, 73DC1683h dd 0E3630B12h, 94643B84h, 0D6D6A3Eh, 7A6A5AA8h dd 0E40ECF0Bh, 9309FF9Dh, 0A00AE27h, 7D079EB1h dd 0F00F9344h, 8708A3D2h, 1E01F268h, 6906C2FEh dd 0F762575Dh, 806567CBh, 196C3671h, 6E6B06E7h dd 0FED41B76h, 89D32BE0h, 10DA7A5Ah, 67DD4ACCh dd 0F9B9DF6Fh, 8EBEEFF9h, 17B7BE43h, 60B08ED5h dd 0D6D6A3E8h, 0A1D1937Eh, 38D8C2C4h, 4FDFF252h dd 0D1BB67F1h, 0A6BC5767h, 3FB506DDh, 48B2364Bh dd 0D80D2BDAh, 0AF0A1B4Ch, 36034AF6h, 41047A60h dd 0DF60EFC3h, 0A867DF55h, 316E8EEFh, 4669BE79h dd 0CB61B38Ch, 0BC66831Ah, 256FD2A0h, 5268E236h dd 0CC0C7795h, 0BB0B4703h, 220216B9h, 5505262Fh dd 0C5BA3BBEh, 0B2BD0B28h, 2BB45A92h, 5CB36A04h dd 0C2D7FFA7h, 0B5D0CF31h, 2CD99E8Bh, 5BDEAE1Dh dd 9B64C2B0h, 0EC63F226h, 756AA39Ch, 026D930Ah dd 9C0906A9h, 0EB0E363Fh, 72076785h, 05005713h dd 95BF4A82h, 0E2B87A14h, 7BB12BAEh, 0CB61B38h dd 92D28E9Bh, 0E5D5BE0Dh, 7CDCEFB7h, 0BDBDF21h dd 86D3D2D4h, 0F1D4E242h, 68DDB3F8h, 1FDA836Eh dd 81BE16CDh, 0F6B9265Bh, 6FB077E1h, 18B74777h dd 88085AE6h, 0FF0F6A70h, 66063BCAh, 11010B5Ch dd 8F659EFFh, 0F862AE69h, 616BFFD3h, 166CCF45h dd 0A00AE278h, 0D70DD2EEh, 4E048354h, 3903B3C2h dd 0A7672661h, 0D06016F7h, 4969474Dh, 3E6E77DBh dd 0AED16A4Ah, 0D9D65ADCh, 40DF0B66h, 37D83BF0h dd 0A9BCAE53h, 0DEBB9EC5h, 47B2CF7Fh, 30B5FFE9h dd 0BDBDF21Ch, 0CABAC28Ah, 53B39330h, 24B4A3A6h dd 0BAD03605h, 0CDD70693h, 54DE5729h, 23D967BFh dd 0B3667A2Eh, 0C4614AB8h, 5D681B02h, 2A6F2B94h dd 0B40BBE37h, 0C30C8EA1h, 5A05DF1Bh, 2D02EF8Dh...;***************************************************************************;; CRC32 computes a CRC-32 value for a data packet of arbitrary length.; See W. David Schwaderer's book "C Programmer's Guide to NetBIOS" for; details concerning the algorithm.;; Input:; DS:SI = Address of CRCTable; ES:DI = Address of input buffer; CX = Number of bytes to process;; Output:; DX:AX = 32-bit CRC value;;***************************************************************************CRC32 proc near mov ax,0FFFFh ;Initialize DX:AX to mov dx,ax ;0FFFFFFFFhCRC32_1: push cx ;Save CX mov bl,byte ptr es:[di] ;Get next byte in BL inc di ;Increment input pointer xor bl,al ;Compute an index into the xor bh,bh ;CRCTable array and convert shl bx,1 ;it to an offset address shl bx,1 add bx,si mov cx,word ptr [bx+2] ;Fetch 32-bit value from mov bx,word ptr [bx] ;CRCTable into CX:BX mov al,ah ;Shift DX:AX right 8 bits mov ah,dl mov dl,dh xor dh,dh xor ax,bx ;XOR CX:BX into DX:AX xor dx,cx pop cx ;Restore CX from the stack loop CRC32_1 ;Loop until done not ax ;Flip the bits to compute not dx ;the 1's complement ret ;Return to the callerCRC32 endp

Этот же алгоритм на языке Delphi приведён в прилагаемом к пояснительной записке диску.

Циклический избыточный код (Cyclic redundancy check, CRC) -- алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных, а также вычисления хеш-функций. CRC является практическим приложением помехоустойчивого кодирования, основанного на определенных математических свойствах циклического кода.