Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > как правильно отсеять дупликаты текстов


Автор: kulibinka 12.12.2006, 02:09
В процессе решения задачи "Как определить схожесть текстов" http://forum.vingrad.ru/topic-121705.html я подсчитывал для двух любых документов А и В характеристики вида насколько документ А похож на В и насколько В похож на А  (это размер одинаковой части документа/размер всего документа). 

Например, на рис.1 
user posted image
документ А похож на документ В на 30%, док. В на док. A на 77%. После этого я брал максимальное значение и если оно было больше некоторого порога (я брал 50% - значит один из текстов лежит в другом больше чем на 50% ) я убивал тот, у которого процент похожести больше (в этом случае док. В).

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

Но в результате алгоритм получился немножко дырявый - например, он для варианта на рис.2. 
user posted image

оставлял только документ А (А и В - убиваем В, В и С - убиваем С, А и С - ничего не убиваем, в результате алгоритм говорит "в конце убей В и С"), хотя должен был оставить документы А и С (действительно, ведь А и С между собой вообще абсолютно уникальные). 

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

Автор: kulibinka 12.12.2006, 15:24
Ну люди, ну подскажите - работа стоит smile

Вот получил я пачки таких "слепленных" статей (насколько я помню это называется компонентами связности), но как эти компоненты потом "развязать"?

Автор: SoWa 12.12.2006, 20:22
Если твой алгоритм не работает с примером 2, то значит прокол в нем.
Понятно, что проверяет он у тебя такие связи
A--B
B--C
Но при этом не проверяет A--C
Делай выводы.
Проверяй каждый с каждым тексты на "пересечение". Сложность правда "факториал" выйдет, но что поделать...

Автор: sergejzr 12.12.2006, 20:30
Рано убиваешь доки. Строй таблицу, потом упрощай. (Упрощение почти всегда факториал). Но большинство доков сможешь выкинуть на первом этапе. (Те, которые пересекаются только друг с другом.) И учитывать только сложные пересечения.

Автор: kulibinka 12.12.2006, 21:08
Цитата

Проверяй каждый с каждым тексты на "пересечение". Сложность правда "факториал" выйдет, но что поделать... 


Я и так тексты каждый с каждым проверяю. Но почему сложность "факториал", если для n текстов нужно (n*n + n)/2 операций сравнения?

Автор: kulibinka 12.12.2006, 21:33
Вот приблизительный алгоритм, которым я собираюсь разбирать эти слипшиеся документы:

Цитата

-1. получаем слипшиеся статьи и порог выбрасывания

0. для всех двоек i, j из статей подсчитываем схожесть v_i, v_j, min(v_i, v_j), max(v_i, v_j) (где v_j - то насколько статья j похожа (лежит) на статью i)

1. выбираем пару где min(v_i, v_j) самое меньшее среди всех значений (т.е. именно в этой паре есть самая "уникальная" статья из всей слипшейся пачки)

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

3. выбрасываем те статьи, у которых max схожести с той статьей, которая попала в результат, больше порога

4. возвращаемся на шаг -1. со всеми статьями, которые не попали в результат или не были выброшены


Как минимум ситуацию на рис.2 он разруливает... да и другие те которые я умственно смог сгенерировать вроде бы разруливает smile

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)