Un PDF n'a pas de suivi des modifications. Quand un contrat revient en PDF « avec quelques petites retouches », la seule trace de ce qui a changé, c'est la différence entre les deux fichiers. Il y a trois façons évidentes de calculer cette différence : comparer les pages rendues pixel par pixel, comparer le texte extrait ligne par ligne, ou le comparer mot par mot. Sur la même paire de fichiers, elles donnent des réponses très différentes, et une seule résiste au traitement de texte de l'autre partie quand il remet le texte en page.
Voici d'abord les mesures des trois méthodes sur une vraie paire de PDF, puis une comparaison au niveau des mots en environ 120 lignes de Python (PyMuPDF et le module difflib de la bibliothèque standard), qui récupère les boîtes de chaque mot modifié et réécrit les changements dans le PDF sous forme de commentaires. Le PDF Editor de l'application de bureau osFoundry fonctionne de la même manière : sa boîte de dialogue Compare Files indique « Text is compared word by word; the differences are shown on the new file », et sur cette paire il trouve les mêmes cinq changements que le script ci-dessous.
La paire de test
Les fichiers sont un contrat de prestation de design d'une page, inventé pour l'occasion (exemple), généré avec PyMuPDF pour que la couche texte soit réelle. La version renvoyée contient cinq modifications :
| Clause | Envoyé | Revenu |
|---|---|---|
| 3. Paiement | within 30 days. Late payments add a 2% fee each month. | within 60 days. |
| 4. Révisions | two rounds of revisions | unlimited rounds of revisions |
| 5. Propriété | the final logo once the fee is paid in full. | the final logo and all drafts once work begins. |
Pour simuler le logiciel de l'autre partie qui recompose le texte, un troisième fichier reprend exactement les mots de la version renvoyée, recomposés en 12 pt sur une colonne de 300 pt au lieu de 11.5 pt sur 468 pt. Même texte, retours à la ligne différents.
Pixels, lignes ou mots
Le diff de pixels rend les deux premières pages à 72 dpi en niveaux de gris et compte les rangées où au moins un pixel diffère de plus de 40 niveaux ; une « bande » est une suite de rangées de ce type. Le diff de lignes applique difflib.SequenceMatcher au résultat de page.get_text() découpé sur les retours à la ligne. Le diff de mots, c'est le script plus bas.
| Nouveau fichier | Diff de pixels | Diff de lignes | Diff de mots |
|---|---|---|---|
| Tel que renvoyé | 30 rangées sur 792, 3 bandes | 3 blocs, 3 lignes | 5 changements |
| Mêmes mots, recomposés | 284 rangées sur 792, 20 bandes | 6 blocs, 9 lignes | 5 changements |
Sur le fichier tel que renvoyé, le diff de pixels trouve trois zones et le diff de lignes trois lignes. Les deux ont raison, mais aucun ne dit ce qui a changé : le diff de lignes signale la clause 3 comme une ligne remplacée, et c'est encore à vous de repérer « 30 » face à « 60 ». Sur la copie recomposée, le diff de pixels allume 20 bandes séparées sur presque tout le texte, et le diff de lignes double à 9 lignes touchées parce que les retours à la ligne ont bougé. Le diff de mots donne les mêmes cinq changements sur les deux fichiers, parce que les espaces et les retours à la ligne ne l'atteignent jamais.
Extraire les caractères avec leurs boîtes
Une simple chaîne get_text() suffit pour trouver les changements, mais pour les réécrire sur la page il faut des coordonnées. get_text("rawdict") donne chaque caractère avec sa boîte englobante. La fonction ci-dessous aplatit tout ça en une seule liste, dans l'ordre de lecture :
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
Deux détails comptent. sort=True trie les blocs de haut en bas et de gauche à droite, ce qu'on veut pour un contrat sur une seule colonne (une mise en page sur deux colonnes demande son propre ordre). NFKC regroupe les caractères qui se ressemblent, donc un « ６０ » pleine chasse tapé d'un côté et « 60 » de l'autre n'apparaissent pas comme un changement. Chaque caractère normalisé garde la boîte du caractère d'origine, ce qui garde la liste alignée sur la page.
Les tokens : des mots, et un caractère à la fois quand il n'y a pas d'espaces
Le diff travaille sur des tokens, pas sur des caractères. Ici, un token est soit une suite de lettres latines et de chiffres, soit n'importe quel autre caractère visible pris seul :
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)]
En anglais, ça donne des mots, avec le point final détaché pour que « days. » et « days » correspondent quand même. Les nombres restent entiers, donc un changement apparaît comme « 30 » → « 60 » et non « 3 » → « 6 ».
La partie « n'importe quel autre caractère pris seul » sert aux langues qui ne mettent pas d'espaces entre les mots. Découper une version japonaise du même contrat sur les espaces, ce que fait get_text("words") de PyMuPDF, donne un « mot » par phrase, et le diff signale trois phrases entières comme remplacées. Avec un token par caractère, il trouve les modifications à l'intérieur, mais en 8 fragments, parce que des caractères communs comme の découpent une modification en morceaux (« 2 » supprimé, « まで » → « 数 », « 制限なく » inséré). Fusionner les changements séparés par au plus un caractère inchangé ramène ce nombre à 5, les mêmes cinq modifications que dans le fichier anglais. En anglais, la fusion ne se déclenche jamais, puisque le plus petit écart entre deux changements (« once ») fait quatre caractères.
Le 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
La boucle de glissement gère une bizarrerie commune à tous les algorithmes de diff. La phrase supprimée se trouve entre « days » et « 4. Revisions », et le texte autour est « . Late payments add a 2% fee each month. » d'un côté et « . » de l'autre. Supprimer « . Late … month » ou supprimer « Late … month. » est tout aussi minimal, et SequenceMatcher a choisi la première option. Faire glisser une suppression ou une insertion pure le long des tokens répétés jusqu'à ce qu'elle se termine sur une ponctuation donne la version qu'une personne aurait marquée.
autojunk=False est voulu ; on y revient plus bas. Lancé sur les deux fichiers, le script complet (contract_diff.py) affiche :
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'
et exactement les mêmes cinq lignes pour la copie recomposée.
Réécrire les changements sous forme de commentaires
Chaque token porte les boîtes de ses caractères, donc marquer un changement dans le nouveau fichier revient à poser une annotation de surlignage sur ces boîtes, fusionnées par ligne, avec l'ancien et le nouveau texte en commentaire. Une suppression ne laisse rien à surligner : elle reçoit donc une icône de note juste après le texte qui la précédait :
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)
Ce sont des annotations PDF standard, donc les lecteurs PDF ordinaires les affichent, et la personne qui a envoyé les modifications voit exactement sur quoi porte votre question.
Contrats longs : autojunk et clause par clause
SequenceMatcher a une heuristique appelée autojunk : quand la deuxième séquence compte 200 éléments ou plus, tout élément qui représente plus de 1 % de cette séquence est ignoré comme point d'ancrage. C'est prévu pour des choses comme les lignes vides dans du code source. Dans un texte de contrat, les tokens fréquents sont des mots comme « the » ou, en japonais, の et 甲 (le nom que le contrat donne à l'une des parties). Sur le fichier japonais d'une page (238 tokens dans la nouvelle version), elle a écarté 18 caractères différents, dont 甲, 乙, の et 。, et le résultat est passé de 8 blocs à 6. Pas pire dans ce cas, mais différent, et ce n'est pas quelque chose à laisser à une heuristique dans un document que vous allez signer.
La désactiver a un coût. Le diff est à peu près quadratique dans le pire cas, et un contrat de 40 pages est bien plus long qu'une page. Pour le mesurer, le contrat japonais a été répété 10 et 100 fois, avec seulement la dernière copie modifiée, sur un Mac M1 avec Python 3.12 :
| Tokens | autojunk=False | autojunk=True | Clause par clause |
|---|---|---|---|
| 2,550 | 12 ms | 3 ms | 1 ms |
| 25,500 | 1,142–1,564 ms | 163–209 ms | 7–10 ms |
Les chiffres à 25,500 tokens sont la plage sur trois exécutions ; d'autres tâches utilisaient le CPU en même temps, et deux exécutions antérieures sous une charge plus lourde ont pris jusqu'à 4.2 secondes sans autojunk.
La dernière colonne, c'est la solution. Les contrats sont déjà découpés en clauses numérotées : on coupe donc les deux textes aux titres de clause, on aligne les clauses avec un seul SequenceMatcher sur la liste des clauses (les clauses identiques correspondent en bloc, pour pas cher), et on ne lance le diff de tokens qu'à l'intérieur des paires qui diffèrent. On garde autojunk=False et c'est quand même la plus rapide des trois. Dans measure.py, le découpage est une regex sur 第N条 pour le texte japonais ; pour l'anglais, un motif sur les lignes du type « 3. Payment » ferait le même travail.
Les limites
Tout ce qui précède lit la couche texte. Un contrat scanné n'en a pas et demande d'abord un OCR, après quoi les erreurs d'OCR apparaissent comme des changements. Des tableaux extraits dans le mauvais ordre de lecture produisent des diffs bruités. Et une clause déplacée plutôt que modifiée ressort comme une suppression et une insertion ; détecter les déplacements demande une deuxième passe qui fait correspondre les blocs supprimés et insérés entre eux.
Les scripts (contract_diff.py, measure.py et les générateurs des fichiers de test) se lancent avec uvx --with pymupdf python. Le PDF Editor, avec les mêmes étapes de comparaison, de marquage en commentaires et de rapport, fait partie de l'application de bureau gratuite disponible sur la page de téléchargement d'osFoundry, et il tourne sur votre propre machine comme le reste de la plateforme local-first d'osFoundry.
Top comments (0)