Нужна помощь с алгоритмом..., математика и программирование! Опции

[ViGOur]

Есть хеш документов:

// qint64 - номер документа, CDocument* - сам документ, использую хеш так как нужно быстро находить нужные документы.
QHash<qint64, CDocument*> m_hashDoc;

Документов может быть огромное количество.
Я умею определить, похож один документ на другой или нет:

bool isEqual( CDocument *p1, CDocument *p2);

Нужно, оптимально быстро разбить документы на категории, в каждой категории должны быть только похожие друг на друга документы.

[Iron Bug]

как-то неполно поставлена задача.
если, к примеру, есть индуктивность (если А похож на B и B похож на C, то из этого следует, что A похож на C) - тогда можно попытаться строить цепочки зависимостей. однако, количество групп заранее неизвестно, поэтому прогнозировать скорость разбиения трудно.
в общем случае, в худшем варианте количество групп будет равно количеству файлов. и если нет индуктивности, то есть только один метод: полный перебор, сравнение каждого с каждым. а как иначе определить похожесть?

[ViGOur]

если А похож на B и B похож на C, то из этого следует, что A похож на C

Что-то вроде этого, без перебора для составления списка похожих документов не обойтись.

Но вот как быть с разбиением на категории, после получения списка похожих документов для каждого документа?
Если есть примерно следующее:

д1 - д3, д5, ...
д2 - д4, д7, ...
д3 - д1, д8, ...
... - ...

[Iron Bug]

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

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

Сообщение отредактировал Iron Bug - 16.3.2010, 20:54

[ViGOur]

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

Так что подумаю как реализовать мини графы для моих нужд...