Rubyで素朴なdiffコマンドを書いてみた（動的計画法）

だいぶ前に書いたものを見て思い出したりしつつ最低限のものを書いてみました。

コード

一番ベーシックな動的計画法のものを書いてみました。より改良された手法もあるようですが本記事では扱いません。

後で自分が見て思い出しやすいように少し冗長に書いています。「理解のためのリファクタリング」を自分なりに行った状態です。

# 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）オプションを指定したときのようにスペースを無視した差分が得られます。

-  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つ前の編集距離」が分かっていれば、それを元に「その次」の編集距離を低コストで求めることができる。

• 「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 があるようです。

この記事を読んだ人は（ひょっとしたら）こちらも読んでいます