Как яндекс находит плагиат. И как бороться со склейкой.

Да но там еще другие операции будут. И числа 12 байтные :-)

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

По поводу ключа такой базы. В классической технологии шинглов (с длинной шингла в 10 слов) для документа в 100 кб потребуется 631 шингл (хеш 10 слов)

Количество контента = (100 * 1024) * 0.5 (0.5 - цифра с потолка, будем предпологать что контента ровно половина, остальное разметка)

Т.о количество контента = 51200

Средняя длинна слова с пробелом пусть будет 8 (опять цифра с потолка), тогда

Количество слов в таком документе будет 6400

Таким образом количество 10 словных шинглов будет (6400/10) - 9 = 631

Получается что ключ будет очень большой, а именно длинной в 631 шингл

Нет супер шингл не такой большой. Это один или несколько шинглов взятых по какойто хитрой формуле, делающию его помехоустойчивым. Т.е. супершингл это не контрольная сумму шинглов, а хитрый индикатор документа.

PS Шинглы ситаються в захлест их 6400-9.

При чем тут шинглы? Вы сами запутались. Я о шинглах здесь ни одного слова не написал и не имел их в виду! А писал о числе сравнений для определения дубликатов. Шинглы к этому вопросу перпендикулярно стоят. Быстроту сравнений они не повышают, так как здесь главное хранение данных по месту, определяемому хешкодом.

Или Вы шинглы собрались также хранить (в хеш таблице)? Это ОЧЕНЬ не экономно, так как число слов практически равно числу шинглов и тогда размер индекса возрастет на порядок. :)

Да и что Вам даст равенство друг другу одного шингла? Что по десять слов в текстах совпадают?

Вообще Вы интересный человек :)

Я у Вас совета не спрашивал, что мне читать или не читать. Поэтому прошу: воздержитесь от советов, когда я у Вас их не спрашиваю явно. Это похоже на совет почитать Онегина, которого я наизусть знаю... Мне нервы надо беречь :)

Точно, их 6400-9. Я говорил о классических шинглах

Hkey, По все видимости, вы провели хорошую работу по разбору алгоритма шинглов. Похвально. Но Выши рассуждения, имх - чистая математика. Т.с работа в лоб. Вы верно заметили, что основная работа по расчету дублей(нечетких дублей) ведется в пределах кластера, но есть меленькая неточность. Вы обращали внимание на то, что склеиваются, в основном, новые страницы, а вот страницы с большой разницей во времени, чаще всего, не склеины. (Возьмите любую известную тему по программированию, физике и т.д.) Там не много слеек.

Похоже, что действительно склейка идет в реальном времени на основе контрольных сумм.(аналогично спам-защите на почтовых серверах. Не раз говорилось что алгоритмы одинаковые). Если же дубль документа появляется через значительное время ппосле оригинала - то скорее всего склейки не будет.

PS Затрат времени и рессурса, при таком подходе, - куда меньше

Да я этот эффект не знал.

Но все равно клеяться не только новые страницы.

Есть идея про двойную проверку. Что некоторые документы проверяються намного более строго. Этому есть подтвержения в статьях Яндекса (если кто не верит могу процетировать) и здравый смысл, что например, если сайты связаны то их нужно проверить более шестко.

Зачем сравнивать каждый с каждым? Хэш + выборка по ключу при новой индексации. Сравниваются только с теми записями, у которых тот же хэш.

В Яндексе скорее всего Oracle стоит, там и больше миллиарда записей бывает в базах данных. Их можно как-то разбить, еапример, для начала анализировать главные страницы сайтов, их явно не больше нескольких миллионов в Рунете (зона ru + русскоязычные в других зонах). А уж с миллионными табличками тот же Oracle спокойно справляется если индексы нормально сделать и запросы оптимизировать.

Вы меня или вас не понимаем.

1. Выборки Шинглов и Супер шинглы для чего то нужны. Или что бы статьи яндекс про них писал.

2. Можно найти огромное к- во документов в которых совпадает один и тот же ключ.

3. Если тупо считать контрольную сумму, то малейшее изменение приводит к смене ключа.

По теме

------------------------------------------------------------

Может кто-то провести экспирименты.

Мне нужно 5-10 добровольцев. Если получиться, то вышлю прогу им бесплатно. Собираюсь написать такую программу "антишингл".

Первый - на сайте одновременно добавить две страницы.

Первая слова идут в нормальном порядке, вторая в обратном.

1. Мама мыла раму большой зеленой тряпкой. Я наблюдал за этим.

2. Этим за наблюдал Я. Тряпкой зеленой большой раму мыла мама.

Нужен, чтобы понять шинглы считаються с учетом расположения слов или без учета.

Еще один экспиримент:

Замена части букв на транслит.

Так спамеры поступают.

1. Электронным

2. Элеkтpонныm

Если получиться, то прогу легко написать.

И последний экспиримент:

1. Мама мыла раму большой зеленой тряпкой. Я наблюдал за этим.

2. Мамы мыли рамы большими зелеными тряпками. Я наблюдали за этими.

Хочу понять шинглы считаються тупо по словам или продвинуто по словоморфам.

Hkey

Идея не плохая.

Я даже со стула упал :)

Но вы не учли, сколько железа (серверов) нужно для такого алгоритма.

Я думаю все намного проще.

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