Oblika drevesa strani PDF: razvejanje, sploščanje in celovitost /Count

Naš spremljevalni članek o vrstnem redu strani PDF pojasnjuje temeljno pravilo: vrstni red prikaza izhaja iz prehoda po globini od leve proti desni skozi polja /Kids v drevesu /Pages, nikoli iz številk objektov. Ta članek si drevo ogleda z drugega zornega kota — njegove oblike. Zakaj zreli ustvarjalci PDF-jev generirajo hierarhije vmesnih vozlišč, ko bi bilo enojno plosko polje povsem skladno s specifikacijo? Kaj se dejansko spremeni, ko orodje drevo sploščí ali obnovi? In kaj se zgodi, ko knjigovodstvo /Count, ki celotno strukturo dela hitro, preneha govoriti resnico

Razvejanje je odločitev glede zmogljivosti

Nič ne prisili ustvarjalca k gnezdenju. Dokument z 10.000 stranmi z enim korenskim vozliščem /Pages in 10.000 sklici na liste v enem samem polju /Kids je skladen s specifikacijo. PDF Reference kljub temu za obsežne dokumente priporoča uravnoteženo drevo, glavni generatorji pa ta nasvet upoštevajo z zmernim razvejanjem, običajno po nekaj deset otrok na vmesno vozlišče

Razlog je v tem, kaj mora pregledovalnik prebrati, preden lahko karkoli prikaže. Predstavljajmo si skok naravnost na stran 8214 v tej datoteki z 10.000 stranmi. Pri ploskem drevesu mora pregledovalnik najprej razčleniti korensko vozlišče, to pa je eno samo ogromno polje: pri približno osmih bajtih na posredni sklic gre za 80 KB velik objekt, ki ga je treba tokenizirati od začetka do konca, preden je mogoče razrešiti vnos 8213. Pri uravnoteženem drevesu z razvejanjem 32 isti skok prebere koren, primerja tekoče vsote /Count, da izbere pravega otroka, in se spusti navzdol — skupno tri ali štiri majhne slovarje, vsak po nekaj sto bajtov. To je dostop z zapletenostjo O(log n), za katerega je bilo drevo zasnovano, in to je ves razlog, zakaj /Count obstaja na vmesnih vozliščih: bralniku omogoča, da preskoči celotno poddrevo, ne da bi odprl en sam objekt v njem

Oblika drevesa določa tudi ceno urejanja. Postopna posodobitev, ki vstavi eno stran, mora prepisati vsako vozlišče, katerega /Kids ali /Count se je spremenil, torej pot od starša novega lista navzgor do korena. V uravnoteženem drevesu je ta pot peščica majhnih slovarjev, dodanih datoteki. V ploskem drevesu je „pot“ eno samo velikansko korensko polje, v celoti podvojeno pri vsaki reviziji. Pogodba, ki gre skozi trideset ciklov pregleda in pripomb, lahko na koncu v svojem bajtnem toku vleče trideset presežených kopij istega 80 KB polja

Notranja vozlišča nosijo podedovane atribute

Vmesna vozlišča niso zgolj usmerjanje. Štiri podedljive lastnosti strani — /Resources, /MediaBox, /CropBox in /Rotate — je mogoče postaviti na katero koli vozlišče /Pages, kjer veljajo za vsak list pod njim, razen če jih potomec prepiše. Ustvarjalec, ki pripravlja poročilo s prilogo v ležeči postavitvi, lahko to postavitev izrazi kar v samem drevesu:

5 0 obj   % document root
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % report body: portrait A4, body font
<< /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   % dodatek: ležeči A4, zasukan, z lastno pisavo
<< /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  % appendix page: inherits size, rotation, fonts
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Objekti od 40 do 42 so skoraj prazni. Njihova velikost strani, zasuk in viri pisav v celoti prihajajo z dedovanjem iz vozlišča 7, kar datoteko ohranja kompaktno in samovzdržno: dodajte četrto stran pod vozlišče priloge in ta samodejno izpade v ležeči postavitvi

Isti mehanizem ustvarja klasično nevarnost pri premikanju strani. Recimo, da orodje premakne objekt 40 v telo poročila tako, da uredi obe polji /Kids in preusmeri /Parent na vozlišče 6. Premik je strukturno veljaven, vendar objekt 40 zdaj deduje pokončni /MediaBox, brez zasuka, in pisavo /F1 — medtem ko njegov vsebinski tok še vedno izbira /F2, ki se ne razreši več. Stran se z eno samo urejevalno operacijo skrči, izgubi zasuk in izgubi svoje besedilo. Zanesljiva koda za preurejanje zato pred spremembo starša materializira razrešene vrednosti vseh štirih podedljivih atributov na slovar strani. Če ste kdaj v urejevalniku povlekli stran in opazovali, kako spremeni velikost ali usmerjenost, ste priča prav temu mehanizmu

Sploščanje: zakonito, pogosto, občasno drago

Veliko orodij ravna nasprotno. Minimalistični ustvarjalci generirajo enonivojsko drevo, ker je preprosto, mnogi pripomočki za združevanje in razdeljevanje pa katero koli prebrano drevo obnovijo v eno samo plosko polje /Kids, ker je ustvarjanje uravnotežene strukture dodatno delo, plosk izhod pa je vedno skladen. Pravilna obnova mora hkrati razrešiti dedovanje: vsak atribut, ki ga je list dedoval, je treba kopirati nanj ali ga postaviti na novi koren, če je enoten po celotnem dokumentu — sicer izhod spremeni geometrijo natanko tako, kot pri premiku strani

Pri tipičnih dokumentih je sploščanje neškodljivo. Škoduje pri obsegu, in sicer na dva že opisana načina: korensko polje postane en velik objekt, ki ga mora vsako odpiranje in vsak skok na stran razčleniti v celoti, vsaka strukturna urejevalna operacija pa ga v celoti prepiše. Sploščanje ne uniči souporabe prek posrednih sklicev — plosko drevo, v katerem vseh 10.000 strani kaže na isti objekt slovarja /Resources, je še vedno deduplicirano. Izgubi se le možnost, da se vnos izpusti na strani in prepusti prednikoma, da ga zagotovi

Ko /Count laže

/Count je čisto knjigovodstvo: mora biti enak številu listnih strani v poddrevesu vozlišča, in nič v obliki datoteke tega ne vsiljuje. Za večino lažnih števcev, ki jih srečamo v praksi, sta odgovorna dva vzorca poškodb

Prvi je zastarel števec, ki ga za sabo pusti postopna posodobitev. Urejevalnik vstavi stran, prepiše neposrednega starša z novim /Kids in posodobljenim /Count, oboje doda datoteki — prednikov pa nikoli ne dotakne:

% Original revision
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

% Dodana revizija: ena stran vstavljena v srednjo vejo
% Object 14 is superseded; object 12 is never rewritten
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

Drevo zdaj vsebuje deset listov, koren pa še vedno pravi devet. Pregledovalnik, ki zaupa korenu, v svojem števcu strani javi devet strani. Tisti, ki za dvojiško iskanje skoka na stran uporablja notranje števce, za vsako stran po točki vstavljanja izračuna napačen indeks. Poln obhod jih najde deset. Tri različni odgovori, ena datoteka

Drugi vzorec je števec, ki nikoli ne more biti pravilen: negativen, ničeln na zapolnjenem vozlišču ali absurdno velik. Ti izvirajo iz fuzzinga, iz poškodb pri prenosu in občasno iz aritmetičnih napak v urejevalnikih. Še posebej nevarni so za kodo, ki pri dodeljevanju pomnilnika zaupa /Count — dimenzioniranje polja glede na /Count -3 v najboljšem primeru sproži napako obsega, dodeljevanje glede na /Count dve milijardi pa je dodeljevanje pomnilnika vrste odklonitev storitve. Ta vrednost je nezaupanja vreden vnos, tako kot vsako drugo število v datoteki

Parserji se glede vsega tega delijo v dva tabora. Strogi porabniki — orodja za predpregled, validatorji PDF/A, arhivski cevovodi — /Count primerjajo z rezultatom obhoda in datoteko zavrnejo ali označijo. Interaktivni pregledovalniki so skoraj vsi ohlapni: opravijo obhod, izpeljejo dejansko število in shranjeno vrednost tiho prezrejo, kar je natanko razlog, da lahko datoteka z zastarelim števcem leta kroži brez pritožb, dokler ne naleti na strožji parser znotraj kakega avtomatiziranega delovnega toka. Obrambna srednja pot za knjižnično kodo je obravnavati /Count kot namig — uporaben za vnaprejšnjo dodelitev pomnilnika in za preskakovanje poddreves po preverjanju — obhod pa naj ostane vir resnice

Za sam algoritem obhoda, pravila iskanja dedovanja in pot od kataloga do lista glejte članek o vrstnem redu strani. Kako te vrste napak izgledajo, ko prava strankina datoteka doseže produkcijsko kodo, si preberite v študiji primera odpravljanja napak vrstnega reda strani, ki sledi incidentu s premešanimi stranmi od simptoma do temeljnega vzroka

Komponenta HotPDF Delphi Component vse to obravnava interno: prehodi po gnezdenih drevesih poljubne globine, razreši podedovane atribute, ko se strani kopirajo ali premikajo, in preveri /Count glede na dejansko število listov, namesto da bi mu zaupala, tako da indeksi strani v njenem API-ju vedno pomenijo logične strani