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

Алгоритм поиска и сравнения отпечатков документов является одним из наиболее популярных алгоритмов для поиска плагиата. Он основан на выборе множества небольших участков документа в качестве отпечатка этого документа и сравнения этого отпечатка с другими [13,14]. В данной работе этот алгоритм применяется на генерализированных исходных кодах.

Алгоритм использует параметры и - положительные целочисленные значения, смысл которых станет понятен при описании алгоритма.

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

Введем определение как последовательной подстроки документа длиной символов [15].

Поиск отпечатков

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

Чтобы сделать это с минимальными затратами по времени, используется алгоритм кольцевого хэша [15]. Этот метод позволяет вычислять за короткое время (алгоритмическая сложность ) хэш подстроки из символов из значения хэша для подстроки . Для этого применяется следующая формула:

,

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

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

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

Схематическое представление вычисления отпечатка на строковой последовательности “adorunrunrun”

Рисунок 3. Схематическое представление вычисления отпечатка на строковой последовательности “adorunrunrun”

 
< Пред   СОДЕРЖАНИЕ   Загрузить   След >