文章の「差分」はどう計算されているのか。最短の編集を探す問題と、見え方が1通りではない理由

2026-11-10

契約書の改訂版を受け取ったとき、前の版との違いを、赤と緑の行で見たことがあるだろう。あの「差分」は、どう決められているのか。差分は、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,00020025 ms
200行追加・300行削除19,90050018 ms
完全に別の内容20,00020,000445 ms(※)
行の順番をでたらめに入れ替え20,00019,6184,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行「全角・半角の違いを無視」で、同じ
Hellohello変更1行「大文字小文字の違いを無視」で、同じ
a bab変更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日確認)

この記事に対応するツール