python で２つの PDF のテキストの差分を検出する方法のメモ。
「JavaScript で２つの PDF のテキストの差分を検出」の python 版ですが、処理速度の改善を行ってみました。

やりたいこと

2つの PDF ファイルでテキスト要素単位で差分を検出（※文字単位ではない）
ページが異なってもテキスト要素が同じ文字列であれば差分とみなさない
編集距離の計算範囲を制御

プログラム

PDF の解析には PyMuPDF を使用しています。

diff() で差分検出を行いますが、パラメータに指定した値のテキスト要素数の範囲でマッチング処理を行うため、同じテキストでも範囲外のものはマッチング処理の対象外差分として扱います。

差分検出プログラム本体

pdf_text_matcher.py

import re
import fitz


class PdfTextMatcher:
    def __init__(self, pdf1, pdf2):
        self.pdf1 = pdf1
        self.pdf2 = pdf2

        self.re_strip = re.compile(r'(?:^\s+|\s+$)', flags=re.MULTILINE)
        self.text_objs1 = self.get_text_objs(pdf1)
        self.text_objs2 = self.get_text_objs(pdf2)

        self.matches = {}
        self.unmatches1 = []
        self.unmatches2 = []


    def get_text_objs_from_page(self, pdf, page_id):
        page = pdf[page_id]
        blocks = page.get_text('blocks')

        text_objs = []
        for i, obj in enumerate(blocks):
            text = obj[4]
            text = self.re_strip.sub('', text)
            if text == '': continue

            id = f"id_{page_id}_{i}"
            text_obj = {'id': id, 'page': page_id, 'text': text, 'obj': obj}
            text_objs.append(text_obj)

        return text_objs


    def get_text_objs(self, pdf):
        num_pages = pdf.page_count
        text_objs = []

        for p in range(0, num_pages):
            page_text_objs = self.get_text_objs_from_page(pdf, p)
            text_objs.extend(page_text_objs)

        return text_objs


    def match_list(self, obj):
        objs = []

        while True:
            if obj is None:
                break

            #if type(obj) == tuple:
            objs.append(obj[1])
            obj = obj[0]

        objs.reverse()
        return objs


    def diff(self, max_range=100):
        text_objs1 = self.text_objs1
        len1 = len(text_objs1)

        text_objs2 = self.text_objs2
        len2 = len(text_objs2)

        delta_len = len2 - len1

        #    _ a b c ...
        #  _ 0 1 2 3
        #  a 1 0 1 2
        #  c 2 1 2 1
        #  ...

        col_prev = [{}] * (len1 + 1)
        col_cur = [{}] * (len1 + 1)

        for r in range(0, len1+1):
            col_prev[r] = { 'cost': r, 'matches': None }

        for c in range(1, len2+1):
            col_cur[0] = { 'cost': c, 'matches': None }

            # 範囲
            if delta_len >= 0:
                min_row = c - delta_len - max_range - 1
                max_row = c + max_range + 1
            else:
                min_row = c - max_range - 1
                max_row = c + (- delta_len) + max_range + 1

            if min_row <= 0: min_row = 1
            if max_row > len1: max_row = len1

            for r in range(min_row, max_row+1):
                # コスト
                # 左上
                cost_lu = col_prev[r-1]['cost'] + 1
                matches_lu = col_prev[r-1]['matches']
                if text_objs1[r-1]['text'] == text_objs2[c-1]['text']:
                    cost_lu = col_prev[r-1]['cost']
                    matches_lu = (matches_lu, (r-1, c-1))

                # 上
                if col_cur[r-1].get('cost') is None: cost_u = None
                else: cost_u = col_cur[r-1]['cost'] + 1

                # 左
                if col_prev[r] is not None and col_prev[r].get('cost') is None:
                    cost_l = None
                else:
                    cost_l = col_prev[r]['cost'] + 1

                # 経路
                if cost_u is not None and (cost_l is None or cost_u <= cost_l) and cost_u <= cost_lu:
                    # 上
                    col_cur[r] = {
                        'cost': cost_u,
                        'matches': col_cur[r-1]['matches'],
                    }
                elif cost_l is not None and (cost_u is None or cost_l <= cost_u) and cost_l <= cost_lu:
                    # 左
                    col_cur[r] = {
                        'cost': cost_l,
                        'matches': col_prev[r]['matches'],
                    }
                else:
                    # 左上
                    col_cur[r] = {
                        'cost': cost_lu,
                        'matches': matches_lu
                    }

            if c < len2:
                tmp = col_prev
                col_prev = col_cur
                col_cur = tmp

        # 結果
        matches = col_cur[len1]['matches']
        match_ids = self.match_list(matches)
        self.matches = [(text_objs1[m[0]], text_objs2[m[1]])
                        for m in match_ids]

        # match
        matches1 = {}
        matches2 = {}
        for m in match_ids:
            obj1 = text_objs1[m[0]]
            obj2 = text_objs2[m[1]]
            matches1[obj1['id']] = obj2
            matches2[obj2['id']] = obj1

        # unmatch
        for obj in text_objs1:
            if matches1.get(obj['id']): continue
            self.unmatches1.append(obj)

        for obj in text_objs2:
            if matches2.get(obj['id']): continue
            self.unmatches2.append(obj)

        return [self.matches, self.unmatches1, self.unmatches2]

呼び出し側のプログラム例

test.py

import time
import sys
import fitz
from pdf_text_matcher import PdfTextMatcher

pdf1 = fitz.open(sys.argv[1])
pdf2 = fitz.open(sys.argv[2])

from_time = time.time()

m = PdfTextMatcher(pdf1, pdf2)
result = m.diff()

to_time = time.time()

print('match', result[0])
print('unmatch1', [[obj['page'], obj['text']] for obj in result[1]])
print('unmatch2', [[obj['page'], obj['text']] for obj in result[2]])

print(f"time: {to_time - from_time}")

実行例

PDF ファイル1

1ページ目

あああああ
いいいいい
ううううう
えええええ
おおおおお
かかかかか
ききききき
くくくくく
けけけけけ
こここここ
さささささ
ししししし

2ページ目

すすすすす
せせせせせ
そそそそそ
たたたたた
ちちちちち
つつつつつ
ててててて
ととととと

PDF ファイル2

1ページ目

あああああ
い
ううううう
え
おおおおお
＃＃＃＃＃
％％％％％
かかかかか
ききききき
くくくくく
けけけけけ

2ページ目

％％％％％
さささささ
ししししし
すすすすす
せせせせせ
そそそそそ
＃＃＃＃＃
％％％％％
たたたたた
ちちちちち
つつつつつ
ててててて

実行結果

※見やすさのため加工しています

match [
  ({'id': 'id_0_2', 'page': 0, 'text': 'あああああ', 'obj': ...},
   {'id': 'id_0_2', 'page': 0, 'text': 'あああああ', 'obj': ...}),
  ({'id': 'id_0_8', 'page': 0, 'text': 'ううううう', 'obj': ...},
   {'id': 'id_0_8', 'page': 0, 'text': 'ううううう', 'obj': ...}),
   ...,
  ({'id': 'id_0_32', 'page': 0, 'text': 'さささささ', 'obj':...},
   {'id': 'id_1_5', 'page': 1, 'text': 'さささささ', 'obj': ...}),
  ({'id': 'id_0_35', 'page': 0, 'text': 'ししししし', 'obj': ...},
   {'id': 'id_1_8', 'page': 1, 'text': 'ししししし', 'obj': ...}), 
   ...,
  ({'id': 'id_1_20', 'page': 1, 'text': 'ててててて', 'obj': ...)},
   {'id': 'id_1_35', 'page': 1, 'text': 'ててててて', 'obj': ...)
]

unmatch1 [[0, 'いいいいい'], [0, 'えええええ'], [0, 'こここここ'], [1, 'ととととと']]

unmatch2 [[0, 'い'], [0, 'え'], [0, '＃＃＃＃＃'], [0, '％％％％％'], [1, '％％％％％'], [1, '＃＃＃＃＃'], [1, '％％％％％']]

'さささささ'、'ししししし' はファイル1とファイル2とでページは異なりますが、マッチしていると判定されています。
また、テキスト要素単位で差分を検出するため、ファイル1の5文字の 'いいいいい' とファイル2の1文字の 'い' が差分となっています。