| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > как правильно отсеять дупликаты текстов |
| Автор: kulibinka 12.12.2006, 02:09 |
| В процессе решения задачи "Как определить схожесть текстов" http://forum.vingrad.ru/topic-121705.html я подсчитывал для двух любых документов А и В характеристики вида насколько документ А похож на В и насколько В похож на А (это размер одинаковой части документа/размер всего документа). Например, на рис.1 ![]() документ А похож на документ В на 30%, док. В на док. A на 77%. После этого я брал максимальное значение и если оно было больше некоторого порога (я брал 50% - значит один из текстов лежит в другом больше чем на 50% ) я убивал тот, у которого процент похожести больше (в этом случае док. В). В конце после прогона между всеми двойками документов из всей базы текстов я получал номера документов-дубликатов и убирал их из базы. Но в результате алгоритм получился немножко дырявый - например, он для варианта на рис.2. ![]() оставлял только документ А (А и В - убиваем В, В и С - убиваем С, А и С - ничего не убиваем, в результате алгоритм говорит "в конце убей В и С"), хотя должен был оставить документы А и С (действительно, ведь А и С между собой вообще абсолютно уникальные). Подскажите пожалуйста алгоритм который бы исходя из этих известных характеристика корректно выдавал что именно стоит считать за дупликат (стоит убивать). |
| Автор: kulibinka 12.12.2006, 15:24 |
| Ну люди, ну подскажите - работа стоит Вот получил я пачки таких "слепленных" статей (насколько я помню это называется компонентами связности), но как эти компоненты потом "развязать"? |
| Автор: 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 | ||
Вот приблизительный алгоритм, которым я собираюсь разбирать эти слипшиеся документы:
Как минимум ситуацию на рис.2 он разруливает... да и другие те которые я умственно смог сгенерировать вроде бы разруливает Как вам кажется, нормальный алгоритм или есть в нем дыры? |