大学で習った動的計画法で差分比較ツールを実装する｜LCS + DP の行・文字二段差分
2026-04-29
はじめに
大学の講義で動的計画法（DP）を習ったとき、せっかくなら習いっぱなしにせず実用的なツールに落とし込みたいと思いました。題材を探していて思い当たったのが、自分自身がコードレビューや原稿校正で日常的に使う「差分比較」です。
この記事では、自作の 差分比較ツール を LCS + DP で実装するにあたってやったことや行レベル・文字レベルの二段差分という設計をまとめます。
ブラウザ完結の差分比較ツールを、大学で習った動的計画法（DP）で実装した記録です。LCS（最長共通部分列）は DP の典型問題で、自分の手で書ける手触りのちょうど良さがありました。行レベルでまず差分を取り、changed ペアに対して文字レベルで再差分する二段構えで、実用度も担保しています。
環境
| 項目 | 技術 |
|---|---|
| フレームワーク | Nuxt 4 + Vue 3 |
| 言語 | TypeScript |
| 差分計算 | ブラウザ内（サーバー送信なし） |
| 対象テキスト長 | 数千行程度まで想定 |
なぜLCS + DPを利用する判断をしたか
調査パート
大学で習った内容は、音声認識に関するDPだったので、文字列を対象にしていませんでした。なので、まずどのようなアプローチで文字列比較をDPで行うかという部分を調べる必要がありました。調べたところ、LCSという最長共通部分列を求める問題を解けば良いことがわかりました。
LCS の基本：1行同士で考える
最長共通部分列の具体例を挙げます。まず２つの文字列があるとします。変更前、変更後の順です。
- あああああ
- いあああい
２つの文字列から最長共通部分列を求めると、「あああ」が該当します。
複数行への応用
さらに実用的な例として、複数行の文字列を考えてみます。
- あ\nああ\nああ
- い\nあああい
差分比較では行ごとに対応付けて比較します。対応する行同士で最長共通部分列を求めると、以下のような結果になります。
- 1行目（あ vs い）→ 共通文字なし
- 2行目（ああ vs あああい）→ 「ああ」が共通
- 3行目（ああ vs 対応行なし）→ 文字列2に該当行なし
これでわかることは、1行目は完全に変更されているということ、2行目は「ああ」が変更されていないということ、3行目は削除されたということです。これが文字列差分比較の大まかな仕組みです。
他の差分アルゴリズム
差分計算アルゴリズムには他のものもあり、Myers アルゴリズム（git diff 等で使われる O(ND) 法）など、より洗練された手法が存在するようです。実用面ではそちらの方が強力ですし、世の中の差分ライブラリも豊富です。
今回のユースケースに照らし合わせる
今回のツールが対象とするのは次のような状況に限られます。
- プログラマーがコードレビュー前に数十行〜数百行を見比べたい
- 編集者が原稿の校正で段落単位の変更を確認したい
- 契約書担当者が条文の版ごとの違いを見たい
どれも 1画面におさまる長さ が大半です。この規模なら O(m·n) の計算量でも体感的に一瞬で終わるため、単純なLCS＋DPの実装で問題ないと判断しました。
基本：LCS テーブルと DP
LCS (Longest Common Subsequence) は「2つの列の最長共通部分列」を求める典型的な DP 問題です。
const lcsTable: number[][] = Array(len1 + 1)
.fill(null)
.map(() => Array(len2 + 1).fill(0))
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
if (str1[i - 1] === str2[j - 1]) {
lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1
} else {
lcsTable[i][j] = Math.max(lcsTable[i - 1][j], lcsTable[i][j - 1])
}
}
}
この表が埋まったら、右下から左上へ バックトレース することで「どこが一致で、どこが追加/削除か」の操作列を取り出せます。計算量は O(m·n) ですが、対象サイズが小さいことを制約としているので、十分なはずです。小規模ツールの設計では制約決めが重要だという話はここでも活きてきます。
軽量ツールの制約設計についてはこちら⬇️
二段構成：行レベル → 文字レベル
差分比較ツールの面白いところは、同じ LCS ロジックを二段階で使う 点です。 行単位の差分で大まかに分類し、さらに文字単位で差分を作るという仕組みになります。
第1段：行レベルの差分
まずテキストを \n で分割して行の配列を作り、行同士を要素比較します。等価判定は行文字列の完全一致。findLineDiff がこの役割を担っています。
if (lines1[i - 1] === lines2[j - 1]) {
lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1
} else {
lcsTable[i][j] = Math.max(lcsTable[i - 1][j], lcsTable[i][j - 1])
}
一致しない行は removed / added として扱われます。この時点では「行ごと」の粒度しか分かりません。
第2段："changed" ペアを文字レベルで再差分
行レベルで removed の直後に added が来た場合、「丸ごと別の行に置き換わった」のではなく「少しだけ編集された」可能性が高いです。そこで差分比較ツールでは隣接する removed + added ペアを changed にします。
while (idx < ops.length) {
if (
idx + 1 < ops.length &&
ops[idx].type === 'removed' &&
ops[idx + 1].type === 'added'
) {
merged.push({
type: 'changed',
originalLine: (ops[idx] as { line: string }).line,
modifiedLine: (ops[idx + 1] as { line: string }).line,
})
idx += 2
} else {
merged.push(ops[idx])
idx++
}
}
そして changed な行ペアについては、文字単位の LCS をもう一度かけて、行内のどこが変わったかを細かくハイライトします。これを担うのが buildCharSegments で、実態は findCharacterDiff（先ほど見せたのと同じ LCS + DP）です。
行レベルと文字レベルで まったく同じ関数ひな形を使い回せる のが、この設計の特徴です。
現実的な制限
LCS + DP は O(m·n) メモリを食うので、超長文（数十万文字）に投げると当然重くなります。差分比較ツールでは大容量テキスト向けの Web Worker 対応は未実装で、代わりにユーザー向けマニュアルで分割比較の利用を案内しています。差分計算自体はブラウザ側で同期実行していますが、100KB 程度までなら UI スレッドでも体感上気になりません。
学習目的で書いた単純な実装ですが、当初想定していたユースケースでは十分に動きます。もし将来、もっと大規模なテキストを扱いたくなったら、より洗練された手法に置き換える余地もあります。
まとめ
- 大学で習った 動的計画法を実用ツールに落とし込む題材 として、差分計算は手触りがちょうど良かった
- 行レベル LCS →
changedペアに対して文字レベル LCS、という 二段構成 で精度を稼ぐ - 超長文は対象外、と割り切ってマニュアルで案内するのも立派な設計判断
学んだ手法をまずは素直に実装してみる経験は、後でより洗練された手法を読むときの理解の土台にもなると考えています。
