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

123 4
E
На сайте с 27.08.2005
Offline
15
13496

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

Я знаю о 2х алгоритмах определения дублировния - шинглы и http://company.yandex.ru/articles/article7.html (descriptive words).

С шинглами - все понятно, но вот они очень небыстрые. Что же касается метода, преложенного Sergey Ilyinsky, Maxim Kuzmin, Alexander Melkov, Ilya Segalovich, то он заявлен как более быстрый и проще в реализации. Вот только не ясно, как же все-таки выбирать эти слова.

Есть 3 правила:

1. A set of words should cover the maximal possible amount of documents

2. The "quality" of a word in the sense described below should be the highest

3. The number of words in the set should be minimal

Но, к сожалению, конкретики это не прибавляет.

В дополнение к 2м перечисленным методам, есть еще такая идея - считать контрольную сумму от слов с частотами появления в интервале 3% - 4% (пока что сказал наобум, смысл в том, чтобы учитывать слова из "середины" по частоте появления в документе)

R
На сайте с 29.04.2003
Offline
37
#1
Eugen:

В дополнение к 2м перечисленным методам, есть еще такая идея - считать контрольную сумму от слов с частотами появления в интервале 3% - 4% (пока что сказал наобум, смысл в том, чтобы учитывать слова из "середины" по частоте появления в документе)

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

E
На сайте с 27.08.2005
Offline
15
#2
Rusl:
А поподробнее можно? Идея, насколько я понял в том, что эти слова передают суть документа и при незначительных изменениях теста страницы остаются не изменными?

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

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

S
На сайте с 21.05.2006
Offline
3
#3

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

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

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

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

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

seodev:
Если пересечение есть, то можно использовать идеи Locality Sensitive Hash, см. например здесь: http://www-db.stanford.edu/~taherh/papers/scalable-clustering.pdf
только вместо одной суммы crc будет несколько, чем больше сумм, тем меньше вероятность не найти похожий документ. Найденные в результате кандидиты нужно сравнить непосредственно с помощью какой-нибудь более точной функции.

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

S
На сайте с 21.05.2006
Offline
3
#5

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

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

E
На сайте с 27.08.2005
Offline
15
#6
seodev:
Это он для компьютера перестанет быть дубликатом, а для пользователя он будет выглядеть абсолютно аутентично.

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

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

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

S
На сайте с 21.05.2006
Offline
3
#7

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

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

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

В моем случае надо отлвливать прежде всего неумышленные нечеткие дубли. Например, одна и та же страница, но поменялось время в футере, добавилась форма ввода сообщения (проанализируйте, к примеру, этот форум на предмет таких непреднамеренных дублей - будет понятно, о чем я). Кроме того, было бы здорово ограничится только одной контрольной суммой на документ ;) Или же найти другие быстрые алгоритмы.
mnt
На сайте с 11.11.2002
Offline
107
mnt
#8
Eugen:
Знаю, тема уже поднималась не раз, но все-таки хотелось бы собрать summary насчет существующих алгоритомов.
Я знаю о 2х алгоритмах определения дублировния - шинглы и http://company.yandex.ru/articles/article7.html (descriptive words).

С шинглами - все понятно, но вот они очень небыстрые. Что же касается метода, преложенного Sergey Ilyinsky, Maxim Kuzmin, Alexander Melkov, Ilya Segalovich, то он заявлен как более быстрый и проще в реализации. Вот только не ясно, как же все-таки выбирать эти слова.
Есть 3 правила:
1. A set of words should cover the maximal possible amount of documents
2. The "quality" of a word in the sense described below should be the highest
3. The number of words in the set should be minimal
Но, к сожалению, конкретики это не прибавляет.

В дополнение к 2м перечисленным методам, есть еще такая идея - считать контрольную сумму от слов с частотами появления в интервале 3% - 4% (пока что сказал наобум, смысл в том, чтобы учитывать слова из "середины" по частоте появления в документе)

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

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

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

дорого куплю ссылки с хороших жирных русскоязычных авто сайтов.
E
На сайте с 27.08.2005
Offline
15
#9
mnt:
Смотря для чего вам нужно находить дубли.
Вон яндекс вроде бы умеет с дублями работать, а вы посмотрите на его новости как он сюжеты объединяет - иногда очень забавно наблюдать ;)
т.е. для того, чтобы находить более точно нечеткие дубли с помощью не важно каких алгоритмов, нужно предварительно применять устойчивую кластеризацию.

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

Y
На сайте с 02.01.2006
Offline
138
#10

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

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

123 4

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий