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

To: Hkey

Не нравиться мне математика, не ваша, а вообще :) Она слишком не точно описывает жизнь... Единственное что можно точно описать математикой, так это сферического коня в вакууме.

На примерах:

Пусть мы разработали алгоритм сравнения 1 млрд страниц/сек, при этом наш бот индексирует 10 страниц в сек (усугубляет ситуацию, что мы не всё сразу индексируем) - АМБА.

Пока мы сравнивали Б1млрд с А1, А1 могло уже поменяться и стать искомым Б1млрд (сайт переехал, его что клеить с местом откуда он переехал?)!

Всё, эту тему закончили :)

Как же быть?

Кто вам сказал что сравнить нужно 1 млрд страниц?

Давайте сделаем следующее:

Руками:

+ Промаркируем как "не сравниваемые" все объёмные (имеющие много страниц) сайты, которым можно доверять и которые вообще не нужно сравнивать, т.к. контент на них гроша выеденного не стоит (новости, форумы и т.п. и сайты которые сами вздрючат если у них покомуниздят контент).

{хлоп, осталось 0,5 млрд страниц}

Автоматом при проверке:

+ Отсечём страницы которые изменялись позднее чем NN секунд от даты текущего проверяемого документа (ведь для практических целей, нет ничего ужасного в том, что кто то процитировал документ настолько старый в интернете, что его уже пол интернета процитировала).

{хлоп, осталось 1 млн страниц}

+ Ещё пара отсечений, о которых я даже помыслить боюсь :)

{хлоп, осталось 10 тыс страниц}

А вот тут уже можно работать...

To: Socionics, ХренРедькиНеСлаще и группа товарищей знающих слова "ключи" и "хеши".

Дружно идут читать Кнута.

Дружно садятся и пишут свою базу данных на асме.

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

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

За уопоминание Кнута, респект. Забывают както о нем, а вот с остальным - не соглашусь.

Чтобы проверить каждую десятую страницу и 0.5 млрд нужн 50 млн * 60 сек = 34 722.2(2) ~ 95 лет! быстрее не получится. Не всякий форум и не всякие новости мусор!

Какое время брать из LastModify или когда ее робот читал???

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

И главное, Вы забываете что сеть асинхронна, с точки зрения информации. Скорость каналов очень сильно отличается. + Обновляемость информации.

Тривиальные методы, очень бысты и хороши, но тольок тогда, когда и задача тривиальна

To: T.R.O.N

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

Конечно, некоторую часть можно просто исключить, действительно списав на мусор (NN% форумов это уж точно).

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

Заметим, всё это - солидный объём интернет страниц.

Пойдём далее.

Отсекать по времени.

Можно отсекать по времени последнего зафиксированного изменения (если документ не менялся, скажем 2 года, очевидно он устарел (устарел - в данном контексте, что не означает утрату ценности информации)).

На счёт асинхронности сети, я не просто не забываю, а обратил на это внимание, в предыдущем сообщении, в первую очередь:

"Пока мы сравнивали Б1млрд с А1, А1 могло уже поменяться и стать искомым Б1млрд (сайт переехал, его что клеить с местом откуда он переехал?)!"

На счёт задач:

Любая задача существует только в рамках практического применения, иначе и задача и поиск любого, даже самого блестящего её решения, есть пустая трата времени.

Можно предположить, что в Яндекс ставят задачи, решение которых будет способствовать конкретной цели - улучшению поиска, а не нахождению идеальной мат.модели и алгоритма выявления плагиата. Для указанной конкретной цели позволительны некоторые допущения, которые, однако, могут существенно ускорить процесс.

Частности:

- По какому времени отсекать;

- Какой временной интервал установить;

- Какие сайты считать мусором;

- Какие заведомо дубляжами;

В данном случае не важны.

Как я понимаю, цель данного топика - решение задачи имеющей конкретное практическое применение, цитирую Hkey: "Собираюсь написать такую программу <антишингл>".

Практическая сторона моего сообщения в ветке:

+ Указать на то, что не всегда обязательно работать с полным объёмом данных, всегда можно найти критерии, по которым этот объём можно снизить;

+ Указать на то, что в реальном процессе, не стоит забывать про время (сеть асинхронна, динамична и так далее).

О Кнуте. Многие вечно забывают про многое хорошее, разумное, светлое. Самое печальное, что эти многие считают, что есть некие божества "разработчики баз данных", которые по мановению волшебной палки могут ускорить в 10 раз, даже вот этот код:
jmp $-3
путём его оптимизации волшебным эликсиром или чем-то подобным :)

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

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

А вот конкретная задача по поиску дублей/нечетких дублей - какраз требует очень тонкого подбора параметров модели, чтобы придти к улучшению качества поиска, особенно в низкочастотных запросах.

Помните разницу между половинным делением и золотым сечением? Казалось бы некая мелочь, а результат порозительный.

To: T.R.O.N

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

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

Буду откровенен, меня данная проблема интересует совершенно с другой стороны, а именно: как выявлять дубли.

Я и уделил больше внимания как создать, а не тому как обойти.

Как обойти (о таком вот даже подумать страшно) - ломать не строить, уже всё сказано: добавление 1 слова ... Изменение мест слов ... И комбинации: обмен абзацами/педложениями текста с добавлением слов, наконец (метод применительно к статьям) - написание статей с разметкой определяющей порядок замен, см.: /ru/forum/67627

Мало, что бы индексировать страницу. Чуть больше чем провести поиск.

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

Каждый с каждым не сравниваеться, сравниваються новые или перелинкованые.

Некоторые материалы сравниваються более жестко нужно в этом случае нужно для сравнения двух документов 85 ть операций. Как происходит - не знаю.

Как выявить дубли. Если обьемы проверяемых данных малы. То делаеться так:

Текст разбиваеться на шинглы.

Для каждого шингла считаеться 85 контроотльных сумм по разным формулам. Вид функций подсчета контрольных сумм - неиграет роли, кроме ленейно зависимости и вырожденых случаев.

Для каждой из 85 функций находим шингл чек чумм которого будет минимальной.

Записываем 85 этих чисел.

И что бы сравнить два документа в худшем случае нужно 85 сранений.

Если одинаковых шинглов > 20 (допустим), то это плагиат.

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

Это самый жесткий алгоритм проверки ЯШИ.

SH1, SH2 .... SHn - шинглы (строки из 10 слов)

F1, F2 ...F85 функции произвольного вида

VSH1...VSH85 - выборка шинглов

VSH1 =min(F1(SH1),F1(SH2) ...F1(SHn));

VSH2 =min(F2(SH1),F2(SH2) ...F2(SHn));

.........................................................

VSH85 =min(F85(SH1),F85(SH2) ...F85(SHn));

Пусть {VSH}, i = 1, ... 85 выборка первого документа
А {VSH'} , i = 1, ... 85 выборка второго документа

Алгоритм проверки

for(i=0;i<85;i++)
{
if (VSH==VSH') ВЕРОЯТНОСТЬ_ПЛАГИАТА++;
}

if(ВЕРОЯТНОСТЬ_ПЛАГИАТА>20)
return Дубль!!!_Зеркальшик_склеить;
else уникальный_контент_не_ клеить!!;



Это алгоритм самой строгий проверки ЯШИ.

P.S. КТо т будет мне помогать опыты ставить?

Один доброволец есть для чистоты экспиремента нужно еще 4 ре. Страницы я вам предоставлю.