PDF-sivupuun (Page Tree Shape: Fan-Out) muoto (Shape): Haarautuminen (Fan-Out), litistäminen (Flattening) ja (and) /Count-eheys (Count Integrity)

Rinnakkainen artikkelimme PDF-sivujärjestyksestä kattaa perussäännön: näyttöjärjestys tulee syvyys ensin, vasemmalta oikealle -läpikulusta /Pages-puun /Kids-taulukoiden yli, ei koskaan objektinumeroista. Tämä artikkeli tarkastelee puuta toisesta näkökulmasta — sen muodosta. Miksi kypsät PDF-kirjoittajat tuottavat hierarkioita välisolmuista, kun yksittäinen litteä taulukko olisi täysin laillinen? Mikä oikeasti muuttuu, kun työkalu litistää tai rakentaa puun uudelleen? Ja mitä tapahtuu, kun /Count-kirjanpito, joka tekee koko rakenteesta nopean, lakkaa kertomasta totuutta

Haarautuminen on suorituskykypäätös

Mikään ei pakota kirjoittajaa muodostamaan sisäkkäisyyksiä. 10 000-sivuinen asiakirja, jossa on yksi juuritason /Pages-solmu ja 10 000 lehtiviittausta yhdessä /Kids-taulukossa, on määritysten mukainen. PDF Reference suosittelee silti tasapainoista puuta suurille asiakirjoille, ja valtavirran generaattorit noudattavat tuota neuvoa vaatimattomalla haarautumisella, tyypillisesti muutamalla kymmenellä lapsella välisolmua kohden

Syy on se, mitä katseluohjelman on luettava, ennen kuin se voi näyttää mitään. Kuvitellaanpa suoraa hyppyä tuon 10 000-sivuisen tiedoston sivulle 8214. Litteällä puulla katseluohjelman on ensin jäsennettävä juurisolmu, ja tuo juurisolmu on yksi valtava taulukko: karkeasti kahdeksan tavua epäsuoraa viittausta kohden tarkoittaa 80 kt:n objektia, joka on tokenisoitava alusta loppuun, ennen kuin merkintä 8213 voidaan ratkaista. Tasapainoisessa puussa, jonka haarautuminen on 32, sama hyppy lukee juuren, vertailee juoksevia /Count-kokonaissummia oikean lapsen valitsemiseksi ja laskeutuu alaspäin — yhteensä kolme tai neljä pientä sanakirjaa, kukin muutaman sadan tavun kokoinen. Tuo on se O(log n) -satunnaissaanti, jota puu suunniteltiin tarjoamaan, ja se on koko syy siihen, miksi /Count on olemassa välisolmuissa: se antaa lukijan ohittaa kokonaisen alipuun avaamatta ainuttakaan sen sisällä olevaa objektia

Puun muoto asettaa myös muokkauskustannukset. Inkrementaalisen päivityksen, joka lisää yhden sivun, on kirjoitettava uudelleen jokainen solmu, jonka /Kids tai /Count muuttui, mikä tarkoittaa polkua uuden lehden isännästä ylös juureen. Tasapainoisessa puussa tuo polku on kourallinen tiedoston loppuun liitettyjä pieniä sanakirjoja. Litteässä puussa "polku" on yksittäinen jättimäinen juuritaulukko, joka monistetaan kokonaisuudessaan jokaisella versiolla. Sopimus, joka käy läpi kolmekymmentä tarkastus- ja kommentointikierrosta, voi päätyä raahaamaan tavuvirrassaan mukanaan kolmekymmentä korvattua kopiota samasta 80 kt:n taulukosta

Sisäiset solmut kantavat perittyjä attribuutteja

Välisolmut eivät ole vain reititystä varten. Neljä perittävää sivuattribuuttia — /Resources, /MediaBox, /CropBox ja /Rotate — voidaan nostaa mihin tahansa /Pages-solmuun, jossa ne koskevat jokaista sen alapuolella olevaa lehteä, ellei jälkeläinen ohita niitä. Kirjoittaja, joka tuottaa raportin, jossa on vaakasuuntainen liite, voi ilmaista tuon asettelun itse puussa:

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

6 0 obj   % raportin runko: pystysuuntainen A4, runkofontti
<< /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   % liite: vaakasuuntainen A4, kierretty, oma fontti
<< /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  % liitesivu: perii koon, kierron ja fontit
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Objektit 40–42 ovat lähes tyhjiä. Niiden sivukoko, kierto ja fonttiresurssit saapuvat kaikki perintönä solmulta 7, mikä pitää tiedoston kompaktina ja itseään ylläpitävänä: lisää neljäs sivu liitesolmun alle, ja se tulostuu vaakasuuntaisena automaattisesti

Sama mekanismi luo klassisen sivunsiirron vaaran. Oletetaan, että työkalu siirtää objektin 40 raportin runkoon muokkaamalla kahta /Kids-taulukkoa ja osoittamalla /Parent-arvon uudelleen solmuun 6. Siirto on rakenteellisesti kelvollinen, mutta silti objekti 40 perii nyt pystysuuntaisen /MediaBox-arvon, ei kiertoa, ja fontin /F1 — vaikka sen sisältövirta valitsee edelleen fontin /F2, jota ei enää pystytä ratkaisemaan. Sivu kutistuu, purkautuu kierrosta ja kadottaa tekstinsä yhdessä muokkauksessa. Vankka uudelleenjärjestelykoodi siksi realisoi kaikkien neljän perittävän attribuutin ratkaistut arvot sivusanakirjaan ennen sivun uudelleenisännöintiä. Jos olet koskaan vetänyt sivua editorissa ja seurannut sen muuttavan kokoa tai suuntaa, tämä on se mekanismi, jonka näit

Litistäminen: laillista, yleistä, ajoittain kallista

Useat työkalut kulkevat toiseen suuntaan. Minimaaliset kirjoittajat tuottavat yksitasoisen puun, koska se on yksinkertaista, ja monet yhdistämis- ja jakotyökalut rakentavat lukemansa puun uudelleen yhdeksi litteäksi /Kids-taulukoksi, koska tasapainoisen rakenteen luominen on ylimääräistä työtä ja litteä tuloste on aina määritysten mukainen. Oikean uudelleenrakentamisen on ratkaistava perintä samalla kertaa: jokainen attribuutti, jonka lehti peri, on joko kopioitava lehteen tai nostettava uuteen juureen, jos se on yhdenmukainen koko asiakirjassa — muuten tulosteen geometria muuttuu aivan samalla tavalla kuin sivunsiirtotapauksessa

Tyypillisille asiakirjoille litistäminen on vaaratonta. Se satuttaa skaalautuessa kahdella jo kuvatulla tavalla: juuritaulukosta tulee yksi suuri objekti, joka jokaisen avauksen ja sivuhypyn on jäsennettävä kokonaisuudessaan, ja jokainen rakenteellinen muokkaus kirjoittaa sen kokonaan uudelleen. Mitä litistäminen ei tuhoa, on jakaminen epäsuorien viittausten kautta — litteä puu, jossa kaikki 10 000 sivua osoittavat samaan /Resources-sanakirjaobjektiin, on edelleen deduplikoitu. Ainoa, mikä menetetään, on mahdollisuus jättää merkintä pois sivulta ja antaa esi-isän tarjota se

Kun /Count valehtelee

/Count on puhdasta kirjanpitoa: sen on oltava yhtä suuri kuin solmun alipuun lehtisivujen määrä, eikä mikään tiedostomuodossa valvo sitä. Kaksi korruptiokuviota aiheuttaa suurimman osan luonnossa nähdyistä valehtelevista laskuista

Ensimmäinen on inkrementaalisen päivityksen jälkeensä jättämä vanhentunut laskuri. Editori lisää sivun, kirjoittaa välittömän isännän uudelleen uudella /Kids-taulukolla ja päivitetyllä /Count-arvolla, liittää molemmat tiedostoon — eikä koskaan koske esi-isiin:

% Alkuperäinen versio
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

% Liitetty versio: yksi sivu lisätty keskimmäiseen haaraan.
% Objekti 14 korvataan; objektia 12 ei koskaan kirjoiteta uudelleen
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

Puu sisältää nyt kymmenen lehteä, mutta juuri sanoo edelleen yhdeksän. Katseluohjelma, joka luottaa juureen, ilmoittaa sivulaskurissaan yhdeksän sivua. Ohjelma, joka käyttää sisäisiä laskuja binäärihakuun sivuhypyssä, laskee väärän indeksin jokaiselle lisäyskohdan jälkeiselle sivulle. Täysi läpikäynti löytää kymmenen. Kolme eri vastausta, yksi tiedosto

Toinen kuvio on lukema, joka ei koskaan voisi olla oikein: negatiivinen, nolla asutetulla solmulla, tai absurdin suuri. Nämä johtuvat sumennuksesta, siirtovaurioista ja satunnaisesti editorien laskuvirheistä. Ne ovat vaarallisia erityisesti koodille, joka luottaa /Count-arvoon allokoinnissa — taulukon mitoittaminen /Count-arvosta -3 nostaa parhaimmillaan aluevirheen, ja saman tekeminen /Count-arvosta kaksi miljardia on palvelunestohyökkäysallokointi. Arvo on epäluotettavaa syötettä, kuten kaikki muutkin tiedoston numerot

Jäsentimet jakautuvat tässä kahteen leiriin. Tiukat kuluttajat — esitarkastustyökalut, PDF/A-validaattorit, arkistointiputket — vertaavat /Count-arvoa läpikäyntitulokseen ja hylkäävät tiedoston tai merkitsevät sen. Interaktiiviset katseluohjelmat ovat lähes poikkeuksetta lempeitä: ne käyvät puun läpi, johtavat todellisen määrän ja jättävät tallennetun arvon äänettömästi huomiotta, mikä on täsmälleen se syy, miksi vanhentuneella laskurilla varustettu tiedosto voi kiertää vuosia ilman valituksia, kunnes se kohtaa tiukemman jäsentimen jonkin automaattisen työnkulun sisällä. Puolustava keskitie kirjastokoodille on käsitellä /Count-arvoa vihjeenä — hyödyllisenä ennakkoallokointiin ja alipuun ohittamiseen sen jälkeen, kun se on varmennettu — antaen samalla läpikäynnin pysyä totuuden lähteenä

Itse läpikäyntialgoritmiin, perinnän hakusääntöihin ja katalogista lehteen -kävelyyn liittyen, aloita sivujärjestyksen selityksestä. Nähdäksesi, miltä nämä epäonnistumistilat näyttävät, kun todellinen asiakasasiakirja saavuttaa tuotantokoodin, lue sivujärjestyksen virheenkorjauksen tapaustutkimus, joka seuraa sivujen sekoittumistapausta oireesta juurisyyhyn

HotPDF Delphi Component käsittelee tämän kaiken sisäisesti: se käy läpi minkä tahansa syvyisiä sisäkkäisiä puita, ratkaisee perityt attribuutit, kun sivuja kopioidaan tai siirretään, ja varmistaa /Count-arvon todellisia lehtimääriä vasten luottamisen sijaan, joten sen API:n sivuindeksit tarkoittavat aina loogisia sivuja