新井です。

In message "[ruby-list:38466] Re: diff library"
  on 06 Oct 2003 02:32:23 +0900,
  Tanaka Akira <akr / m17n.org> wrote:
> 便利かどうかは保証の限りではありませんが、diff は私も書きました。
> Ruby/CVS に入っています。

おーありがたい。そんなところに・・・うーむ、RAA から diff で
検索しても見つかりませんでした。

> ついでにいえば、
> http://arika.org/memo.cgi?cmd=view;name=UNIX+USER+2002.02 でコメントに
> かこつけて各 diff のアルゴリズムについて触れています。

O(NP)が実装されているのですね、Claus Rick という人の論文がリ
ンク切れで見つかりませんでした。残念っと思ったら簡単に見つかった

  http://theory.cs.uni-bonn.de/blum/Mitarbeiter/rick/

で、実際のライブラリの方ですがまだこれから使い方を見るところですが

ruby -I /tmp/ruby-cvs/lib -rdiff.rb -e '
  diff = Diff.new("aaabc".split(//),"bcaaad".split(//))
  p diff.lcs
  diff.ses.each {|v| p v}
'
[:add_elt, nil, ["b", "c"]]
[:common_elt_elt, ["a", "a", "a"], ["a", "a", "a"]]
[:del_elt, ["b", "c"], nil]
[:add_elt, nil, ["d"]]

むむ、これは便利。汎用的な分以下のように応用が効きやすいようです。

ruby -I /tmp/ruby-cvs/lib -rdiff.rb -e '
class Diff
  def Diff.comm(a, b, &block)
    Diff.new(a, b).ses.comm(&block)
  end

  class EditScript
    def comm
      each {|mark, del, add|
        case mark
        when :add_elt
	  add.each {|v| yield(nil,v,nil) }
        when :common_elt_elt
	  add.each {|v| yield(nil,nil,v) }
        when :del_elt
	  del.each {|v| yield(v,nil,nil) }
	end
      }
    end
  end
end

Diff.comm("aaabc".split(//),"bcaaad".split(//)) {|*a|
 puts "%5s %5s %5s" % a
}
'
=>

          b
          c
                a
                a
                a
    b
    c
          d

--
新井康司 (Koji Arai)