1 (29.08.2012 14:08:51 отредактировано marikk)

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

[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. Используя рекурсию(боюсь я раньше состарюсь чем ее сделаю) комплектовать ассоциативный массив конечных обьектов дальше все просто...
Какой из этих подходов более безболезненный или же есть другой выход ? Оба этих метода имеют огромные затраты оперативной памяти, при их реализации столкнусь с огромным количеством проблем.

2

marikk пишет:

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

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

marikk пишет:

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

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

Карусель разнесло по цепочке за час
Всех известий — конец
Да, весна началась!
(всё к лицу подлецу, как родному отцу, не рассказывай, батя, и так всё пройдёт)

3

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

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

4

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

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

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

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

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

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

5

voral пишет:

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

как я понял:

marikk пишет:

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

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

Карусель разнесло по цепочке за час
Всех известий — конец
Да, весна началась!
(всё к лицу подлецу, как родному отцу, не рассказывай, батя, и так всё пройдёт)

6 (29.08.2012 15:20:03 отредактировано marikk)

voral пишет:

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

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

/Root 8 0 obj


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

/Parent ****

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

/Type /Pages

Конечный

/Type /Page

7

drBatty пишет:
voral пишет:

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

как я понял:

marikk пишет:

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

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

Все правильно

8

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

marikk пишет:

Конечный

/Type /Page

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

Да, у меня Ubuntu.
Нет, не глючит.

9

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

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

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

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

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

10

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

95% процентов проблем находятся между клавиатурой и стулом.

11

Fat-Zer пишет:

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

Вроде, необходимо вычислять подозрительные объекты в Матрице... http://linuxforum.ru/extensions/bbcode_smiles/img/ag.gif

Да, у меня Ubuntu.
Нет, не глючит.

12

marikk пишет:

 

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

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

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

voral пишет:

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

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

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

Карусель разнесло по цепочке за час
Всех известий — конец
Да, весна началась!
(всё к лицу подлецу, как родному отцу, не рассказывай, батя, и так всё пройдёт)

13 (30.08.2012 00:08:30 отредактировано voral)

drBatty пишет:

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

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

drBatty пишет:

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

marikk пишет:

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


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

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

14

-=Serj=- пишет:

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

marikk пишет:

Конечный

/Type /Page

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

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

15

voral пишет:

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

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

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

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

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

16 (30.08.2012 09:00:34 отредактировано voral)

marikk пишет:

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

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

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

17

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

18 (30.08.2012 09:05:43 отредактировано marikk)

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

19

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

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

?

Да, у меня Ubuntu.
Нет, не глючит.

20

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

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

21

#!/usr/bin/env python
#_*_coding: utf-8_*_
import sys, re
def Find(patt, text):
    match = re.findall(patt, text)
    if match:
        for block in match:
            if '/Type /Page\n' in block:
                print (block + '-----------------')
    else : print ('Не найдено...')

f = open(sys.argv[1], 'r')
data = f.read()
patt = re.compile(r'\sobj([\s\S]+?)endobj') 

Find(patt, data)

 Консоль:
$ ./pdfparser.py test.pdf

+ открыть спойлер

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 16 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 19 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Annots 24 0 R
  /Contents 26 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 29 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 32 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 35 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Annots 40 0 R
  /Contents 42 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 45 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 48 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Annots 53 0 R
  /Contents 54 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 57 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 60 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 63 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 66 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 69 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 72 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 75 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 78 0 R
>>

-----------------

<<
  /Resources 3 0 R
  /Type /Page
  /MediaBox [0 0 595.275 841.889]
  /CropBox [0 0 595.275 841.889]
  /BleedBox [0 0 595.275 841.889]
  /TrimBox [0 0 595.275 841.889]
  /Parent 1 0 R
  /Contents 81 0 R
>>

-----------------

Оно ?

Да, у меня Ubuntu.
Нет, не глючит.

22

Оно ?

так то оно да. Большое спасибо за старания.
В большинстве случаев такой парсинг будет уместен (если добавить пару условий), на первое время он будет взят за основу.
Но проблему непоследовательности страниц таким подходом не побороть. Наглядный пример:

1531 0 obj
<</Count 86/Type/Pages/Kids[1532 0 R 1533 0 R 1534 0 R 1535 0 R 1536 0 R 1537 0 R 1538 0 R 1539 0 R 1540 0 R]>>
endobj
1532 0 obj
<</Parent 1531 0 R/Count 10/Type/Pages/Kids[1545 0 R 1 0 R 3 0 R 11 0 R 13 0 R 190 0 R 339 0 R 510 0 R 597 0 R 602 0 R]>>
endobj
1533 0 obj
<</Parent 1531 0 R/Count 10/Type/Pages/Kids[604 0 R 616 0 R 623 0 R 629 0 R 665 0 R 678 0 R 689 0 R 702 0 R 710 0 R 723 0 R]>>
endobj

1532 0 obj -- 1 страница
604 0 obj -- 21 страница.
Такое будет встречаться редко, но все равно хотелось бы иметь возможность работать со всем, а иначе теряется смысл "проекта".

23

marikk пишет:

Но проблему непоследовательности страниц таким подходом не побороть.

Брр.. Опять не понял... Я в этих PDFах не бум-бум. Попробуйте более широко описать задачу.

Да, у меня Ubuntu.
Нет, не глючит.

24

-=Serj=- пишет:
marikk пишет:

Но проблему непоследовательности страниц таким подходом не побороть.

Брр.. Опять не понял... Я в этих PDFах не бум-бум. Попробуйте более широко описать задачу.

Все вы правильно сделали. Ошибся немного с переводом документации. Спасибо