![]() |
|
![]() ![]() ![]() |
|
kulibinka |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 191 Регистрация: 20.11.2006 Репутация: 2 Всего: 4 |
В процессе решения задачи "Как определить схожесть текстов" http://forum.vingrad.ru/topic-121705.html я подсчитывал для двух любых документов А и В характеристики вида насколько документ А похож на В и насколько В похож на А (это размер одинаковой части документа/размер всего документа).
Например, на рис.1 ![]() документ А похож на документ В на 30%, док. В на док. A на 77%. После этого я брал максимальное значение и если оно было больше некоторого порога (я брал 50% - значит один из текстов лежит в другом больше чем на 50% ) я убивал тот, у которого процент похожести больше (в этом случае док. В). В конце после прогона между всеми двойками документов из всей базы текстов я получал номера документов-дубликатов и убирал их из базы. Но в результате алгоритм получился немножко дырявый - например, он для варианта на рис.2. ![]() оставлял только документ А (А и В - убиваем В, В и С - убиваем С, А и С - ничего не убиваем, в результате алгоритм говорит "в конце убей В и С"), хотя должен был оставить документы А и С (действительно, ведь А и С между собой вообще абсолютно уникальные). Подскажите пожалуйста алгоритм который бы исходя из этих известных характеристика корректно выдавал что именно стоит считать за дупликат (стоит убивать). |
|||
|
||||
kulibinka |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 191 Регистрация: 20.11.2006 Репутация: 2 Всего: 4 |
Ну люди, ну подскажите - работа стоит
![]() Вот получил я пачки таких "слепленных" статей (насколько я помню это называется компонентами связности), но как эти компоненты потом "развязать"? |
|||
|
||||
SoWa |
|
|||
![]() Харекришна ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Если твой алгоритм не работает с примером 2, то значит прокол в нем.
Понятно, что проверяет он у тебя такие связи A--B B--C Но при этом не проверяет A--C Делай выводы. Проверяй каждый с каждым тексты на "пересечение". Сложность правда "факториал" выйдет, но что поделать... -------------------- Всем добра ![]() |
|||
|
||||
sergejzr |
|
|||
![]() Un salsero ![]() Профиль Группа: Админ Сообщений: 13285 Регистрация: 10.2.2004 Где: Германия г .Ганновер Репутация: 4 Всего: 360 |
Рано убиваешь доки. Строй таблицу, потом упрощай. (Упрощение почти всегда факториал). Но большинство доков сможешь выкинуть на первом этапе. (Те, которые пересекаются только друг с другом.) И учитывать только сложные пересечения.
|
|||
|
||||
kulibinka |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 191 Регистрация: 20.11.2006 Репутация: 2 Всего: 4 |
Я и так тексты каждый с каждым проверяю. Но почему сложность "факториал", если для n текстов нужно (n*n + n)/2 операций сравнения? |
|||
|
||||
kulibinka |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 191 Регистрация: 20.11.2006 Репутация: 2 Всего: 4 |
Вот приблизительный алгоритм, которым я собираюсь разбирать эти слипшиеся документы:
Как минимум ситуацию на рис.2 он разруливает... да и другие те которые я умственно смог сгенерировать вроде бы разруливает ![]() Как вам кажется, нормальный алгоритм или есть в нем дыры? |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |