Реализация алгоритма шинглов позволяет определять уровень идентичности двух документов. Зеленков Ю. Г. и Сегалович И.В. в своей работе «Сравнительный анализ методов определения нечетких дубликатов для Web-документов» подробно описали принцип алгоритмов шинглов разной величины для сравнения веб-документов.
Авторы публикации подробно анализируют технику определения идентичности документов. Они предлагают версию алгоритма шинглов, которая использует случайную выборку из анализируемого текста 84-х случайных шинглов.
Использование именно 84-х значений контрольных сумм, выбранных случайно, позволяет перевести алгоритм до уровня алгоритма супершинглов и мегашинглов, емкость ресурса которых значительно меньше.
Знание алгоритма определение нечетких дублей, позволит избежать проблемы при написании текстов для
поисковой продвижения. Можно выделить следующие этапы, через которые проходит текст при его сравнении:
- канонизации текста;
- разбиения его на шинглы;
- вычисления, через статические функции, 84-х хэшей шинглов;
- случайной выборки значений 84 контрольных сумм;
- сравнения и определения результата.
1. Канонизация текста.
Канонизация текста - приведение оригинального текста к единой нормальной форме через очищение его от всех вспомогательных единиц текста (предлогов, союзов, знаков препинания, тегов и прочее), которые не должны участвовать в сравнении. Часто предполагается также удаление имен прилагательных, поскольку они, как правильно, несут эмоциональную, а не смысловую нагрузку.
Канонизация текста также требует приведения имен существительных в именительный падеж, единственное числе, а иногда – оставление только их корневых значений.
После проведения всех указанных операций получается «чистый» текст, пригодный для сравнения.
2. Разбиение текста на шинглы.
Шинглы (от англ. – чешуйки) - выделенные для сравнения из тела статьи отдельные части текста, с определенным количеством слов в его последовательности для проверки на уникальность.
Шинглы могут быть на любое количество слов – от 3 до 10. Чем шингл короче, тем точнее будет результат проверки. При назначении размера шингла в 3 слова проверка, давшая 100% уникальности, является свидетельством оригинальности текста, поскольку совпадения словосочетаний встречаются практически в любом тексте.
Сравниваемые тексты нужно разделить на подпоследовательности (идущих друг за другом) слов и определить длину шингла в 10 слов. Такая выборка происходит не встык, а внахлест - это гарантирует, что поисковая система не пропустит ни одной строки подстроки.
Полученные наборы шинглов, после того как каждый из текстов разбит на подпоследовательности, равны количеству слов в документе минус длина шингла (-10) плюс один (+1).
3. Вычисление хэшей шинглов.
Принцип алгоритма шинглов базируется на сравнении случайно выбранных контрольных сумм шинглов (подпоследовательностей) двух документов.
Суть действия алгоритма заключается в том, чтобы найти верное количество контрольных сумм для сравнения. Завышенное число шинглов негативно отразится на результате, поскольку для сравнения будет произведено гораздо больше операций, что снизит производительность.
Для облегчения текст представляется в виде таблиц с набором контрольных сумм, рассчитанных для каждого шингла по 84-м статическим хэш-функциям. Все 84 строки (для каждого из документов) охарактеризованы соответствующей контрольной суммой.
Из обоих наборов случайным образом отбираются 84 значения – для каждого из документов – и сравниваются в соответствии с функциями своей контрольной суммы. Иными словами, потребуется 84 операции, чтобы сравнить тексты.
4. Случайная выборка 84 значений контрольных сумм.
Для увеличения производительности при сравнении элементов каждого из 84-х выбранных массивов нужно произвести случайную выборку контрольных сумм для каждой из строк. Выбор минимального значения из каждой строки в итоге даст набор наименьших значений контрольных сумм шинглов для каждой из хэш функций.
5. Получение результата.
Сравнение каждого из 84 элементов обоих документов выявляет соотношение одинаковых значений, что позволяет определить уровень идентичности, или уникальности каждого из текстов.
