Поиск:

Ответ в темуСоздание новой темы Создание опроса
> как правильно отсеять дупликаты текстов 
:(
    Опции темы
kulibinka
Дата 12.12.2006, 02:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



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

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

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

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

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

Подскажите пожалуйста алгоритм который бы исходя из этих известных характеристика корректно выдавал что именно стоит считать за дупликат (стоит убивать).
PM MAIL   Вверх
kulibinka
Дата 12.12.2006, 15:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



Ну люди, ну подскажите - работа стоит smile

Вот получил я пачки таких "слепленных" статей (насколько я помню это называется компонентами связности), но как эти компоненты потом "развязать"?
PM MAIL   Вверх
SoWa
Дата 12.12.2006, 20:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74



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


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
sergejzr
Дата 12.12.2006, 20:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



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


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
kulibinka
Дата 12.12.2006, 21:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



Цитата

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


Я и так тексты каждый с каждым проверяю. Но почему сложность "факториал", если для n текстов нужно (n*n + n)/2 операций сравнения?
PM MAIL   Вверх
kulibinka
Дата 12.12.2006, 21:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



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

Цитата

-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

Как вам кажется, нормальный алгоритм или есть в нем дыры?
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1183 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.