Rubyで素朴なdiffコマンドを書いてみた（動的計画法）
だいぶ前に書いたものを見て思い出したりしつつ最低限のものを書いてみました。
（他所に書いていたものを引っ越してきました。元の公開日は 2024-02-12 です。）
コード
一番ベーシックな動的計画法のものを書いてみました。より改良された手法もあるようですが本記事では扱いません。
後で自分が見て思い出しやすいように少し冗長に書いています。「理解のためのリファクタリング」を自分なりに行った状態です。
# diff.rb
class Diff
def initialize(xs_a, xs_b)
@xs_a = [nil] + xs_a
@xs_b = [nil] + xs_b
@table = Array.new(@xs_a.size) { Array.new(@xs_b.size) }
end
def no_edit?(ai, bi)
@xs_a[ai] == @xs_b[bi]
end
def edit_distance(ai, bi)
# assert ai >= 1
# assert bi >= 1
if no_edit?(ai, bi)
@table[ai - 1][bi - 1] # 左上
else
[
@table[ai - 1][bi ], # 上
@table[ai ][bi - 1] # 左
].min + 1
end
end
def fill_table
(0...@xs_a.size).each { |ai| @table[ai][ 0] = ai } # 左端
(0...@xs_b.size).each { |bi| @table[ 0][bi] = bi } # 上端
# 左端・上端以外の部分
(1...@xs_a.size).each do |ai|
(1...@xs_b.size).each do |bi|
@table[ai][bi] = edit_distance(ai, bi)
end
end
end
def determine_operation(ai, bi)
if ai == 0 && bi == 0
# 左上端
raise "must not happen"
elsif ai == 0
# 上端
:add # 上端より上には進めないので左に進む
elsif bi == 0
# 左端
:del # 左端より左には進めないので上に進む
else
# 上端・左端以外
if no_edit?(ai, bi)
:no_edit
else
d_del = @table[ai - 1][bi ] # 上
d_add = @table[ai ][bi - 1] # 左
if d_add == d_del
# diff コマンドのように -, + の順に表示する都合のため add を優先しているだけ
:add
elsif d_add < d_del
:add
else # d_del < d_add
:del
end
end
end
end
# 右下から左上に向かって進む
def make_ses
ai = @xs_a.size - 1
bi = @xs_b.size - 1
ses = []
until ai == 0 && bi == 0
op = determine_operation(ai, bi)
case op
when :no_edit then ai -= 1; bi -= 1 # 左上に進む
when :add then bi -= 1 # 左に進む
when :del then ai -= 1 # 上に進む
else
raise "invalid operation"
end
ses.prepend(op)
end
ses
end
end
diff のアルゴリズムのコア部分は以上。
しくみが分かってしまえば実装自体はコンパクトで、使っている言語にライブラリがなくても自分でサッと書いてしまえるレベルです。
せっかくなのでコマンド化してみました。こっちはあまり本質的でないラッパー的な部分。
# diff_cmd.rb
require_relative "diff"
def make_op_lines(xs_a, xs_b, ses)
ai = 0
bi = 0
op_lines = []
ses.each do |op|
line =
case op
when :del then xs_a[ai]
when :add then xs_b[bi]
when :no_edit then xs_a[ai]
else
raise "invalid operation"
end
case op
when :del then ai += 1
when :add then bi += 1
when :no_edit then ai += 1; bi += 1
else
raise "invalid operation"
end
op_lines << [op, line]
end
op_lines
end
def print_op_lines(op_lines)
op_sign_map = {
del: "-",
add: "+",
no_edit: " "
}
op_lines.each do |op, line|
puts op_sign_map[op] + line.chomp
end
end
if $0 == __FILE__
lines_a = File.read(ARGV[0]).lines
lines_b = File.read(ARGV[1]).lines
diff = Diff.new(lines_a, lines_b)
diff.fill_table
ses = diff.make_ses
op_lines = make_op_lines(lines_a, lines_b, ses)
print_op_lines(op_lines)
end
コマンドの実行例:
$ cat input_a.json
[
1,
2,
3
]
$ cat input_b.json
[
1,
4,
5,
3
]
$ ruby diff_cmd.rb input_a.json input_b.json
[
1,
- 2,
+ 4,
+ 5,
3
]
diff コマンドに -w（--ignore-all-space）オプションを指定したときのようにスペースを無視した差分にするのは簡単で、スペースを取り除いたものを入力として渡してあげるだけでOK。
- diff = Diff.new(lines_a, lines_b)
+ diff = Diff.new(
+ lines_a.map{ |line| line.delete(" ") },
+ lines_b.map{ |line| line.delete(" ") }
+ )
$ cat input_a.json
[
1,
2,
3
]
$ cat input_c.json
[
1,
[
2,
3
]
]
$ ruby diff_cmd_w.rb input_a.json input_c.json
[
1,
+ [
2,
3
+ ]
]
メモ
ここから下はおまけの自分用メモです。
後はソース読んだりリンク先の記事や書籍を読んでね（← 将来の自分向けのメッセージ）。
- 15 動的計画法 / 15.4 最長共通部分列 / 章末問題 15-5 編集距離
- 達人出版会
- 3.6.3 動的計画法（編集距離を扱っている）
コア部分の処理は大きく2つのステップに分かれる。
- (1) 表を埋める
- それぞれのセルに入る値は編集距離（レーベンシュタイン距離）
- 今回の例の場合は追加・削除のみで置換はなし
- 動的計画法の場合はこの処理にかかる計算量・メモリ使用量が O(MN)
- M, N は2つの入力のそれぞれの大きさ
- (2) SES（shortest edit script）を求める
- 末尾（右下）から先頭（左上）に向かってコストの低い経路を辿る
こういうイメージ:
表と編集距離
たとえば入力が ab → aX だった場合、
| a | X | ||
|---|---|---|---|
| 0 | 1 | 2 | |
| a | 1 | 0 (A) | 1 (B) |
| b | 2 | 1 (C) | 2 (D) |
表の (A)〜(D) のセルに入る値はそれぞれ以下のようになる。
(A) "a" → "a" の編集距離
(B) "a" → "aX" の編集距離
(C) "ab" → "a" の編集距離
(D) "ab" → "aX" の編集距離
-
あるセルに入る値を求めるには 左上、上、左の3つのセルの値が分かっていればよく、それ以外については知る必要がない。
- (A), (B), (C) が分かっていれば (D) を求めることができる
- (A) "a" → "a" の編集距離
- (B) "a" → "aX" の編集距離
- (C) "ab" → "a" の編集距離
- が分かっていれば「(D) "ab" → "aX" の編集距離」を簡単に得ることができる
- 入力がどんなに大きくなっても「1つ前の編集距離」が分かっていれば、それを元に「その次」の編集距離を低コストで求めることができる。
- (A), (B), (C) が分かっていれば (D) を求めることができる
-
「1つ前の値」＝ 99 とすでに分かっていればそれに 1 を足すだけで「その次の値」＝ 100 が得られるのだから、馬鹿正直に 1 を 100回足し直す必要はない、みたいな発想
- この性質を利用して動的計画法の形に持ち込んでいる
-
表には 3 * 3 = 9 個のセルがあり、結局以下のように先頭部分文字列同士のすべての組み合わせについて編集距離を求めていることになる（が、上述のようにそれら一つ一つについて馬鹿正直に求める必要はない）
"" → ""
"" → "a"
"" → "aX"
"a" → ""
"a" → "a"
"a" → "aX"
"ab" → ""
"ab" → "a"
"ab" → "aX"
シンプルな例をいくつか。
"" → ""
"" → "ab"
"ab" → ""
"ab" → "ab"
"ab" → "cd"
"abc" → "aXc"
入力となる配列 A, B と SES があれば、これらを使って diff コマンドのような出力を作れる。ここは簡単。
input_a = ["a", "b", "c"]
input_b = ["a", "X", "c"]
ses = [:no_edit, :del, :add, :no_edit]
↓出力
a ... input_a[0]
-b ... input_a[1]
+X ... input_b[1]
c ... input_a[2]
上に貼ったコードでいえばこの部分。
op_lines = make_op_lines(lines_a, lines_b, ses)
print_op_lines(op_lines)
文字列以外への拡張・一般化
- 例では入力として文字列の配列を使っているが、配列の要素同士の一致判定さえできればどんな値が入った配列でも処理対象にできる（はず）
- そういう意味では
no_edit?メソッドで行っている一致判定の部分がキモ。ロジック中で変更が必要なのはここだけ。
- そういう意味では
- Java でいえば、一致の判定ができる
Matchableというインターフェイスが仮にあったとして、List<Matchable>同士であれば処理対象にできる、みたいなイメージ
利用例（実際にやったことがあるもの）:
- ウェブアプリケーション
- フォームでテキストを編集して保存する前に差分を確認したい
- Wiki ページのスナップショット間の差分表示
- 自作 virtual dom ライブラリに組み込む
- 自動テストや監視などで失敗したときにレポートや通知に差分を出力させたい
自前実装しなくても diff コマンドに任せた方が良い場合はもちろんそうすればよいし、既存のライブラリを使った方が良ければそれを使えばよいと思います。
Ruby の場合はたとえば diff-lcs や diffy といった gem があるようです。
この記事を読んだ人は（ひょっとしたら）こちらも読んでいます
Discussion