Το συνοδευτικό μας άρθρο για την σειρά σελίδων PDF καλύπτει τον βασικό κανόνα: η σειρά εμφάνισης προκύπτει από μια διάσχιση κατά βάθος, από αριστερά προς τα δεξιά, των πινάκων /Kids στο δέντρο /Pages, ποτέ από τους αριθμούς αντικειμένων. Αυτό το άρθρο εξετάζει το δέντρο από διαφορετική οπτική γωνία — το σχήμα του. Γιατί οι ώριμοι συγγραφείς PDF παράγουν ιεραρχίες ενδιάμεσων κόμβων όταν ένας απλός επίπεδος πίνακας θα ήταν απόλυτα έγκυρος; Τι αλλάζει πραγματικά όταν ένα εργαλείο ισοπεδώνει ή ανασυγκροτεί το δέντρο; Και τι συμβαίνει όταν η λογιστική καταχώριση /Count, που κάνει ολόκληρη τη δομή γρήγορη, σταματά να λέει την αλήθεια
Το fan-out είναι απόφαση απόδοσης
Τίποτα δεν αναγκάζει έναν συγγραφέα να δημιουργήσει ένθετη δομή. Ένα έγγραφο 10.000 σελίδων με έναν ριζικό κόμβο /Pages και 10.000 αναφορές φύλλων σε έναν μόνο πίνακα /Kids συμμορφώνεται πλήρως με την προδιαγραφή. Το PDF Reference ωστόσο συνιστά ένα ισορροπημένο δέντρο για μεγάλα έγγραφα, και οι κύριοι generators ακολουθούν αυτή τη συμβουλή με μέτριο fan-out, συνήθως λίγες δεκάδες παιδιά ανά ενδιάμεσο κόμβο
Ο λόγος είναι τι πρέπει να διαβάσει ένα πρόγραμμα προβολής προτού μπορέσει να εμφανίσει οτιδήποτε. Σκεφτείτε ένα άλμα κατευθείαν στη σελίδα 8.214 αυτού του αρχείου 10.000 σελίδων. Με ένα επίπεδο δέντρο, το πρόγραμμα προβολής πρέπει πρώτα να αναλύσει τον ριζικό κόμβο, και αυτός ο ριζικός κόμβος είναι ένας τεράστιος πίνακας: με περίπου οκτώ bytes ανά έμμεση αναφορά, ένα αντικείμενο 80 KB που πρέπει να αναλυθεί (tokenized) από άκρη σε άκρη πριν επιλυθεί η καταχώριση 8.213. Με ένα ισορροπημένο δέντρο fan-out 32, το ίδιο άλμα διαβάζει τη ρίζα, συγκρίνει τα τρέχοντα αθροίσματα /Count για να επιλέξει το σωστό παιδί, και κατεβαίνει — τρία ή τέσσερα μικρά λεξικά συνολικά, το καθένα λίγες εκατοντάδες bytes. Αυτή είναι η τυχαία πρόσβαση O(log n) που το δέντρο σχεδιάστηκε να παρέχει, και είναι ολόκληρος ο λόγος που το /Count υπάρχει σε ενδιάμεσους κόμβους: επιτρέπει σε έναν αναγνώστη να παραλείψει ολόκληρο ένα υποδέντρο χωρίς να ανοίξει ούτε ένα αντικείμενο μέσα του
Το σχήμα του δέντρου καθορίζει επίσης το κόστος επεξεργασίας. Ένας incremental update που εισάγει μία σελίδα πρέπει να ξαναγράψει κάθε κόμβο του οποίου το /Kids ή το /Count άλλαξε, δηλαδή τη διαδρομή από τον γονέα του νέου φύλλου έως τη ρίζα. Σε ένα ισορροπημένο δέντρο αυτή η διαδρομή είναι λίγα μικρά λεξικά που προσαρτώνται στο αρχείο. Σε ένα επίπεδο δέντρο η «διαδρομή» είναι ο ενιαίος τεράστιος ριζικός πίνακας, που διπλασιάζεται πλήρως σε κάθε αναθεώρηση. Ένα συμβόλαιο που περνά από τριάντα κύκλους αναθεώρησης και σχολιασμού μπορεί να καταλήξει να κουβαλά τριάντα ξεπερασμένα αντίγραφα του ίδιου πίνακα 80 KB μέσα στη ροή byte του
Οι εσωτερικοί κόμβοι μεταφέρουν κληρονομημένα χαρακτηριστικά
Οι ενδιάμεσοι κόμβοι δεν είναι απλώς δρομολόγηση. Τα τέσσερα κληρονομήσιμα χαρακτηριστικά σελίδας — /Resources, /MediaBox, /CropBox και /Rotate — μπορούν να τοποθετηθούν σε οποιονδήποτε κόμβο /Pages, όπου εφαρμόζονται σε κάθε φύλλο από κάτω του εκτός αν κάποιος απόγονος τα παρακάμψει. Ένας συγγραφέας που παράγει μια αναφορά με ένα παράρτημα σε landscape μπορεί να εκφράσει αυτή τη διάταξη μέσα στο ίδιο το δέντρο:
5 0 obj % ριζικός κόμβος εγγράφου
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % σώμα αναφοράς: portrait A4, γραμματοσειρά κειμένου
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [30 0 R 31 0 R 32 0 R]
/MediaBox [0 0 595 842]
/Resources << /Font << /F1 8 0 R >> >> >>
endobj
7 0 obj % παράρτημα: landscape A4, περιστραμμένο, δική του γραμματοσειρά
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [40 0 R 41 0 R 42 0 R]
/MediaBox [0 0 842 595] /Rotate 90
/Resources << /Font << /F2 9 0 R >> >> >>
endobj
40 0 obj % σελίδα παραρτήματος: κληρονομεί μέγεθος, περιστροφή, γραμματοσειρές
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjΤα αντικείμενα 40 έως 42 είναι σχεδόν κενά. Το μέγεθος σελίδας, η περιστροφή και οι πόροι γραμματοσειράς τους προέρχονται όλα από κληρονομικότητα από τον κόμβο 7, κάτι που κρατά το αρχείο συμπαγές και αυτοσυντηρούμενο: προσθέστε μια τέταρτη σελίδα κάτω από τον κόμβο του παραρτήματος και θα βγει αυτόματα σε landscape
Ο ίδιος μηχανισμός δημιουργεί τον κλασικό κίνδυνο μετακίνησης σελίδας. Υποθέστε ότι ένα εργαλείο μετακινεί το αντικείμενο 40 στο σώμα της αναφοράς επεξεργαζόμενο τους δύο πίνακες /Kids και αλλάζοντας το /Parent ώστε να δείχνει στον κόμβο 6. Η μετακίνηση είναι δομικά έγκυρη, όμως το αντικείμενο 40 τώρα κληρονομεί το portrait /MediaBox, καμία περιστροφή, και τη γραμματοσειρά /F1 — ενώ η ροή περιεχομένου του εξακολουθεί να επιλέγει το /F2, το οποίο δεν επιλύεται πια. Η σελίδα συρρικνώνεται, χάνει την περιστροφή της και χάνει το κείμενό της σε μία μόνο επεξεργασία. Ο ανθεκτικός κώδικας αναδιάταξης επομένως ενσωματώνει τις επιλυμένες τιμές και των τεσσάρων κληρονομήσιμων χαρακτηριστικών στο λεξικό της σελίδας πριν την επανασυνδέσει σε νέο γονέα. Αν έχετε ποτέ σύρει μια σελίδα σε έναν επεξεργαστή και την έχετε δει να αλλάζει μέγεθος ή προσανατολισμό, αυτός είναι ο μηχανισμός που είδατε
Ισοπέδωση: νόμιμη, συνηθισμένη, μερικές φορές δαπανηρή
Αρκετά εργαλεία ακολουθούν την αντίθετη κατεύθυνση. Οι ελάχιστοι συγγραφείς παράγουν ένα δέντρο ενός επιπέδου επειδή είναι απλό, και πολλά βοηθητικά προγράμματα συγχώνευσης και διαχωρισμού ανασυγκροτούν όποιο δέντρο διαβάζουν σε έναν ενιαίο επίπεδο πίνακα /Kids, επειδή η παραγωγή ισορροπημένης δομής είναι επιπλέον δουλειά και η επίπεδη έξοδος είναι πάντα συμμορφούμενη. Μια σωστή ανασυγκρότηση πρέπει να επιλύσει την κληρονομικότητα ταυτόχρονα: κάθε χαρακτηριστικό που ένα φύλλο κληρονομούσε πρέπει να αντιγραφεί πάνω στο φύλλο, ή να μεταφερθεί στη νέα ρίζα αν είναι ομοιόμορφο σε όλο το έγγραφο — διαφορετικά η έξοδος αλλάζει τη γεωμετρία ακριβώς όπως στην περίπτωση της μετακίνησης σελίδας
Για τυπικά έγγραφα η ισοπέδωση είναι αβλαβής. Πονάει σε μεγάλη κλίμακα, με τους δύο τρόπους που ήδη περιγράφηκαν: ο ριζικός πίνακας γίνεται ένα μεγάλο αντικείμενο που κάθε άνοιγμα και κάθε άλμα σελίδας πρέπει να αναλύσει πλήρως, και κάθε δομική επεξεργασία το ξαναγράφει ολόκληρο. Αυτό που η ισοπέδωση δεν καταστρέφει είναι ο διαμοιρασμός μέσω έμμεσων αναφορών — ένα επίπεδο δέντρο στο οποίο όλες οι 10.000 σελίδες δείχνουν στο ίδιο αντικείμενο λεξικού /Resources παραμένει χωρίς επανάληψη δεδομένων (deduplicated). Αυτό που χάνεται είναι μόνο η δυνατότητα να αφήσει κανείς την καταχώριση εκτός της σελίδας και να αφήσει έναν πρόγονο να την παρέχει
Όταν το /Count λέει ψέματα
Το /Count είναι καθαρή λογιστική: πρέπει να ισούται με τον αριθμό των σελίδων-φύλλων στο υποδέντρο του κόμβου, και τίποτα στη μορφή του αρχείου δεν το επιβάλλει. Δύο μοτίβα αλλοίωσης ευθύνονται για τις περισσότερες ψευδείς τιμές που εντοπίζονται στην πράξη
Το πρώτο είναι η μη ενημερωμένη τιμή που αφήνει πίσω της ένα incremental update. Ένας επεξεργαστής εισάγει μια σελίδα, ξαναγράφει τον άμεσο γονέα με νέο /Kids και ενημερωμένο /Count, προσαρτά και τα δύο στο αρχείο — και δεν αγγίζει ποτέ τους προγόνους:
% Αρχική αναθεώρηση
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R 14 0 R 15 0 R] >>
endobj
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
/Kids [50 0 R 51 0 R 52 0 R] >>
endobj
% Προσαρτημένη αναθεώρηση: μία σελίδα εισήχθη στον μεσαίο κλάδο.
% Το αντικείμενο 14 αντικαθίσταται· το αντικείμενο 12 δεν ξαναγράφεται ποτέ
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjΤο δέντρο τώρα περιέχει δέκα φύλλα, αλλά η ρίζα εξακολουθεί να λέει εννέα. Ένα πρόγραμμα προβολής που εμπιστεύεται τη ρίζα αναφέρει εννέα σελίδες στον μετρητή σελίδων του. Ένα που χρησιμοποιεί τις εσωτερικές μετρήσεις για δυαδική αναζήτηση σε ένα άλμα σελίδας υπολογίζει λάθος δείκτη για κάθε σελίδα μετά το σημείο εισαγωγής. Μια πλήρης διάσχιση βρίσκει δέκα. Τρεις διαφορετικές απαντήσεις, ένα αρχείο
Το δεύτερο μοτίβο είναι η τιμή που δεν θα μπορούσε ποτέ να είναι σωστή: αρνητική, μηδενική σε έναν κόμβο με περιεχόμενο, ή παράλογα τεράστια. Αυτές προέρχονται από fuzzing, από βλάβη κατά τη μετάδοση, και περιστασιακά από σφάλματα αριθμητικής σε επεξεργαστές. Είναι επικίνδυνες συγκεκριμένα για κώδικα που εμπιστεύεται το /Count για εκχώρηση μνήμης — η προσαρμογή μεγέθους ενός πίνακα από ένα /Count ίσο με -3 προκαλεί στην καλύτερη περίπτωση σφάλμα εύρους, ενώ η ίδια πράξη από ένα /Count δύο δισεκατομμυρίων είναι μια εκχώρηση τύπου denial-of-service. Η τιμή είναι μη έμπιστη είσοδος, όπως κάθε άλλος αριθμός στο αρχείο
Οι αναλυτές χωρίζονται σε δύο στρατόπεδα σχετικά με όλα αυτά. Οι αυστηροί καταναλωτές — εργαλεία preflight, validators PDF/A, γραμμές αρχειοθέτησης — συγκρίνουν το /Count με το αποτέλεσμα της διάσχισης και απορρίπτουν ή επισημαίνουν το αρχείο. Τα διαδραστικά προγράμματα προβολής είναι σχεδόν πάντα ανεκτικά: διασχίζουν, εξάγουν την πραγματική τιμή, και αγνοούν σιωπηλά την αποθηκευμένη, κάτι που εξηγεί ακριβώς γιατί ένα αρχείο με μη ενημερωμένη τιμή μπορεί να κυκλοφορεί για χρόνια χωρίς παράπονα μέχρι να συναντήσει έναν αυστηρότερο αναλυτή μέσα σε κάποια αυτοματοποιημένη ροή εργασίας. Η αμυντική μέση λύση για κώδικα βιβλιοθήκης είναι να αντιμετωπίζει το /Count ως ένδειξη — χρήσιμη για προδέσμευση μνήμης, και για παράλειψη υποδέντρων μόλις επαληθευτεί — ενώ αφήνει τη διάσχιση να παραμένει η πηγή αλήθειας
Για τον ίδιο τον αλγόριθμο διάσχισης, τους κανόνες αναζήτησης κληρονομικότητας, και τη διαδρομή από τον κατάλογο έως το φύλλο, ξεκινήστε με το επεξηγηματικό άρθρο για τη σειρά σελίδων. Για το πώς μοιάζουν αυτές οι αστοχίες όταν ένα πραγματικό έγγραφο πελάτη φτάνει σε κώδικα παραγωγής, διαβάστε τη μελέτη περίπτωσης αποσφαλμάτωσης σειράς σελίδων, η οποία παρακολουθεί ένα περιστατικό ανακατεμένων σελίδων από το σύμπτωμα έως τη βασική αιτία
Το HotPDF Delphi Component χειρίζεται όλα αυτά εσωτερικά: διασχίζει ένθετα δέντρα οποιουδήποτε βάθους, επιλύει κληρονομημένα χαρακτηριστικά όταν σελίδες αντιγράφονται ή μετακινούνται, και επαληθεύει το /Count έναντι του πραγματικού αριθμού φύλλων αντί να το εμπιστεύεται, έτσι ώστε οι δείκτες σελίδων στο API του να σημαίνουν πάντα λογικές σελίδες