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

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

ОПРЕДЕЛЕНИЕ ТЕКСТОВЫХ ЗАИМСТВОВАНИЙ И НЕЧЕТКИХ ДУБЛИКАТОВ НА ОСНОВЕ АЛГОРИТМА ШИНГЛОВ

Мешков В.Е.,

Царев А.П.

Огромное количество текстов, обмен контентом и копирование, в том числе и без указания первоисточника, сделали выявление нечетких дубликатов, определение копирайта и плагиата важными задачами для современной глобальной сети. Существует огромное количество достаточно эффективных алгоритмов сравнения текстовых документов. Правильное применение нужного алгоритма зависит от конкретной задачи, стоящей перед исполнителем, характера и объёма данных, других особенностей предметной области.[2]

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

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

Одним из эффективных алгоритмов определения сходства документов на предмет заимствования и определения, является алгоритм шинглов, подробно рассмотренный и реализованный в представленной работе. Шинглы - выделенные для сравнения из тела текста отдельные части (подстроки), с определенным количеством слов в его последовательности для проверки на уникальность. Алгоритм шинглов предназначен для нечеткого поиска дубликатов текста. «Нечеткость» в данном случае подразумевает, что документ не является полной копией заданного, вхождение дублей ищется не точно, а частично: дубликат строки, отдельных словосочетаний, абзацев и т.д.

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

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

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

Алгоритм шинглов используется для решения:

1. Задачи сравнения текстов для определения тематической близости;

2. Задачи сравнения текстов для определения нечетких дубликатов;

3. Задачи автоклассификации текстовой информации.

Общий алгоритм шинглов очень распространен в сети, особенно на сайтах по СЕО и рерайтингу [1]. Задача определения заимствований и дубликатов является сложной и сильно зависит от типа заимствования: плагиат, использование идеи, копипаст, рерайтинг и т.д. При этом существуют множество ее разновидностей:

Установление приоритета в сетевых публикациях;

Удаление частично измененного копипаста;

Сравнение документа по контенту;

Установление смысловой близости документа.

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

Как уже было отмечено выше, задача сравнения текста актуальна и для рерайтинга, что подтверждает большое количество ресурсов, посвященных определению доли оригинальности\заимствований в тексте, а также использованных в работах источников [1].

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

1. Канонизация текста;

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

3. Вычисление, через выбранные функции, хэш значений шинглов;

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

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

К таким составляющим относят:

стоп-слова;

предлоги;

союзы;

знаки препинания;

HTML теги (для гипертекста).

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

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

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

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

Следующим этапом является разбиение текста на шинглы. В нашей работе выбран наиболее популярный вариант - шингл из 10 слов, внахлёст.

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

Существуют различные подходы к вычислению контрольных сумм [3], которые получают с помощью хэширования по различным алгоритмам (SHA1, SHA3, CRC32, MD5 и т.д). Можно взять сразу несколько хэшей, полученных по различным алгоритмам, и выборочно сравнить их. Однако, в нашей работе мы выбрали популярный метод MD5.

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

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

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

Мы в данной работе выбрали первый вариант.

Отметим, что выбор в данной работе наиболее распространенных методов и параметров алгоритма шинглов сделан осознанно, так как это отражает поведение основных ресурсов проверки на совпадение текстов.

В заключение отметим, что в рассматриваемой работе описан процесс анализа и выбора алгоритмов сравнения близости текстов, на основе которых реализована программа для определения схожести текстов и поиска нечетких дубликатов на основе алгоритма шинглов. Программа реализована на языке высого уровня C# в виде проекта в VisualStudio 2010.

шингл заимствование дубликат плагиат

Библиографический список

1. Проверка текста на уникальность. Алгоритм ШИНГЛОВ онлайн. [Электронный ресурс]: 2017. URL: http://seo-tank.ru/shingle.php

2. Мешков В.Е., Мешкова Е.В. Определение авторского стиля на основе статистическо-морфологического анализа произведения. Теория операторов, комплексный анализ и математическое моделирование: Тезисы докладов XIII Международной научной конференции (пос. Дивноморское, 7-14 сентября 2016г.). - Владикавказ: ЮМИ ВНЦ РАН, 2016. - 257с.

3. Мешков В.Е., Дьячкин Е.А.. Задача определения близости документов. Материалы Всероссийской нучно- практической конференции «Научный потенциал высшей школы - будущему России», Волгодонск, 2017 (РИНЦ)

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