Hkey

Hkey
Рейтинг
222
Регистрация
30.09.2006
Интересы
Java
T.R.O.N:
Hkey, По все видимости, вы провели хорошую работу по разбору алгоритма шинглов. Похвально. Но Выши рассуждения, имх - чистая математика. Т.с работа в лоб. Вы верно заметили, что основная работа по расчету дублей(нечетких дублей) ведется в пределах кластера, но есть меленькая неточность. Вы обращали внимание на то, что склеиваются, в основном, новые страницы, а вот страницы с большой разницей во времени, чаще всего, не склеины. (Возьмите любую известную тему по программированию, физике и т.д.) Там не много слеек.
Похоже, что действительно склейка идет в реальном времени на основе контрольных сумм.(аналогично спам-защите на почтовых серверах. Не раз говорилось что алгоритмы одинаковые). Если же дубль документа появляется через значительное время ппосле оригинала - то скорее всего склейки не будет.
PS Затрат времени и рессурса, при таком подходе, - куда меньше

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

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

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

На меил ру пришло 684 письма. Спасибо, работа качественная.

lis:
Цена прежняя??

Да преждняя, скоро измениться грядет АП базы! Апы для покупателей бесплатные.

zaara:
Если не ошибаюсь есть несколько склеяных ресурсов в пресс релизах.

Вроде бы нет хотя они почти все на одном движке. Можно мне в личку инфу?

Можно лого для рекламного агенства?

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

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

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

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

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

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

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

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

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

mik-a-el:
Почему 1000 000 и причем здесь задержки сети? Операции идут в пределах кластера серверов.
К тому же операции сравнения чисел - самые быстрые из всех.

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

ХренРедькиНеСлаще:
Hkey, представьте (мысленно) Яндекс прочитал документ и "индексирует" его. Документ он режет на предложения (по точкам и т.д.). Для каждого предложения считается хеш - целое число, которая определяет в какой позиции индекса Яндекса нужно хранить это предложение и информацию где это предложение проиндексировано (id документf и номер предложения).

Если предложение ранее не было в индексе, ячейка индекса (определяемая подсчитанным хешем) будет пусто, что означает: ДУБЛЕЙ предлжения НЕТ! Если ячейка занята, то это означает, что дубли есть и даются "координаты" дублей.

Не нравятся Вам "предложения" возьмите для индексации другие куски текста (всю страницу, например)...

И где Вы видите миллиард операций? Когда операция одна: подсчет хеша и проверка "ячейки индекса" с порядковым номером, равным подсчитанному хешу.

Пожалуйста прочитайте статьи Яндекса про шинглы, выборку шинглов и супер шинглы!

По предложениям осознал, что действительно на проверку супершинглов тратиться на порядки меньше времени. Но статьи Яши противоречевы в одной статье говориться о наличие одного супер шингла на документ в другом что их несколько. Мы не знаем алгоритм проверки на примерное соответствие супер шинглов - он может быть громоздким. Тем более для супер шингла нужно изменить 10-20% шиглов и он уже другой.

Есть предположение (в одной из статей написано "для веб документов используеться выборка 85 шинглов."), что некоторые документы перепроверяються более жестоко, даже, если супер шинглы разные! Как написано раньше.

"Не нравятся Вам "предложения" возьмите для индексации другие куски текста (всю страницу, например)..."

Хорошо сравниваю хеш 2 статей отличающающихся на один символ! Сравнил два получил два уникальных текста. Если бы Яндекс нахолил дубли так же... Дубли он находит и по шинглам и возможно еще по глобальным лексическим методам.

P.S. спасибо за конструктивную критику! Благодаря дискусии мы колективным разумом решаем поставленную задачу!

mik-a-el:
Еще как имеет. Может хешироваться часть документа и сравниваться с хешем другого документа. Сравнение хешей - потоковая операция и выполняется очень быстро.

Речь идет о подщете выборки шинглов. Шингл и есть что то вроде Хеша.

dimanaz:
Сравниваются не страницы а контрольные суммы. Сравниваются они очень быстро, имхо гораздо быстрее чем n*log(n).

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

Помойму n на корень из n. На 4ре порядка снизит затраты. Но учитывая 1000 000 операций сравнения в секунду, который я выбрал с условиями задержек в сети и всего прочего, все равно много проходит времени.

Еще Яща банит лучше когда много одинаковых текстов. Т.е. все он не сверяет однозначно. + задержки в слейки иногда 1.5 - 2 года.

Для этого нужно индексировать списочек и упорядовачивать. Может этим обьясняеться задержка в склейке.

Всего: 2639