Scala による diff の実装 [Scala]
「Scala で diff を書いてみた」[1] という記事に触発されて [2] の論文や [3] の解説を読んで diff のアルゴリズムを勉強して自分なりに Scala で実装してみました。
これは [2] で "An O((M+N)D) Greedy Algorithm" と呼ばれているほうの実装で、論文の後半では改良についても書いてあるけどそちらは読んでいません。
私なりに工夫をした部分は全体的に副作用を排除した所とエディットグラフの格子点をオブジェクトとして表現した点です。
元論文の擬似コードで "a number of simple optimizations are employed" とされている部分は可読性の観点から取り入れませんでした。ただ元論文が「D回の編集で到達する(対角線 k 毎の)最遠点の集合」を配列で管理しているのを Set で管理するようにしたのは本当はよろしくないかもしれません。
abstract class Edit[+T]
case class Ins[T](pos: Int, ch: T) extends Edit[T]
case class Del(pos: Int) extends Edit[Nothing]
case class Vertex[T](x: Int, y: Int, a: List[T], b: List[T], h: List[Edit[T]]) {
val k = x - y
lazy val right =
if (a.isEmpty) None
else Some(Vertex(x + 1, y, a.tail, b, Del(x + 1)::h))
lazy val down =
if (b.isEmpty) None
else Some(Vertex(x, y + 1, a, b.tail, Ins(x, b.head)::h))
lazy val diagonal =
if (a.isEmpty || b.isEmpty || a.head != b.head) None
else Some(Vertex(x + 1, y + 1, a.tail, b.tail, h))
lazy val snake: Vertex[T] = diagonal match {
case Some(v) => v.snake
case None => this
}
def isGoal = { a == Nil && b == Nil }
}
def diff[T](a: List[T], b: List[T]) = {
def extend[T](d: Int, vs: Set[Vertex[T]]): List[Edit[T]] = {
vs.find {_.isGoal} match {
case Some(v) => v.h.reverse
case None =>
val next =
vs.flatMap{v => v.right ++ v.down}.map{_.snake}
.foldLeft(Set[Vertex[T]]()) { (vs, v) =>
vs.find {w => w.k == v.k} match {
case Some(w) => if (v.x > w.x) vs - w + v else vs
case None => vs + v
}
}
extend(d + 1, next)
}
}
extend(0, Set(Vertex(0, 0, a, b, Nil).snake))
}
val a = args(0).toList
val b = args(1).toList
println(diff(a, b))
実行例:
PS D:\scala> scala Diff.scala abcabba cbabac List(Del(1), Ins(1,c), Del(3), Del(6), Ins(7,c))
[1] http://d.hatena.ne.jp/h-hirai/20080202/1201939297
[2] http://citeseer.ist.psu.edu/myers86ond.html
[3] http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
コメント 0