Come confrontare parola per parola due versioni di un contratto PDF in Python

Un PDF non ha il rilevamento delle modifiche. Quando un contratto torna indietro in PDF "con qualche piccola modifica", l'unica traccia di cosa è cambiato è la differenza tra due file. Ci sono tre modi ovvi per calcolarla: confrontare le pagine renderizzate pixel per pixel, confrontare il testo estratto riga per riga, oppure confrontarlo parola per parola. Sulla stessa coppia di file danno risposte molto diverse, e solo uno dei tre regge quando l'elaboratore di testi della controparte reimpagina il testo.

Qui sotto trovi le misure di tutti e tre su una coppia reale di PDF e poi un confronto a livello di parola in circa 120 righe di Python (PyMuPDF più difflib della libreria standard) che ricava i riquadri di ogni parola modificata e riscrive le modifiche nel PDF come commenti. Il PDF Editor dell'app desktop di osFoundry funziona allo stesso modo: la sua finestra Confronta file spiega che "il testo viene confrontato parola per parola e le differenze vengono mostrate sul file nuovo", e su questa coppia segnala le stesse cinque modifiche dello script qui sotto.

La coppia di test

I file sono un contratto di servizi di design di una pagina, inventato (Example), generato con PyMuPDF in modo che il livello di testo sia reale. La versione che torna indietro contiene cinque modifiche:

Clausola	Inviato	Tornato indietro
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.

Per simulare il software della controparte che ricompone il testo, un terzo file contiene esattamente le stesse parole della versione restituita, ricomposte a 12 pt in una colonna da 300 pt invece che a 11.5 pt in 468 pt. Stesso testo, a capo diversi.

Pixel, righe o parole

Il diff dei pixel renderizza la prima pagina di entrambi i file a 72 dpi in scala di grigi e conta le righe in cui almeno un pixel differisce di più di 40 livelli; una "fascia" è una sequenza continua di queste righe. Il diff per righe applica difflib.SequenceMatcher all'output di page.get_text() diviso sugli a capo. Il diff per parole è lo script più sotto.

File nuovo	Diff dei pixel	Diff per righe	Diff per parole
Così come è tornato	30 righe su 792, 3 fasce	3 blocchi, 3 righe	5 modifiche
Stesse parole, ricomposto	284 righe su 792, 20 fasce	6 blocchi, 9 righe	5 modifiche

Sul file così come è tornato, il diff dei pixel trova tre zone e quello per righe tre righe. Hanno ragione entrambi, ma nessuno dei due dice cosa è cambiato: il diff per righe segnala la clausola 3 come una riga sostituita, e "30" contro "60" devi comunque scovarlo tu. Sulla copia ricomposta, il diff dei pixel accende 20 fasce separate su quasi tutto il testo, e quello per righe raddoppia a 9 righe toccate perché gli a capo si sono spostati. Il diff per parole dà le stesse cinque modifiche su entrambi i file, perché spazi e a capo non gli arrivano mai.

Estrarre i caratteri con i loro riquadri

Per trovare le modifiche basta la semplice stringa di get_text(), ma per riportarle sulla pagina servono le coordinate. get_text("rawdict") restituisce ogni carattere con il suo riquadro di delimitazione. La funzione qui sotto lo appiattisce in un'unica lista in ordine di lettura:

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

Due dettagli contano. sort=True ordena i blocchi dall'alto in basso e da sinistra a destra, che è proprio quello che serve per un contratto a colonna singola (i layout a due colonne hanno bisogno di un ordinamento a parte). NFKC unifica i caratteri che si somigliano, quindi un "６０" a larghezza piena scritto da una parte e un "60" dall'altra non risultano come modifica. Ogni carattere normalizzato mantiene il riquadro del carattere da cui deriva, così la lista resta allineata alla pagina.

Token: parole, e un carattere alla volta dove non ci sono spazi

Il diff lavora sui token, non sui caratteri. Qui un token è una sequenza di lettere latine e cifre, oppure qualsiasi altro singolo carattere visibile:

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)]

Per l'inglese questo produce parole, con il punto finale staccato in modo che "days." e "days" combacino comunque. I numeri restano interi, quindi una modifica appare come "30" → "60" e non come "3" → "6".

La parte "qualsiasi altro singolo carattere" serve per le lingue che non separano le parole con spazi. Se dividi sugli spazi una versione giapponese dello stesso contratto, che è quello che fa get_text("words") di PyMuPDF, ottieni una "parola" per frase, e il diff segnala tre frasi intere come sostituite. Con un token per carattere trova le modifiche al loro interno, ma in 8 frammenti, perché caratteri condivisi come の spezzano una stessa modifica in più pezzi ("2" eliminato, "まで" → "数", "制限なく" inserito). Unendo le modifiche separate al massimo da un carattere invariato si scende a 5, le stesse cinque modifiche del file inglese. In inglese l'unione non scatta mai, perché lo spazio più corto tra due modifiche ("once") è di quattro caratteri.

Il 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

Il ciclo di scorrimento gestisce una stranezza comune a tutti gli algoritmi di diff. La frase eliminata sta tra "days" e "4. Revisions", e il testo intorno è ". Late payments add a 2% fee each month." da una parte e "." dall'altra. Eliminare ". Late … month" ed eliminare "Late … month." sono soluzioni ugualmente minime, e SequenceMatcher ha scelto la prima. Far scorrere una pura eliminazione o inserzione lungo i token ripetuti finché non termina su un segno di punteggiatura dà la versione che segnerebbe una persona.

autojunk=False è voluto; ci torniamo più sotto. Eseguito sui due file, lo script completo (contract_diff.py) stampa:

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'

ed esattamente le stesse cinque righe sulla copia ricomposta.

Riscrivere le modifiche come commenti

Ogni token porta con sé i riquadri dei suoi caratteri, quindi segnare una modifica sul file nuovo significa aggiungere un'annotazione di evidenziazione su quei riquadri, uniti per riga, con il testo vecchio e quello nuovo come commento. Un'eliminazione non lascia niente da evidenziare, quindi riceve un'icona nota subito dopo il testo che la precedeva:

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)

Sono annotazioni PDF standard, quindi qualsiasi normale visualizzatore PDF le mostra, e chi ti ha mandato le modifiche vede esattamente a cosa si riferisce la tua domanda.

Contratti lunghi: autojunk e clausola per clausola

SequenceMatcher ha un'euristica chiamata autojunk: quando la seconda sequenza ha 200 o più elementi, qualsiasi elemento che ne costituisce più dell'1% viene ignorato come punto di ancoraggio. È pensata per cose come le righe vuote nel codice sorgente. Nel testo di un contratto i token frequenti sono parole come "the" o, in giapponese, の e 甲 (il nome che il contratto dà a una delle parti). Sul file giapponese di una pagina (238 token nella versione nuova) ha messo da parte 18 caratteri diversi, tra cui 甲, 乙, の e 。, e il risultato è passato da 8 blocchi a 6. In quel caso non peggiore, ma diverso, e non è una cosa da lasciare a un'euristica in un documento che stai per firmare.

Disattivarla ha un costo. Nel caso peggiore il diff è grosso modo quadratico, e un contratto di 40 pagine è molto più lungo di una pagina. Per misurarlo, il contratto giapponese è stato ripetuto 10 e 100 volte modificando solo l'ultima copia, su un Mac M1 con Python 3.12:

Token	autojunk=False	autojunk=True	Clausola per clausola
2,550	12 ms	3 ms	1 ms
25,500	1,142–1,564 ms	163–209 ms	7–10 ms

I valori per 25,500 token sono l'intervallo su tre esecuzioni; nel frattempo altri processi stavano usando la CPU, e due esecuzioni precedenti con un carico più pesante hanno impiegato fino a 4.2 secondi senza autojunk.

L'ultima colonna è la soluzione. I contratti sono già divisi in clausole numerate, quindi spezza entrambi i testi sui titoli delle clausole, allinea le clausole con un solo SequenceMatcher sulla lista di clausole (quelle identiche combaciano come elementi interi, a costo bassissimo) ed esegui il diff dei token solo dentro le coppie che differiscono. Così tieni autojunk=False e resta comunque la più veloce delle tre. In measure.py la suddivisione è una regex su 第N条 per il testo giapponese; per l'inglese, un pattern su righe come "3. Payment" farebbe lo stesso lavoro.

Dove smette di funzionare

Tutto quanto sopra legge il livello di testo. Un contratto scansionato non ce l'ha e richiede prima l'OCR, dopodiché gli errori dell'OCR compaiono come modifiche. Le tabelle estratte nell'ordine di lettura sbagliato producono diff pieni di rumore. E una clausola spostata anziché modificata risulta come un'eliminazione più un'inserzione; per riconoscere gli spostamenti serve un secondo passaggio che metta a confronto tra loro i blocchi eliminati e quelli inseriti.

Gli script (contract_diff.py, measure.py e i generatori dei file di test) si eseguono con uvx --with pymupdf python. Il PDF Editor con gli stessi passaggi di confronto, marcatura come commenti e report fa parte dell'app desktop gratuita disponibile nella pagina di download di osFoundry, e gira sulla tua macchina come il resto della piattaforma local-first di osFoundry.