仕組み¶
kogo のエンジンは kogo.engine(src/kogo/engine/)にあり、関心ごとに分割されています:
words(抽出)、alignment(ページ対応付け)、text_diff(テキスト比較)、
visual_diff(図・レイアウト)、annotations、render(マーカーの焼き込み)、
compare(全体の制御)。このページではモジュール一覧ではなく、アルゴリズム自体を説明します。
単語抽出と読み順¶
テキストは単語単位(CJK — 中国語・日本語・韓国語 — は文字単位。CJK拡張漢字B〜J領域の まれな漢字も含む)で抽出され、PDF内部の生のコンテンツストリーム順をそのまま信用するのではなく、 再帰的な空白分割によって読み順に再構築されます。これにより、段組みのページやスライド形式の テキストボックスが、無関係な列を1つの差分に混在させることなく、正しく比較されます。
ページ対応付け¶
2つの文書間のページは、類似度に基づく系列アラインメント(alignment.py の align_pages)
によって対応付けられます — 旧ファイルのページNが新ファイルのページNに対応すると
仮定するのではなく、ページに対する動的計画法による編集距離を使います。これにより、
ページの挿入や削除があっても、残りの比較全体が同期を失いません。
ページの類似度は2つの指標を組み合わせています:
- テキストシグネチャの類似度 — 単語トークンのCounterベースの重なり (CJKの連続部分は3文字のシングル、欧文は単語単位トークン)
- 視覚シグネチャの類似度 — ページを縮小したグレースケールの「インク」サムネイル に対するコサイン類似度。どちらかのページに抽出可能なテキストがほとんどない場合 (画像中心のページやスキャンページ)、テキストシグネチャだけでは信頼できないため使用
対応付けには、各文書内で相対的に近い位置にあるページ同士を優先するわずかな位置ボーナスも 含まれており、これが繰り返しページやほぼ同一のページの判別に役立ちます。
テキスト差分¶
文書全体に対して一度だけ difflib を実行するのではなく、テキストの差分は
(text_diff.py にて)3段階で検出されます:
- 完全一致行のマッチング — バイト単位で完全に一致するテキスト行を、 ページや位置に関わらず最初にマッチさせます。これにより、変更されていない列や スライドのテキストボックス、テーブルのセルが、改訂間で抽出順が変わっただけで 削除・追加のペアとして扱われるのを防ぎます。
- 対応付けられたページ内での読み順差分 — 残りのテキストは、対応付けられた
各ページのペア内で
difflib.SequenceMatcher(CJKテキストにとって重要なautojunk=False)を使って比較されます。 - 文書全体でのリフローパス — それでもマッチしなかったテキストはページ境界を またいで比較され、改訂によって別のページへ移動した段落を検出します。
非常に大きく、内容がほぼ無関係な文書の場合、_document_text_differences は
文書全体を1回で SequenceMatcher にかけるのではなく、ページごとの比較に
フォールバックします。autojunk=False を指定した SequenceMatcher は最悪計算量が
2乗のオーダーになるためです。このフォールバックが使われたかどうかは
result["settings"]["large_document_fallback"] に記録されます。
太字・斜体・文字サイズなどのスタイルのみの変更(テキスト自体は変更・移動していないもの)も 完全一致行のマッチング時に検出され、追加・削除されたテキストとは別に報告されます。
視覚差分¶
図・数式などのテキスト以外のレイアウトは、対応付けられた各ページのペアを画像として
描画し、テキスト差分で既にカバーされた領域をマスクした上で、残った部分の画素差分を
取ることで比較されます(visual_diff.py)。画像だけのページ(スキャンや書き出し)は、
画素差分の前に平行移動による位置合わせを行い、スキャンや書き出しによるズレを補正します。
そのため、数ピクセルずれているだけのページが「変更あり」と誤検出されません。
レンダリングは、PDFが宣言するページサイズに関わらず、一定のピクセル予算内に
制限されており、悪意のある入力に対してもメモリ使用量を抑えます。
注釈¶
既存のPDF注釈(ハイライト・コメント・手書き)は、種類・正規化された位置・色・
不透明度・境界線・内容によってフィンガープリント化され(annotations.py)、
テキスト差分・視覚差分とは独立に、フィンガープリントの集合差分によって比較されます。
出力¶
検出されたすべての差分は、PDF注釈として残すのではなく、出力PDFのページ内容へ
直接焼き込まれます(render.py)。これにより、初期設定で注釈を非表示にする
ビューアや印刷時であっても、マーカーが常に見える状態を保てます。