Алгоритм поиска дубликатов

Алгоритм поиска дубликатов

В переводе с английского shingle означает «гонт». Яснее не стало? Гонт – это кровельный материал, а точнее, небольшие дощечки с пазами и выступами, которые собираются в один лист. Применительно к поисковым системам шинглы – это алгоритм для поиска дубликатов путем вычисления и сопоставления контрольных сумм выборки канонизированных (см. значение термина ниже) словосочетаний длиной от одной до десяти (приблизительно) единиц. Работает это следующим образом.

1. Все слова в тексте приводятся к исходным словоформам, стоп — слова (предлоги, союзы, частицы, знаки препинания и другие незначимые и не несущие смысловой нагрузки элементы) удаляются. Это называется канонизацией текста. Таким образом получается исходник для вычисления шинглов. Более жесткая канонизация может учитывать синонимы и, например, исходное слово «недомогать» заменять на «болеть». Это помогает выявлять тексты, где лишь некоторые исходные слова заменены близкими по смыслу

2. Канонизированный текст делится на фразы длиной от трех до десяти (примерно) слов. Разбивка осуществляется или встык, или внахлест, когда в последующую фразу включено одно или несколько последних слов из предыдущей. Малейшее изменение канонизированного текста – и возникают совсем другие шинглы. Чтобы конструкция не разрушилась как карточный домик, в тексте нужно задать четкие, но малоочевидные точки отсчета для членения на шинглы. В качестве примера приведем схожий алгоритм «Яндекса» под названием «Спамооборона», где устанавливаются границы, цитата: «от буквы “ю” до буквы “ю”; или от двухбуквия, сумма численных значений символов (букв) которого кратна 50, до следующего такого же».

3. Далее для каждого шингла вычисляется контрольная сумма (точнее, применяется хэш-функция). Проще говоря, последовательность слов превращается в последовательность цифр.

4. Затем формируется выборка шинглов, вернее, контрольных сумм и непосредственно сравнение и анализ документов. Из всех полученных контрольных сумм отбирается несколько десятков значений. Производится это путем случайной выборки, к примеру, 70 математических функций из заблаговременно составленного реестра, каждая из которых может описывать интересный для целей data mining параметр: пересечение, вложенность и т. д. Все шинглы документа пропускаются через каждое из 70 выражений, что дает на выходе значения, атрибутируемые тому или иному шинглу. Для каждой из 70 функций выбирается шингл с минимальным (возможны и иные критерии) значением контрольной суммы. В результате на базе анализируемого документа составляется сигнатура из 70 значений контрольных сумм. При сравнении с другим документом, который подвергся такой же операции, берутся шинглы, отобранные по совпадающим функциям. К примеру, если при отборе шинглов в обоих случаях было использовано 25 одинаковых функций из 70, то сравнение выполняется по 25 соответствующим контрольным суммам.

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

Конечно, алгоритм мы продемонстрировали лишь в общих чертах, чтобы дать представление о принципе поиска дубликатов методом шинглов.

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

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