Ежедневно поисковый робот индексирует многие миллионы документов. Если бы для обнаружения дублей поисковой машине требовалось сопоставить между собой все существующие документы (каждый с каждым), ей пришлось бы произвести миллиарды миллиардов операций. Будь даже полнотекстовое сравнение одного документа со всеми прочими доступно, оно оказалось бы малоэффективным. Небольшая перестановка слов, знаков, предложений в тексте при сопоставлении с идентичным ему в остальном документе исключала бы совпадение.
На помощь поисковой машине были привлечены математика и лингвистика. Для сравнения огромного количества документов в базе поисковика применяется так называемый метод шинглов. Он крайне трудоемок, но современные компьютеры с ним справляются. Детально концепцию описывает опубликованная в апреле 1997 года статья «Синтаксическая кластеризация в Сети» (Syntactic clustering of he Web) авторства А. Бродера, С. Глассмана, М. Манассе и Г. Цвейга, которая вошла в сборник трудов Шестой международной конференции World Wide Web.
Алгоритм поиска дубликатов
В переводе с английского shingle означает «гонт». Яснее не стало? Гонт – это кровельный материал, а точнее, небольшие дощечки с пазами и выступами, которые собираются в один лист. Применительно к поисковым системам шинглы – это алгоритм для поиска дубликатов путем вычисления и сопоставления контрольных сумм выборки канонизированных (см. значение термина ниже) словосочетаний длиной от одной до десяти (приблизительно) единиц. Работает это следующим образом.
1. Все слова в тексте приводятся к исходным словоформам, стоп — слова (предлоги, союзы, частицы, знаки препинания и другие незначимые и не несущие смысловой нагрузки элементы) удаляются. Это называется канонизацией текста. Таким образом получается исходник для вычисления шинглов. Более жесткая канонизация может учитывать синонимы и, например, исходное слово «недомогать» заменять на «болеть». Это помогает выявлять тексты, где лишь некоторые исходные слова заменены близкими по смыслу
2. Канонизированный текст делится на фразы длиной от трех до десяти (примерно) слов. Разбивка осуществляется или встык, или внахлест, когда в последующую фразу включено одно или несколько последних слов из предыдущей. Малейшее изменение канонизированного текста – и возникают совсем другие шинглы. Чтобы конструкция не разрушилась как карточный домик, в тексте нужно задать четкие, но малоочевидные точки отсчета для членения на шинглы. В качестве примера приведем схожий алгоритм «Яндекса» под названием «Спамооборона», где устанавливаются границы, цитата: «от буквы “ю” до буквы “ю”; или от двухбуквия, сумма численных значений символов (букв) которого кратна 50, до следующего такого же».
