CollateDocumentsEx in der Delphi-PDF-Library PDFlibPas führt mehrere geöffnete Dokumente zu einem verschachtelten Dokument zusammen. Es hängt pro Runde GroupSize Seiten von jeder Quelle an, akzeptiert eine Liste von Seitenbereichen pro Quelle und behandelt einen absteigenden Bereich wie 3-1 als Umkehrung dieser Quelle. Ein Aufruf verwandelt einen Vorderseiten-Stapel und einen umgekehrten Rückseiten-Stapel in Leserichtung
Das Szenario hinter dieser API ist alltäglich und äußerst verbreitet. Ein Einzugsscanner mit einseitigem Pfad läuft den ganzen Stapel mit der Vorderseite nach unten durch, dann dreht der Bediener den Stapel um und lässt ihn erneut durchlaufen. Man erhält am Ende zwei PDF-Dateien: Vorderseiten in Reihenfolge, Rückseiten in umgekehrter Reihenfolge. Die vom Anwender gewünschte Ausgabe ist eine Datei, Seite 1 vorne, Seite 1 hinten, Seite 2 vorne, und so weiter. Dieser Artikel behandelt das Reihenfolgeproblem und die darunterliegende Falle der Ressourcenduplizierung. Wer sich für den reinen Konkatenations-Durchsatz interessiert, findet das in schnelles PDF-Merge durch Byte-Ebenen-Ref-Shifting; sind die Eingaben zu groß, um überhaupt im Speicher gehalten zu werden, siehe Zusammenführen und Aufteilen von Gigabyte-PDF-Dateien mit direktem Zugriff
Der Scanner erzeugt zwei Stapel, einer davon rückwärts
Kollationieren ist kein Zusammenführen. Ein Merge verkettet Seitenbereiche; eine Kollation verschachtelt sie, und das Verschachtelungsmuster ist eine Eigenschaft des physischen Geräts, das die Eingabe erzeugt hat. Liegt man beim Muster falsch, ist die Datei nicht ein bisschen falsch, sie ist unlesbar: jede zweite Seite gehört zu einem anderen Blatt. Drei Variablen beschreiben fast jeden echten Fall: wie viele Quellen in der Rotation sind, wie viele Seiten pro Runde von jeder Quelle kommen, und ob eine Quelle rückwärts gelesen werden muss. CollateDocuments deckt die ersten zwei mit einem schlichten Array von Dokument-Handles und einem GroupSize-Integer ab. CollateDocumentsEx fügt die dritte hinzu, indem es eine durch Semikolons getrennte Liste von Seitenbereichen akzeptiert, ein Segment pro Quelle, wobei ein leeres Segment alle Seiten dieser Quelle bedeutet und ein absteigender Bereich sie umkehrt. Beide Funktionen hängen an das Ende des aktuell ausgewählten Dokuments an und liefern bei Erfolg 1, bei jeder Ablehnung 0 zurück
Warum vervielfacht das naive Kollationieren die Dateigröße?
Weil die Import-Map, die Quell-Objektnummern auf Ziel-Objektnummern abbildet, bei jedem Kopieraufruf neu aufgebaut wird, und alles, was von mehr als einem Chunk aus erreichbar ist, einmal pro Chunk importiert wird. Innerhalb von PDFlibPas setzt TPDFDocument.CopyPagesFromDoc seine NewIndObjList zu Beginn jedes Aufrufs zurück. Diese Liste ist das einzige Gedächtnis, das der Kopierer dafür hat, was er bereits herübergebracht hat. Ruft man sie einmal mit einem Zehn-Seiten-Bereich auf, wird eine von allen zehn Seiten gemeinsam genutzte Schrift einmal eingebettet. Ruft man sie zehnmal mit je einer Seite auf, wird dieselbe Schrift zehnmal eingebettet. Das spielt bei Scans weit stärker eine Rolle als bei Textdokumenten, weil eine gescannte Seite ein einziges großes Bild-XObject ist, und die gemeinsam genutzten Objekte sind die mit echtem Gewicht: ein eingebettetes ICC-Profil, eine gemeinsame /DecodeParms-Kette, ein Stempel- oder Wasserzeichen-Form-XObject, das auf jedes Blatt angewendet wird, die Schrift der OCR-Textebene. Der naheliegende Weg, ein Round-Robin-Kollationieren zu schreiben, ist eine Schleife über Runden, und genau diese Schleife ist der pathologische Fall
// Do not do this. Each CopyPageRanges call rebuilds the import map,
// so anything the two sources share internally is imported once per
// round instead of once per source.
var
RoundIndex: Integer;
begin
for RoundIndex := 1 to 12 do
begin
PDF.CopyPageRanges(Fronts, IntToStr(RoundIndex));
PDF.CopyPageRanges(Backs, IntToStr(13 - RoundIndex));
end;
end;Zwölf Runden, zwei Quellen, vierundzwanzig Import-Maps. Nichts warnt einen. Die Seitenreihenfolge ist korrekt, jede Seite rendert, und das einzige Symptom ist eine Datei, die um ein Vielfaches größer ist als die Summe ihrer Eingaben. Bei einem 300-Seiten-Batch-Job ist der Multiplikator kein Rundungsfehler, er ist der Unterschied zwischen einem Archiv, das ins Aufbewahrungsbudget passt, und einem, das es nicht tut
Einmal importieren, dann den Seitenbaum umordnen
Die Lösung besteht darin, die beiden Anliegen zu trennen, die die naive Schleife verschmolzen hatte. Kopieren entscheidet, welche Objekte im Ziel existieren; Ordnung entscheidet, wo die Seiten im Seitenbaum sitzen. CollateDocumentsEx kopiert jede Quelle genau einmal, in einem einzigen CopyPagesFromDoc-Aufruf mit dem vollständigen Bereich dieser Quelle, sodass jede Quelle eine Import-Map bekommt und gemeinsam genutzte Ressourcen einmal geschrieben werden. Erst nachdem jede Quelle gelandet ist, geschieht die Verschachtelung, und sie geschieht vollständig über TPDFPageTree.MovePage
Seitenverschiebungen sind in dem hier relevanten Sinne kostenlos. ISO 32000-1 §7.7.3 definiert den Seitenbaum als eine balancierte Struktur von Knoten-Dictionaries, deren /Kids-Arrays indirekte Referenzen halten, wobei /Count an jedem Knoten die Blattsumme trägt. Eine Seite umzusetzen bedeutet, eine indirekte Referenz aus einem /Kids-Array zu entfernen, sie in ein anderes einzufügen, beide /Count-Werte anzupassen und den Seiten-/Parent neu zu setzen. Kein Content-Stream wird berührt, keine Ressource wird dupliziert, kein Objekt wird erzeugt. Das Seitenobjekt behält seine Objektnummer, was auch der Grund ist, warum Objektnummern so stabil bleiben wie in Seitenersetzung, die Objektnummern erhält. Ein weiteres Detail, das eine naive Seitenverschiebung falsch macht, macht MovePage richtig. ISO 32000-1 §7.7.3.4 erlaubt, dass /Resources, /MediaBox, /CropBox und /Rotate von einem Vorfahrenknoten geerbt werden, statt auf der Seite selbst zu stehen. Eine Seite, die ihre Ressourcen von Knoten A erbt und dann unter Knoten B verschoben wird, erbt still etwas anderes, oder gar nichts. MovePage löst deshalb den geerbten Wert auf und schreibt ihn auf das Seiten-Dictionary, bevor die Verschiebung erfolgt, sodass die Seite ihre eigenen Attribute über die Verschiebung hinweg trägt
Was macht der Umordnungsdurchgang tatsächlich?
Er führt einen Selection-Sort gegen Insert-at-Semantik aus. Die gewünschte blockrelative Reihenfolge wird zuerst berechnet: die Quellen der Rotation nach durchlaufen, bis zu GroupSize Indizes aus jeder nehmen, eine erschöpfte Quelle überspringen, wiederholen, bis jede Seite platziert ist. Das ergibt eine Permutation über den angehängten Block. Sie anzuwenden ist der unangenehme Teil, weil MovePage ein Insert ist, kein Swap, sodass jede Verschiebung alles zwischen alter und neuer Position um eins verschiebt
Die Implementierung führt ein Current-Array, das modelliert, wo jede angehängte Seite gerade sitzt, scannt von Position K aus vorwärts nach der Seite, die dort hingehört, führt die Verschiebung aus, und verschiebt dann die Array-Einträge, um das nachzubilden, was die Verschiebung am Baum bewirkt hat. Es ist O(n Quadrat) an Array-Operationen und null an Objektkopien, was der richtige Kompromiss für diese Arbeitslast ist: Ein 500-Seiten-Kollationieren ist eine Viertelmillion Ganzzahl-Umsortierungen und nicht ein Byte duplizierter Bilddaten. Absteigende Bereiche und wiederholte Seiten brauchen in diesem Durchgang keine Sonderbehandlung, weil PLParsePageRangeList mit deaktivierter Sortierung und erlaubten Duplikaten aufgerufen wird, sodass die angeforderte Reihenfolge das Parsen unbeschadet übersteht
Umgekehrte Bereiche und der Duplex-Merge in einem Aufruf
Wird die Umkehrung als Bereich ausgedrückt, kollabiert der Flachbett-Doppeldurchlauf-Fall zu einem einzigen Aufruf. Die Vorderseiten wollen ihre natürliche Reihenfolge, und die Rückseiten wollen 12-1, und das leere erste Segment vor dem Semikolon sagt, dass die erste Quelle alle ihre Seiten beiträgt
var
PDF: TPDFlib;
Target, Fronts, Backs: Integer;
begin
PDF := TPDFlib.Create;
try
Target := PDF.NewDocument;
if PDF.LoadFromFile('fronts.pdf', '') <> 1 then
Exit;
Fronts := PDF.SelectedDocument;
if PDF.LoadFromFile('backs.pdf', '') <> 1 then
Exit;
Backs := PDF.SelectedDocument;
PDF.SelectDocument(Target);
// fronts 1..12 in order, backs scanned in reverse: F1 B12 F2 B11 ...
if PDF.CollateDocumentsEx([Fronts, Backs], ';12-1', 1) = 1 then
PDF.SaveToFile('duplex.pdf');
finally
PDF.Free;
end;
end;Zwei Verhaltensweisen in diesem Ausschnitt lohnt es, ausdrücklich zu benennen. Die kollationierten Seiten werden an das ausgewählte Dokument angehängt, sodass ein mit NewDocument erstelltes Dokument seine anfängliche leere Seite vor ihnen beiträgt, und man sollte sie löschen, wenn man sie nicht will. Und die Quellen dürfen ungleich sein: Bei GroupSize 2 über eine drei- und eine fünfseitige Quelle kommen die Runden als A1 A2 B1 B2 heraus, dann A3 B3 B4, sobald A fast erschöpft ist, dann B5 allein, weil eine erschöpfte Quelle einfach übersprungen statt aufgefüllt wird
Rollback, Formularfelder, und was nicht mitkommt
Jedes Argument wird validiert, bevor das Ziel berührt wird. Ein fehlendes Dokument-Handle, das ausgewählte Dokument als eigene Quelle aufgeführt, ein GroupSize unter eins, eine Segmentanzahl, die nicht zur Quellenanzahl passt, ein Bereich, der eine Seite benennt, die die Quelle nicht hat: All das liefert 0 zurück, das Ziel bleibt unverändert. Ein Fehlschlag während des Kopierens ist der schwierigere Fall, und er wird über das öffentliche DeletePages behandelt, nicht über das rohe PageTree.DeletePages. Der Grund ist konkret. Das Kopieren läuft mit aktiviertem MergeFormData, sodass die Formularfelder der Quelle bereits an das Ziel-/AcroForm /Fields-Array angehängt wurden, wenn eine spätere Quelle fehlschlägt. Die Seiten auf Seitenbaum-Ebene zu löschen, würde die Widget-Seiten entfernen und diese Feldreferenzen baumelnd zurücklassen; der öffentliche Pfad hebt die Verknüpfung von Feld-, Outline- und Article-Thread-Referenzen zusammen mit den Seiten auf
if PDF.CollateDocumentsEx([Fronts, Backs], ';12-1', 1) = 0 then
// Nothing was appended and the target is byte-identical to before.
// 412 is the copy failure; 0 means the arguments were rejected
// during validation, before any page was touched.
Log(Format('collate rejected, LastErrorCode=%d', [PDF.LastErrorCode]));Man sollte gegenüber den eigenen Anwendern ehrlich über die Grenzen sein. Das Kollationieren trägt Seiten, ihre Annotationen und ihre Formularfelder, und es führt die AcroForm-Feldliste, das Berechnungsreihenfolge-Array und das Default-Resources-Dictionary zusammen. Es trägt keine Quell-Lesezeichen: Der Outline-Baum eines gescannten Vorderseiten-Stapels ist fast immer leer, sodass im Duplex-Fall nichts verlorengeht, aber kollationiert man zwei bereits erstellte Dokumente, bleiben deren Outlines zurück, und man baut die Navigation selbst neu auf. Benannte Ziele, die nur im Quell-Katalog lebten, sind in derselben Lage. Das sollte man einplanen, bevor man einem Kunden ein verlustfreies Kollationieren verspricht
PDFlibPas liefert die Kollationsfunktionen zusammen mit dem Rest seiner Seitenaufbau-Oberfläche aus, sodass Scanner-Workflow, bereichsbasierte Extraktion und Großdatei-Pfade alle hinter einer Komponente in Delphi und C++Builder sitzen. Die vollständige API-Referenz und ein Testbuild finden sich auf der Produktseite der losLab-Delphi-PDF-Library