Cara membandingkan dua versi kontrak PDF kata per kata dengan Python

PDF tidak punya fitur track changes. Saat kontrak dikirim balik dalam bentuk PDF "dengan sedikit revisi kecil", satu-satunya catatan tentang apa yang berubah adalah selisih antara dua file itu. Ada tiga cara yang paling jelas untuk menghitung selisih tersebut: membandingkan halaman yang sudah dirender piksel demi piksel, membandingkan teks hasil ekstraksi baris demi baris, atau membandingkannya kata demi kata. Pada pasangan file yang sama, hasil ketiganya sangat berbeda, dan hanya satu yang tetap akurat ketika word processor pihak lain menata ulang alur teksnya.

Di bawah ini ada hasil pengukuran ketiga cara itu pada sepasang PDF sungguhan, lalu perbandingan tingkat kata dalam sekitar 120 baris Python (PyMuPDF plus difflib dari standard library) yang mengambil kotak koordinat setiap kata yang berubah dan menuliskan perubahannya kembali ke PDF sebagai komentar. PDF Editor di aplikasi desktop osFoundry bekerja dengan cara yang sama: dialog Compare Files-nya bertuliskan "Text is compared word by word; the differences are shown on the new file", dan pada pasangan file ini ia melaporkan lima perubahan yang sama dengan skrip di bawah.

Pasangan file uji

File-nya adalah perjanjian jasa desain satu halaman yang dibuat-buat (contoh), digenerate dengan PyMuPDF supaya lapisan teksnya asli. Versi yang dikirim balik berisi lima perubahan:

Untuk mensimulasikan software pihak lain yang mengatur ulang teks, file ketiga berisi kata-kata yang persis sama dengan versi yang dikirim balik, tetapi diset ulang pada 12 pt dalam kolom 300 pt, bukan 11.5 pt dalam 468 pt. Teksnya sama, pemenggalan barisnya berbeda.

Piksel, baris, atau kata

Diff piksel merender halaman pertama kedua file pada 72 dpi dalam grayscale dan menghitung baris piksel yang punya setidaknya satu piksel berbeda lebih dari 40 level; sebuah "pita" adalah rangkaian baris seperti itu yang berurutan. Diff baris menjalankan difflib.SequenceMatcher pada page.get_text() yang dipecah per baris baru. Diff kata adalah skrip di bagian bawah.

Pada file yang dikirim balik, diff piksel menemukan tiga area dan diff baris menemukan tiga baris. Keduanya benar, tetapi tidak ada yang memberi tahu apa yang berubah: diff baris melaporkan pasal 3 sebagai satu baris yang diganti, dan Anda masih harus mencari sendiri "30" versus "60". Pada salinan yang diset ulang, diff piksel menyala di 20 pita terpisah di hampir seluruh teks, dan diff baris naik dua kali lipat menjadi 9 baris karena pemenggalan barisnya bergeser. Diff kata memberikan lima perubahan yang sama pada kedua file, karena spasi dan pemenggalan baris tidak pernah sampai ke sana.

Mengambil karakter beserta kotaknya

String get_text() biasa sudah cukup untuk menemukan perubahan, tetapi untuk menuliskannya kembali ke halaman Anda butuh koordinat. get_text("rawdict") memberikan setiap karakter beserta bounding box-nya. Fungsi di bawah meratakannya menjadi satu list sesuai urutan baca:

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 

Ada dua detail penting. sort=True mengurutkan blok dari atas ke bawah, kiri ke kanan, dan itulah yang Anda perlukan untuk kontrak satu kolom (layout dua kolom butuh pengurutan sendiri). NFKC menyatukan karakter yang mirip, jadi "６０" full-width yang diketik di satu sisi dan "60" di sisi lain tidak muncul sebagai perubahan. Setiap karakter hasil normalisasi tetap memakai kotak dari karakter asalnya, sehingga list-nya tetap selaras dengan halaman.

Token: kata, dan satu karakter per token kalau tidak ada spasi

Diff dijalankan pada token, bukan karakter. Token di sini adalah rangkaian huruf Latin dan angka, atau satu karakter terlihat lainnya:

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

Untuk bahasa Inggris, hasilnya adalah kata, dengan titik di akhir dipisahkan supaya "days." dan "days" tetap cocok. Angka tetap utuh, jadi perubahan muncul sebagai "30" → "60", bukan "3" → "6".

Bagian "satu karakter lainnya" itu untuk bahasa yang tidak memakai spasi antarkata. Memecah versi bahasa Jepang dari kontrak yang sama berdasarkan spasi, seperti yang dilakukan get_text("words") milik PyMuPDF, menghasilkan satu "kata" per kalimat, dan diff melaporkan tiga kalimat utuh sebagai diganti. Dengan satu token per karakter, diff menemukan perubahan di dalam kalimat itu, tetapi dalam 8 potongan, karena karakter yang sama di kedua versi seperti の memecah satu perubahan menjadi beberapa bagian ("2" dihapus, "まで" → "数", "制限なく" disisipkan). Menggabungkan perubahan yang hanya dipisahkan paling banyak satu karakter yang tidak berubah menurunkannya menjadi 5, yaitu lima perubahan yang sama dengan file bahasa Inggris. Di bahasa Inggris penggabungan ini tidak pernah terjadi, karena jarak terpendek antara dua perubahan ("once") panjangnya empat karakter.

Diff-nya

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 

Loop geser itu menangani keanehan yang ada di semua algoritma diff. Kalimat yang dihapus terletak di antara "days" dan "4. Revisions", dan teks di sekitarnya adalah ". Late payments add a 2% fee each month." di satu sisi dan "." di sisi lain. Menghapus ". Late … month" dan menghapus "Late … month." sama-sama minimal, dan SequenceMatcher memilih yang pertama. Menggeser penghapusan atau penyisipan murni di sepanjang token yang berulang sampai berakhir di tanda baca menghasilkan versi yang akan ditandai oleh manusia.

autojunk=False memang disengaja; penjelasannya ada di bawah. Saat dijalankan pada dua file itu, skrip lengkapnya (contract_diff.py) mencetak:

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' 

dan lima baris yang persis sama untuk salinan yang diset ulang.

Menuliskan perubahan kembali sebagai komentar

Setiap token membawa kotak dari karakter-karakternya, jadi menandai perubahan di file baru cukup dengan anotasi highlight di atas kotak-kotak itu, digabung per baris, dengan teks lama dan baru sebagai komentarnya. Penghapusan tidak menyisakan apa pun untuk di-highlight, jadi ia mendapat ikon catatan tepat setelah teks yang mendahuluinya:

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) 

Ini adalah anotasi PDF standar, jadi PDF viewer biasa bisa menampilkannya, dan orang yang mengirim revisi itu bisa melihat persis bagian mana yang Anda tanyakan.

Kontrak panjang: autojunk dan per pasal

SequenceMatcher punya heuristik bernama autojunk: kalau urutan kedua berisi 200 elemen atau lebih, elemen apa pun yang jumlahnya lebih dari 1% dari urutan itu diabaikan sebagai titik jangkar pencocokan. Ini dimaksudkan untuk hal seperti baris kosong di source code. Di teks kontrak, token yang sering muncul adalah kata seperti "the" atau, dalam bahasa Jepang, の dan 甲 (sebutan kontrak untuk salah satu pihak). Pada file bahasa Jepang satu halaman (238 token di versi baru), heuristik ini menyingkirkan 18 karakter berbeda, termasuk 甲, 乙, の dan 。, dan hasilnya berubah dari 8 hunk menjadi 6. Dalam kasus itu tidak lebih buruk, tetapi berbeda, dan itu bukan hal yang pantas diserahkan ke heuristik untuk dokumen yang akan Anda tanda tangani.

Mematikannya ada harganya. Diff ini kira-kira kuadratik di kasus terburuk, dan kontrak 40 halaman jauh lebih panjang dari satu halaman. Untuk mengukurnya, kontrak bahasa Jepang diulang 10 dan 100 kali dengan hanya salinan terakhir yang diubah, di Mac M1 dengan Python 3.12:

Angka untuk 25,500 token adalah rentang dari tiga kali jalan; ada proses lain yang memakai CPU pada saat yang sama, dan dua percobaan sebelumnya dengan beban lebih berat memakan waktu hingga 4.2 detik tanpa autojunk.

Kolom terakhir adalah solusinya. Kontrak sudah terbagi dalam pasal-pasal bernomor, jadi pecah kedua teks di judul pasal, sejajarkan pasal-pasalnya dengan satu SequenceMatcher pada daftar pasal (pasal yang identik cocok sebagai satu item utuh, murah), lalu jalankan diff token hanya di dalam pasangan yang berbeda. Cara ini tetap memakai autojunk=False dan tetap yang tercepat dari ketiganya. Di measure.py, pemecahannya berupa regex pada 第N条 untuk teks bahasa Jepang; untuk bahasa Inggris, pola pada baris seperti "3. Payment" bisa melakukan hal yang sama.

Batasannya

Semua cara di atas membaca lapisan teks. Kontrak hasil scan tidak punya lapisan teks dan perlu OCR dulu, setelah itu kesalahan OCR akan muncul sebagai perubahan. Tabel yang diekstrak dengan urutan baca yang salah menghasilkan diff yang berantakan. Dan pasal yang dipindahkan, bukan diedit, akan muncul sebagai satu penghapusan dan satu penyisipan; mendeteksi perpindahan butuh tahap kedua yang mencocokkan blok yang dihapus dengan blok yang disisipkan.

Skrip-skripnya (contract_diff.py, measure.py dan generator untuk file uji) bisa dijalankan dengan uvx --with pymupdf python. PDF Editor dengan langkah compare, tandai sebagai komentar, dan laporan yang sama adalah bagian dari aplikasi desktop gratis di halaman download osFoundry, dan berjalan di komputer Anda sendiri seperti bagian lain dari platform local-first osFoundry.