Метод шинглов: алгоритм, применение и основные параметры.

Алгоритм шинглов до сих пор популярен при поиске дубликатов текста. Долгое время он был основным инструментом оценки неявных дубликатов и копипаста. Теперь больше используются различные модификации алгоритма шинглов, позволяющие определять простой рерайт (перестановку слов, абзацев, небольшие изменения). При этом алгоритм не реагирует на смысловую и тематическую близость текстов, чем, например, грешит система Antiplagiat.ru. В этом его принципиальное отличие от векторной модели представления текста (иначе модель «мешка слов»).
Итак, в чем суть алгоритма шинглов (ячеек, чешуек)? Текст разбивается на кусочки (ячейки) – шинглы – в виде набора подстрок с определенным количеством слов. Таким образом, сравниваются два текста – два набора подстрок. Если подстроки совпадают, это говорит о частичном заимствовании. При этом сравниваются не слова в каждой подстроке, а контрольные суммы подстрок. Для каждой части текста она получается с помощью хэш-функции. Пример на кусочке текста:
Текст: «Выявление ключевых слов из контекста страницы применяется при составлении семантического ядра и проверки ресурса на релевантность запросу.»
Разбиваем на шинглы, длина шингла — 3 слова (предлоги отбрасываются):
Выявление ключевых слов | из контекста страницы применяется | при составлении семантического ядра | и проверки ресурса на релевантность | запросу
Это шингл без сдвига. А вот шингл внахлест, когда часть слов одного шингла попадает в следующий:
Выявление ключевых |слов|| из контекста |страницы|| применяется при |составлении || семантического ядра || и т.д.
Шинглы тогда будут следующие:
Выявление ключевых |слов
слов |из контекста |страницы
страницы| применяется при составлении
составлении || семантического ядра
и т.д.
Сразу видно, насколько увеличилось количество шинглов. Сдвиг может быть любым.
Шинглы могут быть на любое количество слов, чем шингл короче, тем точнее будет результат проверки. В основном длина шингла – от 3 до 10 слов. Существуют различные методы разбиения текста на шинглы:
— внахлест или друг за другом (должны ли подстроки включать в себя часть предыдущей подстроки);
— количество слов или символов в шингле.
Способ формирования шинглов сильно влияет на точность результата
Немного подробнее опишем алгоритм сравнения текстов методом шинглов.
1) Очищаем текст: убираем знаки препинания, предлоги, местоимения, стоп-слова (распространенные слова, не несущие информации: он, она, что, кто, либо, нибудь и т.п.), html-теги. Если этого не сделать, то хэш-суммы двух практически одинаковых высказываний, «уже поздно» и «уже поздно!», будут различными из-за одного символа, не влияющего на смысл.
2) Приводим все слова к нормальной форме. Этот пункт не всегда реализуется в алгоритме шинглов. Нормальная форма для существительного – единственное число, именительный падеж (уроков — урок), для глагола – неопределенная форма, «делать», «видеть» и т.д. Если этого не сделать, то нельзя будет распознать элементарное изменение текста: «директор видел» и «директор видит» будут разными фразами.
3) Разбиваем текст на шинглы. Вначале создаем массив слов текста с помощью разделителя (пробел), а затем склеиваем в шинглы, например, по 10 слов.
4) Получаем хэш суммы шинглов с помощью хэш-функций, например, в php – MD5($shingle). Главные требования к хэш-функции : скорость и минимум коллизий. Однако учитывая, что требования скорости в данном случае важнее, а на большой словарной базе вероятность коллизий небольшая, можно воспользоваться простыми хэш-функциями.;
5) Сравниваем хэш-суммы наборов шинглов. Чем больше совпадений –тем более вероятно, что один текст является частично заимствованным.

Как мы видим, сам алгоритм прост, но эффективен. Однако его вычислительная сложность резко возрастает с уменьшением длины шингла. Для больших текстов такой алгоритм будет довольно затратным по времени и вычислительной мощности. Хорошая реализация алгоритма шинглов онлайн представлена на сайте Seo-tank.ru
Благодаря тому, что текст можно хранить в виде набора шинглов, метод применяется в базах документов для определения степени оригинальности текста, что существенно повышает скорость сравнения текстов, а особенно первичной обработки.
Сейчас многие системы антиплагиата отрицают использование алгоритма шинглов, однако судя по результатам, используют его модификации, работающие на собранной ими базе текстов. Базовое отличие используемых систем –это сравнения с имеющейся базой документов, а особенно учебных материалов. Также используется метод ключевых слов, модификация метода «мешка слов» — иначе самостоятельные термины не могли бы попасть в плагиат, как у знаменитой системы Антиплагиат.ру.
Однако это не делает алгоритм шинглов бесполезным, поскольку им хорошо проверять отличие от базового текста в процессе рерайта.