文章の「差分」はどう計算されているのか。最短の編集を探す問題と、見え方が1通りではない理由
契約書の改訂版を受け取ったとき、前の版との違いを、赤と緑の行で見たことがあるだろう。あの「差分」は、どう決められているのか。差分は、2つの文章の違いを最短の編集の手順として求めたものだ。この記事では、その考え方と、同じ2つの文章でも見え方が1通りに決まらない理由を、自作のプログラムで測って確かめた。
差分は「最短の編集」を探す問題
2つの文章(行の並び)A と B があるとする。A を B にするには、行を削除するか、行を追加するしかない(差分の計算が使う操作は、この2つだけだ)。その回数が最も少ない手順を探す。これが「最短編集スクリプト」だ。
論文(Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations"。Algorithmica 第1巻、251〜266ページ、1986年。確認日:2026年11月10日)は、これが最長共通部分列を探す問題と、裏表の関係にあることを示している。A と B のどちらにも残る行の並びの最長のものが、「変更されない行」になる。長さ N の A、長さ M の B、最長共通部分列の長さ L のとき、最短の編集の数は D = N + M − 2L になる。
論文の例で確かめた。A = abcabba、B = cbabac は、N = 7、M = 6 で、最長共通部分列の長さは 4 だ。D = 7 + 6 − 2×4 = 5(削除3回と、追加2回)になる。自作のプログラムで計算しても、共通部分は 4 文字、編集は 5 回になった。
最短の編集を、どう探すか
Myers の論文は、この問題を「編集グラフ」の最短経路探索として考える。A と B を、格子状の地図に見立てる。左上から右下まで進むとき、右に進むと「A の行を削除」、下に進むと「B の行を追加」、斜めに進むと「同じ行(ただで進める)」になる。削除と追加は1回ずつ数え、斜めは数えない。この数が最も少ない道が、最短の編集だ。
探し方の工夫は、編集の回数 d を 0、1、2…と増やしながら、各対角線の上で最も遠くまで進める点を覚えておくことにある(論文の3節)。違いが小さければ、d が小さいうちに終点に着くので、速い。時間は、N+M と D の積に比例する(O(ND))。論文の要旨も、違いが小さいとき(2つの列が似ているとき)に性能が良いと書いている。
さらに、論文の4b節は、メモリを列の長さに比例する量に抑える方法を示している。前向きと後ろ向きの探索を同時に進めて、途中で重なる場所(中間のスネーク)を見つけ、そこで2つに分けて、それぞれを同じ方法で解く。今回の実装は、この方法による。
手元で測った:違いの大きさで、時間が変わる
このサイトのツールの計算部分(Myers の線形空間版を自前で実装したもの)を、Node で動かして測った。1行は約40文字で、左右とも約1万行だ。
| 入力 | N + M | 編集の数 D | 計算時間 |
|---|---|---|---|
| ほぼ同じ(100行だけ変更) | 20,000 | 200 | 25 ms |
| 200行追加・300行削除 | 19,900 | 500 | 18 ms |
| 完全に別の内容 | 20,000 | 20,000 | 445 ms(※) |
| 行の順番をでたらめに入れ替え | 20,000 | 19,618 | 4,650 ms |
※「完全に別の内容」は、相手側に1つも無い行を先に取り除く前処理があるため、D が最大でも速い。行の順番を入れ替えただけの場合は、同じ行が両方に残るので、この近道が使えず、D が大きいぶん遅かった。違いが小さいほど速く、大きいと遅いという Myers の性質が、そのまま出ている。
同じ2つの文章でも、差分は1通りではない
最短の編集は、1通りに決まるとは限らない。論文の例(A = abcabba、B = cbabac)の、長さ4の共通部分列は、baba・caba・cbba の3通りある。どれを「変更されない」とみなしても、編集の数は同じ5回だ。行の例でも確かめた。1・2・3 を 3・2・1 に変える差分は、2 を共通とみなすと「変更2行」、1 か 3 を共通とみなすと「追加2行・削除2行」になった(どちらも、同じ行は1行で、最短)。ツールによって、同じ文章から違う差分が出るのは、このためだ。
もう1つ、「変更」という操作は、差分のアルゴリズムの中には無い。アルゴリズムが出すのは、削除と追加だけだ。「変更された行」は、同じ場所に並んだ削除と追加を、あとから組み合わせて表示したものにすぎない。このサイトのツールは、同じ場所に並んだ、左の削除された行と、右の追加された行を、順番に組み合わせている。さらに、組み合わせた行どうしに、行の中の文字単位の差分(同じアルゴリズムを、文字の列にかけたもの)をかけて、違う文字に下線を付ける。
見た目は同じなのに、差分が出る
文章を目で見て同じに見えても、バイトが違えば、差分は出る。同じ文章を、設定を変えて比べた結果が次のとおりだ(自作のツールで測定)。
| 左 | 右 | 無視しない | 無視する設定 |
|---|---|---|---|
a b(空白2つ) | a b(空白1つ) | 変更1行 | 「空白の量の違いを無視」で、同じ |
a (前後に空白) | a | 変更1行 | 「前後の空白を無視」で、同じ |
a␍ b␍(CRLF) | a b(LF) | 変更2行 | 「改行コードの違いを無視」で、同じ |
ABC123・カナ | ABC123・カナ | 変更2行 | 「全角・半角の違いを無視」で、同じ |
Hello | hello | 変更1行 | 「大文字小文字の違いを無視」で、同じ |
a b | ab | 変更1行 | 空白の量を無視しても、変更1行 |
ひとつ目と最後の行は、空白の「量」だけを無視するのと、「有無」は無視しないことの違いを示す。全角と半角は、NFKC(Unicode の正規化の一つ)で同じ文字にそろえて比べている。ただし、比べるときにそろえるだけで、画面には元の文字のまま出す(ABC123 と ABC123 を並べて表示した)。末尾の改行の有無(a⏎b⏎ と a⏎b)も、行の中身は同じなので、行の違いには数えず、別に知らせる設計にした。
外に出せない文章を、比べる
契約書や社内の文書は、外のサービスに貼れないことが多い。このサイトのツールは、貼り付けた2つの文章を、ブラウザの中だけで比べる。計算は、ブラウザの裏側(Web Worker)で行うので、計算中も画面は固まらない。実際に、行の順番をでたらめに入れ替えた1万行(約6秒かかる最悪の場合)でも、画面は動き続けた。比べている間に、ファイルや文章を送る通信は増えなかった(自分のサイトのプログラムを読み込むだけだった)。左右それぞれ1万行・1MBを超えると、比べる前に警告が出る。20万行・20MBを超える入力は受け付けない。Word・PDF・Excel のファイルは、直接は比べられない。文章をテキストにして貼り付ける。
測定の条件
- 計算時間は、Windows 11 Pro(10.0.26300)の Node 24 で、
diffTextsをメインスレッドで動かして測った。ブラウザ(Web Worker)では、同じ入力で、ほぼ同じ文章が65 ms、行をでたらめに入れ替えた場合が5.9秒だった(next devでの測定)。 - 論文の例の最長共通部分列は、動的計画法で全部数え上げて確かめた(
baba・caba・cbba)。このツールの実装が選ぶのは、そのうちの1つだ。 - 実装の正しさは、ランダムな入力29,500件で、動的計画法の最長共通部分列の長さと突き合わせて確かめた(不一致0件)。
- 論文の本文は、著者の公開PDFを読んだ。要旨と、2節(編集グラフ)、3節(貪欲なアルゴリズム)、4b節(線形空間の改良)に基づいて書いた。論文が示す、期待される計算時間などの詳細は、ここでは書いていない。
参考
- Eugene W. Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica 1, 251–266(1986):https://link.springer.com/article/10.1007/BF01840446 (書誌情報。DOI 10.1007/BF01840446。2026年11月10日確認)/ 著者の公開PDF:http://www.xmailserver.org/diff2.pdf (2026年11月10日確認)