Сбор информации осуществляется по мере наполнения СУБД студентами загрузившими свои бинарные файлы в систему. Обработка файлов и выполнение основной функции выполняется при вызове операции преподавателем.

3. Математический аппарат подсистемы

Токенизация

Пусть у нас есть две строки кода for (int i = 0; i <= n; i + +) и for (int j = 0; (j ? 1) < n; j + +). Очевидно, что у них одинаковая функциональность, и плагиатор мог из одной получить другую без особых усилий, а для ранее описанных представлений они совершенно различны. Для борьбы с такого рода изменениями придуман метод токенизированного представления кода. Основная идея этого представления это сохранение существенных и игнорирование всех поверхностных (то есть легко модифицируемых) деталей кода программы. Процедура токенизации выглядит примерно так:

Каждый оператору языка заменяется на уникальный ключ.

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

Алгоритм Хескела

Пусть у нас есть две программы, представим их в виде строк токенов a и b соответственно. Одним из критериев сходства строк считается длина их наибольшей общей подпоследовательности. Мы всегда можем найти такой элемент строки ai, что НОП строк a0 = a|a|a|a|?1. aia1. ai?1 и b будет значительно меньше (максимум в два раза), чем НОП (a, b) (если НОП (a, b) > 1). Чтобы избежать этого явления можно воспользоваться алгоритмом сравнения строк Хескела, он требует нескольких проходов, но работает за линейное время. Разобьем строки a и b на k-граммы (подстроки длины k). Найдем те k-граммы, которые встречаются в a и b только по одному разу. Для каждой такой пары проверим совпадают ли элементы строк, непосредственно лежащие над ними; если это так, то проведем ту же проверку и для них и так далее, пока несовпадение не будет найдено. Аналогично для строк, лежащих ниже соответствующих k-граммов. Получаем набор общих непересекающиеся подстрок a и b. Их общая длина может служить мерой схожести программ соответвующих a и b. Достоинства.

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

Недостатки.

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

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

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

Нельзя организовать базу данных, ускоряющую проверку "один против всех".

Жадное строковое замощение

Рассмотрим эвристический алгоритм получения жадного строкового замощения (The Greedy String Tiling). Он получает на вход две строки символов над определенным алфавитом (у нас это множество допустимых токенов), а на выходе дает набор их общих непересекающихся подстрок близкий к оптимальному. Подстроку, входящую в этот набор, мы будем называть тайлом (tile). Пусть P и T токенизированные представления сравниваемых программ.

MinimumMatchLength - минимальная длина наибольшего общего префикса строк Pp и Tt, при которой он учитывается алгоритмом.

Длина самого большого из пока найденных на текущей итерации алгоритма общих префиксов строк Pp и Tt обозначается maxmatch.

Набор тайлов мы будем обозначать как tiles.

Множество, содержащие кандидатов на попадание в набор тайлов, обозначется mathes.

Алгоритм можно разделить на две фазы:

1. Ищутся наибольшие общие подстроки P и T, состоящие только из непомеченных элементов (вначале алгоритма все элементы непомечены). Для этого используются три вложенных цикла: первые пробегает по всем возможным Pp, второй по всем Tt, а третий находит наибольший общий префикс Pp и Tt. Далее существует три варианта в зависимости от соотношения величин maxmatch и найденного префикса: a) если maxmatch меньше, то мы удаляем из списка общих подстрок matches все до этого добавленные и помещаем туда найденный префикс. b) если maxmatch больше, то ничего не меняем. c) если они равны, то добавляем наибольший общий префикс Pp и Tt к списку matches.2. Проходим по списку, если текущий элемент списка подстрока, не содержащая помеченных элементов, то помещаем ее в выходной набор tiles (теперь эту подстроку называют tile отсюда и название алгоритма), помечаем все элементы рассматриваемой строки, входящие в P и T. Если длины строк в списке (maxmatch) больше чем MinimumMatchLength, то переходим к первой фазе. Приведем псевдокод этого алгоритма:

Greedy-String-Tiling (String P, String T)

{

tiles = {};

do {

maxmatch = MinimumMatchLength;

Forall unmarked tokens Pp in P

{

Forall unmarked tokens Tt in T

{

j = 0;

while (Pp+j == Tt+j) && unmarked (Pp+j) && unmarked (Tt+j)

j++;

if (j == maxmatch)

{

matches = matches ? match (p, t, j);

} else if (j > maxmatch)

{

matches = {match (p, t, j) }; maxmatch = j;

}

}

}

Forall match (p, t, maxmatch) Ѓё matches

{

if (not occluded)

{

for j = 0. (maxmatch ? 1)

{

mark (Pp+j); mark (Tt+j);

}

tiles = tiles ? matches (a, b, maxmatch);

}

}

} while (maxmatch > MinimumMatchLength); return tiles;

}

}

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

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

Заметим, что “not occluded” (не пересекающиеся) означает, что ни один токен с Pp по Pp+maxmatch?1 и с Tt по Tt+maxmatch?1 не был помечен на предыдущих итерациях. Как бы то ни было, меньшие тайлы не могут быть созданы до больших. Этого достаточно, чтобы утверждать, что нужно про-верять только метки на концах предполагаемого тайла, чтобы узнать содер-жит ли он помеченные символы. Очевидно, это можно проделать за O (1), тогда асимптотическая сложность времени работы всего алгоритма в худ-шем случае O (n3). h (Tj?1Tj. Tj+|P |?2. Tj+|P |?1

Достоинства.

Преимущества токенизированного представления.

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

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

Алгоритм нечувствителен к перестановкам больших фрагментов кода.

Недостатки.

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

Разбиение совпадения на блоки, вставкой или заменой оператора на похожий (например, for на while), каждый длиной меньше MinimumMatchLength, ведет к полному игнорированию совпадения.

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

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

Метод отпечатков

В этом алгоритме мы представляем токенизированную программу в виде набора отпечатков (меток, fingerprints), так чтобы эти наборы для похожих программ пересекались. Этот метод позволяет организовать эффективную проверку по базе данных. Метод отпечатков можно представить в виде четырех нижеследующих шагов:

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

2. Выделяем некоторое подмножество их хэш-значений, хорошо характеризующее P. Проделываем те же шаги для токенизированных программ T1, T2. Tn и помещаем их выбранные хэш-значения в хэш-таблицу.

3. С помощью хэш-таблицы (базы) получаем набор участков строки P, подозрительных на плагиат.

4. Анализируем полученные на предыдущем шаге данные и делаем выводы.

Если в двух программах есть общая подстрока длиной, например, два символа, то необязательно, что мы нашли плагиат - скорее всего это совпадение просто случайность и обусловлено малой мощностью нашего алфавита. То есть значение k может способствовать игнорированию “шума”, но при больших значениях k, мы можем проигнорировать настоящий случай плагиата, поэтому это число нужно выбирать с осторожностью. Пусть наша хэш-функция - это h, а h1, h2. h|P |?k+1 - последовательность значений хэш-функций, полученных на шаге 1. Рассмотрим некоторые возможные реализации шага 2:

Наивный подход заключается в выборе каждого i-ого из n хэш-значений, но он неустойчив к модификациям кода. (Если мы добавим в начало файла один лишний символ, то получим совершенно другое подмножество хэш-значений после выполнения алгоритма.)

3.4 Формирование отчетности