Алгоритмы определения нечетких дубликатов

А поподробнее можно? Идея, насколько я понял в том, что эти слова передают суть документа и при незначительных изменениях теста страницы остаются не изменными?

Да, мы берем качественный состав (т.е., например, считаем контрольную сумму от строки из конкатенированных, отсортированных в определенном порядке - например, по алфавиту - слов из среднечастотников) среднечастотников. К сожалению - это не более чем идея. Интересно, какая получится у нее статистика в плане ошибок 1го и 2го рода. Но метод длжен быть очень удобным, т.к. имеем всего 1 контрольную сумму для документа и считать ее быстро.

А насчет метода от комманды Яндекса, кто-то может прокомментировать, как выбирать эти "характеристические" слова? :)

А есть уверенность, что у похожих страниц в вашем случае наблюдается действительно пересечение по общим словам? В случае спама это может быть и неверно: спамер может специально коверкать слова или заменять некоторые русские буквы латинскими эквивалентами.

Если пересечение есть, то можно использовать идеи Locality Sensitive Hash, см. например здесь: http://www-db.stanford.edu/~taherh/papers/scalable-clustering.pdf

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

Замена букв в слове равносильна замене самомго слова, а если заменить все слова - то такой документ дубликатом являться не будет наверняка ;) Кстати, факт замены букв в слове и алгоритм шинглов будет рассматривать как факт замены слова, а значит - как разницу м/д документами.

Хм... Но сравнивать еще раз с помощью более точной функции - точно очень накладно. Более точная - это расстояние Левенштейна?

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

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

Все же не соглашусь, во 1ых, алгоритм сслылочной кластеризации, Locality Sensitive Hash, то это все-равно будет анализ на уровне слов, а во 2ых, вы сами же предложили пословного левенштейна ;)

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

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

Еще очень полезно такое наблюдение: если пользователь ищет, то он считает дублями те странички, по которым выдаются одинаковые сниппеты (включая заголовок). Конечно, заранее невозможно предсказать, по каким словам будет искать, но можно заменить все цифры на 0, все последовательности небуквенных и нецифровых символов одним пробелом. И откусить от начала некоторый небольшой кусочек, байт тысячу. Присоединить таким же образом отшлифованный тайтл. Посчитать crc. С очень высокой полнотой можно будет отлавливать дубликаты. Ну а точность зависит от конкретики. Для интернета в целом, ИМХО, будет не самая плохая, но если в базе много страниц имеют общее начало, то будет не слишком хорошо.

Смотря для чего вам нужно находить дубли.

Вон яндекс вроде бы умеет с дублями работать, а вы посмотрите на его новости как он сюжеты объединяет - иногда очень забавно наблюдать ;)

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

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

Я сегодня по подобному поводу весь день в блоге бредил:

http://users.livejournal.com/_yukko_/221124.html (предупреждаю, там нет никакой математики, там мысли)