Направьте на правильный путь

Помогите пожалуйста с алгоритмом.
Имеется файл состоящий из отдельных блоков. Пример блоков:

[b]1 0 obj[/b]
...............
endobj
[b]2 0 obj[/b]
.................
endobj
[b]3 0 obj[/b]
................
endobj

Все эти блоки находятся в зависимости по типу древовидной структуры - есть рутовый обьект, который обязательно содержит потомков, эти потомки могут также содержать потомков(до бесконечности) или же быть конечными обьектами. Необходимо вычислить конечные обьекты. Для того, чтобы не гонять файл туда сюда, при входе в программу он считывается в ассоциативный массив(размер массива зависит от того какой файл будет загружен, чаще всего не более 3-4мб).
Пример зависимости:

4 o obj
/kids [1 0 obj.....]
endobj
1 0 obj
/kids [4 0 obj, 5 0 obj .....]
endobj
4 0 obj
---конечный--
endobj
5 0 obj
--конечный
endobj

Вижу два выхода;
1. Попытаться это загнать в Qt древовидную модель QTreeModel, далее забрать необходимые элементы ну и тд...
2. Используя рекурсию(боюсь я раньше состарюсь чем ее сделаю) комплектовать ассоциативный массив конечных обьектов дальше все просто...
Какой из этих подходов более безболезненный или же есть другой выход ? Оба этих метода имеют огромные затраты оперативной памяти, при их реализации столкнусь с огромным количеством проблем.

"marikk" написал:

Какой из этих подходов более безболезненный или же есть другой выход ?

ну если пугает расход памяти - ищите один объект за один проход. Если не пугает - ищите все объекты за один проход (ага. Какой-нить древовидной структурой. Какой хотите. Полезно покурить предварительно Кнута). Если пугает но не сильно - ищите X потомков за один проход (например запоминайте во время прохода только не более 10и корневых узлов и всех их потомков).

"marikk" написал:

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

ктож знает, сколько у вас деревьев в вашем лесу, и насколько они ветвистые?

Может я объяснения не понял, но:
А как в этом исходном файле отражается иерархия блоков?

Искать необходимые конечные обьекты по сложности равносильно, так как обьекты не имеют своего порядкового номера также неизвестно количество обьектов в ветке(придется лопатить всю структуру).

Огромный расход памяти будет только при поиске, так как в каждый узел необходимо будет передать весь массив обьектов(можно попробовать ссылками), для дальнейшего скачка. Конечные обьекты планирую хранить в массиве типа [int] [int], первый integer это порядковый номер, второй это адрес элемента в массиве и инициализировать их по необходимости.

ктож знает, сколько у вас деревьев в вашем лесу, и насколько они ветвистые?

Если файл собран правильно, ветвлений не будет вообще(сразу получу массив конечных обьектов), в крайнем случае будет одно ветвление. Если файл собран криво, то количество ветвлений будет зависеть от больной фантазии разработчика, а также от пользователей, которые будут подгружать все файлы подряд(ради приколу).

Полезно покурить предварительно Кнута

Можно об этом поподробней ?

"voral" написал:

А как в этом исходном файле отражается иерархия блоков?

как я понял:

"marikk" написал:

1 0 obj
/kids [4 0 obj, 5 0 obj .....]

этот (1 0) блок является родителем 4 0 и 5 0

voral написал:

Может я объяснения не понял, но:
А как в этом исходном файле отражается иерархия блоков?

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

/Root 8 0 obj

Который указывает на точку входа в структуру. Рутовый обьект содержит ссылку на первое ветвление, соответственно каждый следующий после рута обьект имеет параметр

/Parent ****

с указателем на родительский обьект. Обьект с ветвлением содержит параметр

/Type /Pages

Конечный

/Type /Page

drBatty написал:

[quote="voral"]А как в этом исходном файле отражается иерархия блоков?

как я понял:

"marikk" написал:

1 0 obj
/kids [4 0 obj, 5 0 obj .....]

этот (1 0) блок является родителем 4 0 и 5 0[/quote]
Все правильно

А можно пример файла?

"marikk" написал:

Конечный

text

/Type /Page

Т.е. конечный объект однозначно определяется?

Ну т.е. глядя на блок мы можем точно сказать имеет он детей или нет. Если не имеет - то он конечный, если имеет - нет..... Соответственно если пробежать по всем блокам и анализировать конечный он или нет.
Критерий наличие детей Да/Нет (если такой параметр есть в описании блока)

Если параметра нет. А есть указатель на родителя. То бежим по файлу записываем в массив блоки (или их смещения в файле). Как только встречаем блок имеющий указатель на родителя. Выкидываем этого родителя из нашего массива.

И в том и в другом случае один проход.

Или я туплю в понимании задачи?
С PDF сам не работал, только бегло взглянул..... Но вроде как-то так

я рад за вас, товарищи телепаты =), но поясните для простых смертных, задача то в чём? мне. так... из спортивного интереса узнать...

Fat-Zer написал:

я рад за вас, товарищи телепаты =), но поясните для простых смертных, задача то в чём? мне. так... из спортивного интереса узнать...

Вроде, необходимо вычислять подозрительные объекты в Матрице...

"marikk" написал:

Полезно покурить предварительно Кнута

Можно об этом поподробней ?

Искусство Программирования
Том 1
2.3 Деревья. Страница 352 русского издания.

"voral" написал:

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

угу. См. выше, расход памяти и прочее (время и т.д.) уже подробно рассмотрено боле 50и лет назад. Всё уже украдено до нас.

marikk
1. если это какая-то VCS - используйте например ртуть, и не * голову себе, нам, и вашим коллегам.
2. если это не VCS, но СУБД, используйте например MySQL, SQLite и не * голову себе, нам, и вашим коллегам. (вы выше рассмотрели классический случай реляционной БД, отношение "один ко многим", если я правильно понял)
3. Если это не п1 и не п2, то конкретизируйте задачу, расскажите, почему это не п1 и п2.

drBatty написал:

угу. См. выше, расход памяти и прочее (время и т.д.) уже подробно рассмотрено боле 50и лет назад. Всё уже украдено до нас.

PDF вроде как ТС сказал.
Список нужен конечных элементов. В зависимости от задачи можно хранить смещения в файле. Я глянул пару pdfин нету там инфы о детях - только о родителях.... (хотя может pdf был "не тот" - надо доку читать) А если так, то полного обхода файла не избежать.

drBatty написал:

3. Если это не п1 и не п2, то конкретизируйте задачу, расскажите, почему это не п1 и п2.

marikk написал:

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

Но вообще да.... Задачу бы поподробнее узнать.....

-=Serj=- написал:

А можно пример файла?
[quote="marikk"]Конечный

text

/Type /Page

Т.е. конечный объект однозначно определяется?[/quote]

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

voral написал:

Ну т.е. глядя на блок мы можем точно сказать имеет он детей или нет. Если не имеет - то он конечный, если имеет - нет..... Соответственно если пробежать по всем блокам и анализировать конечный он или нет.
Критерий наличие детей Да/Нет (если такой параметр есть в описании блока)

Если параметра нет. А есть указатель на родителя. То бежим по файлу записываем в массив блоки (или их смещения в файле). Как только встречаем блок имеющий указатель на родителя. Выкидываем этого родителя из нашего массива.

И в том и в другом случае один проход.

Или я туплю в понимании задачи?
С PDF сам не работал, только бегло взглянул..... Но вроде как-то так

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

"marikk" написал:

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

1. Ну так проблема или нет :)
2. Я так понимаю информация об их видимости так же присутствует. Если это может идти от родителя - придется хранить массив скрытых блоков. (А точнее, полагаю, массив идентификаторов таких блоков). И если родитель очередного блока присутствует в этом списке, то и этот блок записываем в "черный" список.

Кажись додумал. Крутить массив обьектов. Входя в обьект проверять, конечный он или нет? Далее по ссылкам на родителя определить принадлежность к структуре.

Всем спасибо. Буду пробовать, хотя это и неправильный подход, но рабочий(для начала пойдет).

Как я понял, необходимый блок выглядит так:

  obj
.......
/Type /Page
.......
endobj

?

  obj
.......
/Parent X X obj
/Type /Page
.......
endobj

если точнее так