Задача определения заимствований и дубликатов является сложной и сильно зависит от типа заимствования: плагиат, использование идеи, копипаст, рерайтинг и т.д. При этом существуют множество ее разновидностей: установление приоритета в сетевых публикациях, удаление частично измененного копипаста, сравнение документа по контенту, установление смысловой близости документа.
Поиск дубликатов и плагиата среди веб-страниц является одним из главных направлений сравнения текстов. Аналогичные же методы используются такой системой, как антиплагиат, определяющей оригинальность, например, выпускных квалификационных работ и рефератов студентов, научных публикаций.
Одним из эффективных алгоритмов определения сходства документов на предмет заимствования и определения, является алгоритм шинглов, подробно рассмотренный и реализованный в представленной работе. Шинглы – выделенные для сравнения из тела текста отдельные части (подстроки), с определенным количеством слов в его последовательности для проверки на уникальность. Алгоритм шинглов предназначен для нечеткого поиска дубликатов текста. «Нечеткость» в данном случае подразумевает, что документ не является полной копией заданного, вхождение дублей ищется не точно, а частично: дубликат строки, отдельных словосочетаний, абзацев и т.д.
Одно из бесспорных достоинств алгоритма шинглов для задачи определения нечетких дубликатов, в том, что в отличие от алгоритма векторной модели, или иначе «мешка слов», не чувствителен к смысловой близости текстов. Он реагирует исключительно на повторяющиеся фрагменты текстов, причем речь идет не о типовых словосочетаниях, а о повторах словесных оборотов текста.
Изучение и реализация алгоритма шинглов, его тестирование и практическое применение являются интересной и полезной задачей. Таким образом, тема выпускной квалификационной работы является актуальной и востребованной. Решение задачи определения нечетких дубликатов, и копирования является на настоящий момент важным и практически нужным.
Алгоритм шинглов является одним из алгоритмов определения близости текстов. Определение близости текстов, выявление нечетких дубликатов, определение копирайта – важные задачи для современной глобальной сети. Алгоритмов сравнения текстов существует огромное количество, многие из них достаточно эффективны в своем диапазоне решаемых задач. Правильное применение нужного алгоритма зависит от конкретной задачи, стоящей перед исполнителем. На самом деле, именно характер данных, их объём и другие особенности предметной области диктуют алгоритм обработки.
Алгоритм шинглов используется для решения:
Задачи сравнения текстов для определения тематической близости;
Задачи сравнения текстов для определения нечетких дубликатов;
Задачи автоклассификации текстовой информации.
Общий алгоритм шинглов очень распространен в сети, особенно на сайтах по СЕО и рерайтингу [1]. Задача определения заимствований и дубликатов является сложной и сильно зависит от типа заимствования: плагиат, использование идеи, копипаст, рерайтинг и т.д. При этом существуют множество ее разновидностей:
Установление приоритета в сетевых публикациях;
Удаление частично измененного копипаста;
Сравнение документа по контенту;
Установление смысловой близости документа.
Поиск дубликатов и плагиата среди веб-страниц является одним из главных направлений сравнения текстов. Аналогичные же методы используются такой системой, как антиплагиат, определяющей оригинальность, например, выпускных квалификационных работ и рефератов студентов.
Как уже было отмечено выше, задача сравнения текста актуальна и для рерайтинга, что подтверждает большое количество ресурсов, посвященных определению доли оригинальностизаимствований в тексте, а также использованных в работах источников [1].
Рассмотрим подробнее обобщенный алгоритм при сравнении текста поэтапно. Он включает в себя последовательное решение следующих задач.
Канонизация текста;
Разбиение его на шинглы;
Вычисление, через выбранные функции, хэш значений шинглов;
Сравнение и определение результата.
Канонизация текста – приведение оригинального текста к единой нормальной форме, его очищение от всех не несущих смысла составляющих, которые не участвуют в сравнении.
К таким составлюющим относят:
стоп-слова;
предлоги;
союзы;
знаки препинания;
HTML теги (для гипертекста).
Эти составляющие не влияют на смысл текста, но могут повлиять на хэш-сумму шингла, если их не убрать. Например, хэш-суммы двух практически одинаковых высказываний, «уже поздно» и «уже поздно!», будут различными из-за одного символа, не влияющего на смысл. Поэтому они не должны участвовать в сравнении.
Нередко предполагается удаление имен прилагательных, поскольку они, зачастую, несут эмоциональную, а не смысловую нагрузку. Однако, выбор данного параметра может зависеть и от типа сравниваемых текстов, и не всегда имеет смысл.
Канонизация текста также требует приведения имен существительных в нормальную форму. Нормальная форма слова: именительный падеж, единственное число. Иногда можно оставлять только их корневые значения. После очищения получается текст, пригодный для последующей обработки –разбиения на шинглы.
С канонизацией текста можно экспериментировать, так как подход к ней сильно изменяет конечный результат. Если есть цель сравнить и выявить полные тексты-дубликаты, которые во множестве присутствуют в выдаче поисковых систем, то можно не удалять, например, прилагательные; не использовать стеммер для получения одних корней слов. Можно вообще не приводить слова к нормальной форме. Тогда алгоритм будет чувствительным к изменению формы текста. Зато при проведении такой обработки, алгоритм будет не чувствителен к небольшим изменениям при копипасте.
Следующим этапом является разбиение текста на шинглы. В нашей работе выбран наиболее популярный вариант – шингл из 10 слов, внахлёст.
Принцип алгоритма шинглов заключается в сравнении случайной выборки контрольных сумм шинглов (подпоследовательностей) двух текстов между собой. Проблема алгоритма заключается в количестве сравнений, ведь это напрямую отражается на производительности. Увеличение количества шинглов для сравнения характеризуется экспоненциальным ростом операций, кто критически отразится на производительности.
Существуют различные подходы к вычислению контрольных сумм [3], которые получают с помощью хэширования по различным алгоритмам (SHA1, SHA3, CRC32, MD5 и т.д). Можно взять сразу несколько хэшей, полученных по различным алгоритмам, и выборочно сравнить их. Однако, в нашей работе мы выбрали популярный метод MD5.
Сравнение и получение результата – оценки степени сходства документов, определение нечетких дубликатов. Он зависит от полученного на прошлом этапе результата. Как правило, это наиболее простой этап. Возможны следующие варианты:
Нахождение пересечения (общих элементов) двух множеств хэшей, и, в зависимости от результата, оценка сходства. Это вариант для использования одного алгоритма хэширования.
Поэлементное сравнение полученных строк с хэш-суммами из обеих текстов, в случае использования нескольких алгоритмов хэширования.
Мы в данной работе выбрали первый вариант.
Отметим, что выбор в данной работе наиболее распространенных методов и параметров алгоритма шинглов сделан осознанно, так как это отражает поведение основных ресурсов проверки на совпадение текстов.
В заключение отметим, что в рассматриваемой работе описан процесс анализа и выбора алгоритмов сравнения близости текстов, на основе которых реализована программа для определения схожести текстов и поиска нечетких дубликатов на основе алгоритма шинглов. Программа реализована на языке высого уровня C# в виде проекта в VisualStudio 2010.
Библиографический список
Проверка текста на уникальность. Алгоритм ШИНГЛОВ онлайн. [Электронный ресурс]: 2017. URL: http://seo-tank.ru/shingle.php
Мешков В.Е., Мешкова Е.В. Определение авторского стиля на основе статистическо-морфологического анализа произведения. Теория операторов, комплексный анализ и математическое моделирование: Тезисы докладов XIII Международной научной конференции (пос. Дивноморское, 7-14 сентября 2016г.). – Владикавказ: ЮМИ ВНЦ РАН, 2016. – 257с.
3. Мешков В.Е., Дьячкин Е.А. . Задача определения близости документов. Материалы Всероссийской нучно- практической конференции «Научный потенциал высшей школы – будущему России», Волгодонск, 2017 (РИНЦ)