SSブログ

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


nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:パソコン・インターネット

nice! 1

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。