Ein PDF hat keine Änderungsverfolgung. Wenn ein Vertrag als PDF „mit ein paar kleinen Anpassungen“ zurückkommt, steckt die einzige Information darüber, was sich geändert hat, im Unterschied zwischen zwei Dateien. Es gibt drei naheliegende Wege, diesen Unterschied zu berechnen: die gerenderten Seiten Pixel für Pixel vergleichen, den extrahierten Text Zeile für Zeile vergleichen oder ihn Wort für Wort vergleichen. Auf demselben Dateipaar liefern sie sehr unterschiedliche Ergebnisse, und nur einer davon übersteht es, wenn die Textverarbeitung der Gegenseite den Text neu umbricht.
Unten stehen Messungen aller drei Ansätze an einem echten PDF-Paar und danach ein Vergleich auf Wortebene in rund 120 Zeilen Python (PyMuPDF plus difflib aus der Standardbibliothek), der die Boxen jedes geänderten Worts ermittelt und die Änderungen als Kommentare zurück ins PDF schreibt. Der PDF Editor in der Desktop-App von osFoundry funktioniert genauso: Sein Dialog „Dateien vergleichen“ erklärt, dass der Text Wort für Wort verglichen und die Unterschiede in der neuen Datei angezeigt werden, und bei diesem Paar meldet er dieselben fünf Änderungen wie das Skript unten.
Das Testpaar
Die Dateien sind ein frei erfundener einseitiger Vertrag über Designleistungen (Example), erzeugt mit PyMuPDF, damit die Textebene echt ist. Die zurückgeschickte Version enthält fünf Änderungen:
| Klausel | Verschickt | Zurückgekommen |
|---|---|---|
| 3. Payment | within 30 days. Late payments add a 2% fee each month. | within 60 days. |
| 4. Revisions | two rounds of revisions | unlimited rounds of revisions |
| 5. Ownership | the final logo once the fee is paid in full. | the final logo and all drafts once work begins. |
Um zu simulieren, dass die Software der Gegenseite den Text neu setzt, enthält eine dritte Datei exakt dieselben Wörter der zurückgeschickten Version, neu gesetzt in 12 pt auf einer 300 pt breiten Spalte statt in 11.5 pt auf 468 pt. Gleicher Text, andere Zeilenumbrüche.
Pixel, Zeilen oder Wörter
Der Pixel-Diff rendert jeweils die erste Seite beider Dateien mit 72 dpi in Graustufen und zählt die Zeilen, in denen irgendein Pixel um mehr als 40 Stufen abweicht; ein „Band“ ist eine zusammenhängende Folge solcher Zeilen. Der Zeilen-Diff lässt difflib.SequenceMatcher über page.get_text() laufen, aufgeteilt an Zeilenumbrüchen. Der Wort-Diff ist das Skript weiter unten.
| Neue Datei | Pixel-Diff | Zeilen-Diff | Wort-Diff |
|---|---|---|---|
| So wie zurückgeschickt | 30 von 792 Zeilen, 3 Bänder | 3 Hunks, 3 Zeilen | 5 Änderungen |
| Gleiche Wörter, neu gesetzt | 284 von 792 Zeilen, 20 Bänder | 6 Hunks, 9 Zeilen | 5 Änderungen |
Bei der Datei, so wie sie zurückkam, findet der Pixel-Diff drei Bereiche und der Zeilen-Diff drei Zeilen. Beides stimmt, aber keiner von beiden sagt, was sich geändert hat: Der Zeilen-Diff meldet Klausel 3 als eine ersetzte Zeile, und „30“ gegenüber „60“ musst du immer noch selbst finden. Bei der neu gesetzten Kopie leuchten im Pixel-Diff 20 einzelne Bänder über fast den ganzen Text auf, und der Zeilen-Diff verdoppelt sich auf 9 betroffene Zeilen, weil sich der Umbruch verschoben hat. Der Wort-Diff liefert bei beiden Dateien dieselben fünf Änderungen, weil Leerraum und Zeilenumbrüche bei ihm gar nicht erst ankommen.
Zeichen samt Boxen extrahieren
Um Änderungen zu finden, reicht ein einfacher get_text()-String, aber um sie auf der Seite zu markieren, braucht man Koordinaten. get_text("rawdict") liefert jedes Zeichen mit seiner Bounding Box. Die folgende Funktion macht daraus eine flache Liste in Lesereihenfolge:
import difflib, re, sys, unicodedata
import pymupdf
def char_stream(path):
"""All characters of a PDF in reading order, NFKC-normalised, each with its page and box."""
chars = []
for pno, page in enumerate(pymupdf.open(path)):
for block in page.get_text('rawdict', sort=True)['blocks']:
for line in block.get('lines', []):
for span in line['spans']:
for ch in span['chars']:
for c in unicodedata.normalize('NFKC', ch['c']):
chars.append((c, pno, pymupdf.Rect(ch['bbox'])))
chars.append(('\n', pno, None)) # a line break is only whitespace
return chars
Zwei Details sind wichtig. sort=True sortiert die Blöcke von oben nach unten und von links nach rechts, und genau das will man bei einem einspaltigen Vertrag (zweispaltige Layouts brauchen eine eigene Sortierung). NFKC führt ähnlich aussehende Zeichen zusammen, sodass ein auf der einen Seite getipptes vollbreites „６０“ und ein „60“ auf der anderen nicht als Änderung auftauchen. Jedes normalisierte Zeichen behält die Box des Zeichens, aus dem es entstanden ist, damit die Liste deckungsgleich mit der Seite bleibt.
Tokens: Wörter, und dort, wo es keine Leerzeichen gibt, jeweils ein Zeichen
Der Diff arbeitet auf Tokens, nicht auf Zeichen. Ein Token ist hier eine Folge lateinischer Buchstaben und Ziffern oder ein beliebiges anderes einzelnes sichtbares Zeichen:
TOKEN = re.compile(r"[0-9A-Za-z][0-9A-Za-z.,%$'’-]*(?<![.,])|\S")
def tokens(chars):
text = ''.join(c for c, _, _ in chars)
return text, [(m.start(), m.end(), m.group()) for m in TOKEN.finditer(text)]
Für Englisch ergibt das Wörter, wobei ein abschließender Punkt abgetrennt wird, damit „days.“ und „days“ trotzdem übereinstimmen. Zahlen bleiben am Stück, eine Änderung erscheint also als „30“ → „60“ und nicht als „3“ → „6“.
Der Teil mit dem „beliebigen anderen einzelnen Zeichen“ ist für Sprachen ohne Leerzeichen zwischen den Wörtern gedacht. Teilt man eine japanische Version desselben Vertrags an Leerraum auf, was PyMuPDFs get_text("words") macht, bekommt man ein „Wort“ pro Satz, und der Diff meldet drei komplette Sätze als ersetzt. Mit einem Token pro Zeichen findet er die Änderungen innerhalb der Sätze, allerdings als 8 Fragmente, weil gemeinsame Zeichen wie の eine Änderung in Stücke zerteilen („2“ gelöscht, „まで“ → „数“, „制限なく“ eingefügt). Führt man Änderungen zusammen, die höchstens ein unverändertes Zeichen trennt, sind es nur noch 5, also dieselben fünf Änderungen wie in der englischen Datei. Im Englischen greift das Zusammenführen nie, denn die kürzeste Lücke zwischen zwei Änderungen („once“) ist vier Zeichen lang.
Der Diff
PUNCT = set('.。．!?')
def hunks(old_toks, new_toks, gap_chars=1):
a = [t for _, _, t in old_toks]
b = [t for _, _, t in new_toks]
out = []
for tag, i1, i2, j1, j2 in difflib.SequenceMatcher(None, a, b, autojunk=False).get_opcodes():
if tag == 'equal':
continue
if tag in ('delete', 'insert'):
seq, lo, hi = (a, i1, i2) if tag == 'delete' else (b, j1, j2)
k = 0
while hi + k < len(seq) and seq[lo + k] == seq[hi + k]:
k += 1
if seq[hi + k - 1] in PUNCT and seq[lo + k] not in PUNCT:
i1, i2, j1, j2 = (i1 + k, i2 + k, j1 + k, j2 + k)
break
if out:
pi1, pi2, pj1, pj2 = out[-1]
if sum(len(x) for x in a[pi2:i1]) <= gap_chars and sum(len(x) for x in b[pj2:j1]) <= gap_chars:
out[-1] = [pi1, i2, pj1, j2]
continue
out.append([i1, i2, j1, j2])
return out
Die Verschiebeschleife fängt eine Eigenheit ab, die jeder Diff-Algorithmus hat. Der gelöschte Satz steht zwischen „days“ und „4. Revisions“, und der Text drumherum lautet auf der einen Seite „. Late payments add a 2% fee each month.“ und auf der anderen „.“. „. Late … month“ zu löschen und „Late … month.“ zu löschen ist gleich minimal, und SequenceMatcher hat sich für Ersteres entschieden. Schiebt man eine reine Löschung oder Einfügung so lange über die wiederholten Tokens, bis sie auf einem Satzzeichen endet, erhält man die Variante, die ein Mensch markieren würde.
autojunk=False ist Absicht; dazu weiter unten mehr. Auf die beiden Dateien angewendet, gibt das vollständige Skript (contract_diff.py) Folgendes aus:
5 changes
1. replaced '30' -> '60'
2. deleted 'Late payments add a 2% fee each month.' -> ''
3. replaced 'two' -> 'unlimited'
4. inserted '' -> 'and all drafts'
5. replaced 'the fee is paid in full' -> 'work begins'
und für die neu gesetzte Kopie exakt dieselben fünf Zeilen.
Die Änderungen als Kommentare zurückschreiben
Jedes Token trägt die Boxen seiner Zeichen mit sich, also besteht das Markieren einer Änderung in der neuen Datei aus einer Hervorhebungsannotation über diesen Boxen, zeilenweise zusammengefasst, mit altem und neuem Text als Kommentar. Bei einer Löschung bleibt nichts zum Hervorheben übrig, deshalb bekommt sie ein Notizsymbol direkt hinter dem Text, der ihr vorausging:
def mark(new_pdf, changes, out_pdf):
doc = pymupdf.open(new_pdf)
for ch in changes:
by_page = {}
for pno, r in ch['boxes']:
rects = by_page.setdefault(pno, [])
if rects and abs(rects[-1].y0 - r.y0) < 2: # same line: one box, not one per character
rects[-1] |= r
else:
rects.append(pymupdf.Rect(r))
note = {'replaced': f'Replaced: "{ch["old"]}" with "{ch["new"]}"',
'deleted': f'Deleted: "{ch["old"]}"',
'inserted': f'Inserted: "{ch["new"]}"'}[ch['kind']]
for pno, rects in by_page.items():
page = doc[pno]
if ch['kind'] == 'deleted':
annot = page.add_text_annot(rects[-1].tr + (2, -4), note, icon='Comment')
else:
annot = page.add_highlight_annot(rects)
annot.set_info(content=note)
annot.set_info(title='compare')
annot.update()
doc.save(out_pdf)
Das sind ganz normale PDF-Annotationen, also zeigen gängige PDF-Viewer sie an, und wer die Änderungen geschickt hat, sieht genau, worauf sich deine Rückfrage bezieht.
Lange Verträge: autojunk und Klausel für Klausel
SequenceMatcher hat eine Heuristik namens autojunk: Hat die zweite Sequenz 200 oder mehr Elemente, wird jedes Element, das mehr als 1% davon ausmacht, als Ankerpunkt für Übereinstimmungen ignoriert. Gedacht ist das für Dinge wie Leerzeilen in Quellcode. In Vertragstext sind die häufigen Tokens Wörter wie „the“ oder im Japanischen の und 甲 (die Bezeichnung des Vertrags für eine der Parteien). Bei der einseitigen japanischen Datei (238 Tokens in der neuen Version) hat sie 18 verschiedene Zeichen aussortiert, darunter 甲, 乙, の und 。, und das Ergebnis änderte sich von 8 Hunks auf 6. In diesem Fall nicht schlechter, aber anders, und so etwas will man bei einem Dokument, das man gleich unterschreibt, nicht einer Heuristik überlassen.
Das Abschalten hat seinen Preis. Im schlimmsten Fall ist der Diff ungefähr quadratisch, und ein 40-seitiger Vertrag ist weit länger als eine Seite. Zum Messen wurde der japanische Vertrag 10- und 100-mal wiederholt und nur die letzte Kopie bearbeitet, auf einem M1-Mac mit Python 3.12:
| Tokens | autojunk=False | autojunk=True | Klausel für Klausel |
|---|---|---|---|
| 2,550 | 12 ms | 3 ms | 1 ms |
| 25,500 | 1,142–1,564 ms | 163–209 ms | 7–10 ms |
Die Werte für 25,500 Tokens sind die Spanne aus drei Läufen; gleichzeitig lasteten andere Jobs die CPU aus, und zwei frühere Läufe unter höherer Last brauchten ohne autojunk bis zu 4.2 Sekunden.
Die letzte Spalte ist die Lösung. Verträge sind ohnehin in nummerierte Klauseln gegliedert, also teilt man beide Texte an den Klauselüberschriften auf, ordnet die Klauseln mit einem einzigen SequenceMatcher über die Klauselliste einander zu (identische Klauseln passen als ganze Elemente, das kostet kaum etwas) und lässt den Token-Diff nur innerhalb der Paare laufen, die sich unterscheiden. So bleibt autojunk=False erhalten, und es ist trotzdem die schnellste der drei Varianten. In measure.py erfolgt die Aufteilung beim japanischen Text per Regex auf 第N条; für Englisch würde ein Muster auf Zeilen wie „3. Payment“ dasselbe leisten.
Wo das an seine Grenzen kommt
Alles oben liest die Textebene. Ein eingescannter Vertrag hat keine und braucht zuerst OCR, danach tauchen OCR-Fehler als Änderungen auf. Tabellen, die in falscher Lesereihenfolge extrahiert werden, erzeugen verrauschte Diffs. Und eine Klausel, die verschoben statt bearbeitet wurde, erscheint als eine Löschung plus eine Einfügung; um Verschiebungen zu erkennen, braucht es einen zweiten Durchgang, der gelöschte und eingefügte Blöcke miteinander abgleicht.
Die Skripte (contract_diff.py, measure.py und die Generatoren für die Testdateien) laufen mit uvx --with pymupdf python. Der PDF Editor mit denselben Schritten zum Vergleichen, Markieren als Kommentare und Erstellen eines Berichts gehört zur kostenlosen Desktop-App auf der Download-Seite von osFoundry und läuft wie der Rest der Local-first-Plattform von osFoundry auf deinem eigenen Rechner.
Top comments (0)