「diff オンライン」のツールに業務テキストを貼るのが怖くて、ブラウザ完結のdiffツールを自作した話

契約書の改訂版を旧版と見比べる作業があって、「diff オンライン」で検索して出てきたツールに貼りかけて、手が止まった。このテキスト、どこに行くんだ？

ページのどこを見ても「入力はサーバーに送信されません」とも「送信されます」とも書いていない。DevToolsのNetworkタブを開いて比較ボタンを押せば確認はできるが、毎回それをやるのも馬鹿らしいし、そもそも業務の機密テキストを「たぶん大丈夫」で外部サイトに貼るのは筋が悪い。ローカルならgit diff --no-indexで済む話だが、契約書のような「ファイルにすらなっていない、メール本文からコピーした2つのテキスト」を比べたい場面は意外と多い。

だったら、処理が100%ブラウザ内で完結するdiffツールを自分のサイトに置けばいい。そう思って作ったのがテキスト差分比較ツールだ。差分計算も表示もすべてクライアントサイドのJavaScriptで、fetchの類いは一切ない。この記事は、その実装でMyers差分アルゴリズムを自前で書いてわかったことの記録。

diffライブラリを使わず自前実装にした理由

npmにはdiffやfast-diffのような定番ライブラリがある。普通のプロダクトならそれを使えばいい。ただ今回は静的サイト（Astro）のツールページ1枚で、依存を増やしたくなかったのと、毎日git diffを眺めているくせに中身のアルゴリズムを説明できない自分に気づいてしまったのが大きい。gitが使っているのはMyers法（のバリエーション）で、論文は1986年の “An O(ND) Difference Algorithm” 。これを行単位diffに使えるように自分で書いた。

書いてみると、コア部分は驚くほど短い。編集距離dを0から増やしながら、各対角線k上で「どこまで一致をたどれるか」を貪欲に伸ばしていくだけ。実装の本体は50行程度に収まった。

わかったこと1: MyersはLCSを「逆側から」解いている

実装前は「diff = LCS（最長共通部分列）を求めて、共通部分以外を差分にする」と雑に理解していた。教科書どおりにLCSをDPで解くと表がO(NM)、10,000行同士なら1億セルでメモリ的に厳しい。

Myers法が賢いのは、LCSの長さを直接求めるのではなく、編集距離D（削除＋追加の最小数）を小さい方から探索するところだ。LCSの長さをLとすると D = N + M − 2L という関係があるので、両者は同じ問題の裏表になっている。そして実務のdiffでは「2つのテキストはほぼ同じ」、つまりDが小さいケースが圧倒的に多い。そこに計算量O((N+M)D)がぴったりはまる。似たテキスト同士ほど速く終わる、という性質が実利用の分布と一致しているのが、gitがこの系統を採用している理由なんだと、書いてみて腑に落ちた。

さらに定番の高速化として、Myersに渡す前に共通の先頭・末尾を刈り取る前処理を入れた。ファイルの一部だけ直した場合、比較対象が変更周辺だけに縮むので、体感でこれが一番効く。

わかったこと2: 計算量はDで爆発する。フォールバックは必須

O((N+M)D)は、裏を返すと「2つのテキストが全然違うとき」に牙をむく。Dが最大N+Mまで育つと実質O((N+M)²)で、まったく別の文書を2つ貼られたらタブが固まる。自分しか使わないスクリプトなら「そういう使い方をしない」で済むが、公開ツールでは何を貼られるかわからない。

なので上限を切った。行diffの編集距離が2,000を超えたら探索を打ち切り、その範囲を「全削除＋全追加」として表示するフォールバックに落とす。厳密には最適でない差分になるが、そもそも2,000行分も食い違っている領域に「賢い対応付け」を出したところで人間は読めない。正確さを捨てて止まらないことを取る判断で、ステータス欄に「差分が非常に大きいため一部を全削除+全追加として表示しています」と正直に出すようにした。行数自体にも上限を置いて、片方20,000行超は最初から中断する。

アルゴリズムの実装よりも、この「打ち切りの設計」の方に時間を使った気がする。理論上のワーストケースを実際に貼れてしまうのが公開ツールで、gitのdiffにも同種のヒューリスティック（diff.algorithmや打ち切り）が入っている理由を身をもって理解した。

わかったこと3: 行単位diffだけでは実用にならない。文字単位の2段構え

行単位のdiffだけだと、「1行の中の1文字だけ変わった」場合に旧行が丸ごと赤、新行が丸ごと緑で塗られる。契約書の「甲は乙に対し」→「甲は乙および丙に対し」みたいな変更で、どこが変わったか結局目視で探すことになり、ツールの意味が半減する。

そこで、行diffで「削除と追加が隣接しているブロック」を変更ペアとみなし、そのペアに対して同じMyers実装を今度は文字の配列で回す2段構えにした。GitHubのPR画面で変更行の中の変わった部分だけ濃くハイライトされる、あの表示と同じ構造だ。同じ関数を行にも文字にも使い回せるのは、比較対象を「キーの配列」に抽象化しておいたおかげで、ここは設計が素直にはまって気持ちよかった。

ただし文字diffにも同じ爆発問題があるので、編集距離400・行長500文字で打ち切る。長すぎる行や別物の行ペアは、行全体の色分けだけにフォールバックする。結局どの層にも「諦めライン」が要る。

わかったこと4: 一番使うのは「空白無視」だった

作る前は、目玉はMyersの文字ハイライトだと思っていた。公開して自分で使ってみると、実際に一番手が伸びるのは「行頭行末の空白を無視」のチェックボックスだった。

理由は単純で、比較したいテキストの差分の大半が「インデントだけ変わった」「コピー元の都合で末尾に空白がついた」だからだ。整形ツールを通した後のコード、メールからコピーした文章、この手のノイズを無視しないと本質的な変更が埋もれる。git diff -wを普段使っている人なら当たり前の感覚なのに、自分で作るまで優先度を見誤っていた。同じ理由で「空行を無視」「大文字小文字を無視」も付けて、オプションを切り替えたら自動で再比較が走るようにしてある。差分を見ながらノイズを消していく使い方が一番しっくりくる。

もうひとつ、gitユーザー向けに「unified形式でコピー」も付けた。@@ -1,5 +1,6 @@のハンクヘッダ付きで差分をテキスト化するやつで、SlackやIssueに差分を貼るときにそのまま使える。ハンクの前後3行のコンテキストをまとめる処理は、地味だがgit diffの出力を長年読んできた目には省略できなかった。

「送信しない」は実装で保証するのが一番早い

出来上がったテキスト差分比較ツールは、行単位Myers＋文字単位ハイライト＋無視オプション3種＋unifiedコピーという構成で、入力の自動保存もlocalStorageのみ。ネットワークに何も出ていないことは、静的ページなのでソースを見れば誰でも確認できる。冒頭の「このテキスト、どこに行くんだ？」への一番確実な答えは、送信する経路をそもそも実装しないことだった。

JSONの差分を見たいときは、先にJSON整形ツールでキー順や改行を揃えてから貼ると、構造の変更だけが浮き上がって見やすい。日々のバージョン管理の中でのdiffの読み方・使い方はGitワークフローの記事にまとめているので、そちらもどうぞ。

Myersの自前実装は、正直ライブラリを入れれば1時間で終わる仕事を数日がかりにした。それでも、毎日見ているgit diffの裏側で何が起きているか、どこで理論が現実（巨大入力・別物テキスト・空白ノイズ）に譲歩しているかを手で理解できたのは、ツール1本分より価値があったと思っている。