diff（差分）は、2 つのテキストを見比べて「何が追加され、何が削除されたか」を示す仕組みです。Git のコミット、コードレビュー、文章の校正など、私たちは毎日のように差分を見ています。その裏側で多くの実装が使っているのが 最長共通部分列（LCS） という考え方です。本記事では、diff の正体である LCS を動的計画法の小さな例で具体的に追い、そこから追加・削除を導く方法までを正確に整理します。
O(mn) の表として計算できます。
1. diff とは — 行単位・文字単位の差分
diff は、変更前（旧）と変更後（新）の 2 つのテキストを比較し、その違いを追加・削除（・変更なし）として表すものです。「処理」を指すこともあれば、その「出力結果」を指すこともあります。
比較の最小単位には主に 2 種類があります。
- 行単位 diff：1 行をひとつの要素として扱います。ソースコードや設定ファイルのように行が意味を持つテキストに向き、Git の差分表示はこれが基本です。
- 文字単位 diff：1 文字を要素として扱います。1 行の中の細かな修正や、改行の少ない文章での語句の差を見るのに向きます。
どちらの場合も、根っこにあるのは「2 つの列のうち、共通して残せる部分はどこか」という問いです。共通部分を最大化すれば、変更として表示すべき箇所が最小限になり、人にとって読みやすい差分になります。この「共通して残せる最長の部分」を求めるのが、次に述べる LCS です。
2. 最長共通部分列（LCS）の考え方
LCS（Longest Common Subsequence＝最長共通部分列）とは、2 つの列の両方に、同じ順序で現れる要素を選んだときに最長になる並びのことです。重要なのは「連続でなくてよい」点です。
- 部分文字列（substring）：連続している必要がある（例：
ABCBDABのBCB）。 - 部分列（subsequence）：順序さえ保てば間を飛ばしてよい（例：
ABCBDABからBCABを選べる）。
diff では、テキストを「要素（行や文字）の列」とみなし、その LCS を「両方に共通して残せる最大の骨組み」として使います。たとえば 2 つの行の並びの LCS が長いほど、共通して動かさずに済む行が多く、差分は小さくなります。
3. 動的計画法による LCS の求め方
LCS は動的計画法（DP）で求められます。長さ m と n の 2 つの列について、(m+1)×(n+1) の表 L を作り、L[i][j] を「1 つ目の先頭 i 要素と 2 つ目の先頭 j 要素の LCS の長さ」と定義します。漸化式は次のとおりです。
- 末尾の要素が等しいとき：
L[i][j] = L[i-1][j-1] + 1 - 等しくないとき：
L[i][j] = max(L[i-1][j], L[i][j-1]) - どちらかが空（
i=0またはj=0）のとき：L[i][j] = 0
小さな例で確かめましょう。文字列 X = ABCBDAB（長さ 7）と Y = BDCAB（長さ 5）の LCS を求めます。上の漸化式で表を埋めると、右下の L[7][5] が LCS の長さになります。
| ∅ | B | D | C | A | B | |
|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 4 |
右下の値は 4。すなわち ABCBDAB と BDCAB の LCS の長さは 4 です。実際の並びとしては BCAB や BDAB が該当します（どちらも両方の文字列に同じ順序で現れます）。計算量は表の大きさそのもので O(mn)、メモリも素朴な実装では O(mn) です。
4. LCS から追加・削除を導く
LCS の長さを求めた表からは、経路をたどり直す（バックトラック）ことで実際の差分を構成できます。右下のセルから出発し、次のルールで左上方向へ戻ります。
- 現在のセルで末尾の要素が等しいなら、それは LCS の一部（＝変更なし）。左上
(i-1, j-1)へ進む。 - 等しくないなら、
L[i-1][j]とL[i][j-1]の大きい方へ進む。上へ進むなら X 側の要素は削除、左へ進むなら Y 側の要素は追加。 - 表の端（
i=0またはj=0）に着いたら終了。たどった順序を逆にすると差分の並びになる。
言い換えると、LCS に含まれる要素＝両方に残る「変更なし」、X 側にしかない要素＝削除、Y 側にしかない要素＝追加です。次の小例で対応を示します。
| 旧（X） | 新（Y） | 差分の記号 |
|---|---|---|
| apple | apple | （変更なし） |
| banana | — | - 削除 |
| — | blueberry | + 追加 |
| cherry | cherry | （変更なし） |
ここで apple と cherry が LCS（共通して残る行）にあたり、banana は旧にしかないので削除、blueberry は新にしかないので追加になります。これが - / + でおなじみの diff 表示の正体です。
5. 行単位 diff と Myers アルゴリズム
素朴な LCS の DP は O(mn) の時間とメモリを使います。行数が数千・数万に及ぶファイルでは、これは重くなりがちです。そこで実用の diff では、差分の大きさ（編集距離）が小さいときに高速なアルゴリズムが好まれます。
代表が Myers のアルゴリズムです。これは「最短の編集スクリプト（追加・削除の最小回数）」を求める問題を、編集グラフ上の最短経路探索として解きます。差分の量を D（追加＋削除の数）とすると、おおよそ O((m+n)·D) 程度で動き、変更が少ない場合にとても速いのが特長です。Git をはじめ多くのツールが、この系統のアルゴリズムを行単位 diff の既定として採用しています。
6. 用途 — バージョン管理・コードレビュー・文章校正
diff は、ソフトウェア開発から日々の文章作成まで幅広く使われています。
- バージョン管理：Git などは、ファイルの変更を行単位の diff として記録・表示します。差分だけを保存・転送できるため、履歴の管理や共同作業が効率化されます。
- コードレビュー：プルリクエストの画面で「どの行が追加・削除されたか」を一目で確認できます。レビュアーは変更点だけに集中でき、見落としを減らせます。
- 文章校正・推敲：改訂前後の原稿を比べ、加筆・削除・差し替えを把握します。文字単位 diff を併用すると、1 文の中の語句の変化まで追えます。
- 設定・データの差分確認：デプロイ前後の設定ファイルや、生成物の比較にも使えます。意図しない変更の検出に役立ちます。
いずれの場面でも、根っこにあるのは「共通して残せる部分を最大化し、変わった所だけを浮かび上がらせる」という LCS の発想です。仕組みを知っておくと、diff の表示が思った通りにならないときの理由（LCS の選び方の自由度や、行単位／文字単位の違い）も腑に落ちます。
Free Tool テキスト差分ツールで実際に比べる 2 つのテキストを貼り付けるだけで、追加・削除をその場でハイライト表示します。ブラウザ内で完結し、入力は外部に送信されません。よくある質問（FAQ）
diff（差分）とは何ですか？
diff は 2 つのテキストを比較し、「何が追加され、何が削除されたか」を示す処理や、その出力結果のことです。多くの実装は最長共通部分列（LCS）を求め、両者に共通して残る部分を基準に、片方にしかない行・文字を削除、もう片方にしかない行・文字を追加として表します。バージョン管理やコードレビューで日常的に使われています。
LCS（最長共通部分列）とは何ですか？
LCS（Longest Common Subsequence）は、2 つの列の両方に同じ順序で現れる要素を、連続でなくてもよい形で選んだときに最長になる並びのことです。連続性を要求する部分文字列とは異なり、間を飛ばして選べます。動的計画法を使うと長さ m と n の列に対して O(mn) の表で求められ、diff はこの LCS を共通部分の土台にして差分を構成します。
行単位 diff と文字単位 diff はどう違いますか？
比較の最小単位が異なります。行単位 diff は 1 行をひとつの要素として扱い、ソースコードや設定ファイルのように行が意味を持つテキストに向きます。文字単位 diff は 1 文字を要素として扱い、1 行内の細かな変更や、改行の少ない文章での語句の差を見るのに向きます。多くのツールはまず行単位で比較し、変更された行の中だけを文字単位で強調する、という二段構えを取ります。