crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> Нужна помощь с алгоритмом..., математика и программирование!
ViGOur
  опции профиля:
сообщение 16.3.2010, 19:04
Сообщение #1


Мастер
******

Группа: Модератор
Сообщений: 3291
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Есть хеш документов:
// qint64 - номер документа, CDocument* - сам документ, использую хеш так как нужно быстро находить нужные документы.
QHash<qint64, CDocument*> m_hashDoc;
Документов может быть огромное количество.
Я умею определить, похож один документ на другой или нет:
bool isEqual( CDocument *p1, CDocument *p2);


Нужно, оптимально быстро разбить документы на категории, в каждой категории должны быть только похожие друг на друга документы.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 16.3.2010, 19:32
Сообщение #2


Профессионал
*****

Группа: Модератор
Сообщений: 1593
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


как-то неполно поставлена задача.
если, к примеру, есть индуктивность (если А похож на B и B похож на C, то из этого следует, что A похож на C) - тогда можно попытаться строить цепочки зависимостей. однако, количество групп заранее неизвестно, поэтому прогнозировать скорость разбиения трудно.
в общем случае, в худшем варианте количество групп будет равно количеству файлов. и если нет индуктивности, то есть только один метод: полный перебор, сравнение каждого с каждым. а как иначе определить похожесть?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 16.3.2010, 20:13
Сообщение #3


Мастер
******

Группа: Модератор
Сообщений: 3291
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Цитата(Iron Bug @ 16.3.2010, 19:32) *
если А похож на B и B похож на C, то из этого следует, что A похож на C
Что-то вроде этого, без перебора для составления списка похожих документов не обойтись.

Но вот как быть с разбиением на категории, после получения списка похожих документов для каждого документа?
Если есть примерно следующее:
Цитата
д1 - д3, д5, ...
д2 - д4, д7, ...
д3 - д1, д8, ...
... - ...
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 16.3.2010, 20:41
Сообщение #4


Профессионал
*****

Группа: Модератор
Сообщений: 1593
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


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

да, кстати, в boost::algorithms в BGL есть алгоритм Connected Components. но тут надо подумать, удобно ли тебе будет под него подстраиваться или быстрее "на коленке" написать.

Сообщение отредактировал Iron Bug - 16.3.2010, 20:54
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 16.3.2010, 21:05
Сообщение #5


Мастер
******

Группа: Модератор
Сообщений: 3291
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Такс, более менее картинка отрисовывается как это делать.
Проект на Qt и честно говоря не хотелось бы еще boost туда подключать, да и насколько я слышал у BGL свои заморочки, в которые нужно отдельно вникать, а мне как говориться нужно было сделать еще вчера. :)

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

Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 15.12.2019, 1:01