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文字の 'い' が差分となっています。