レーベンシュタイン距離を計算する

gistfile1.scala

object Levenshtein {
  def calc(a: String, b: String): Int = {
    val d = Array.ofDim[Int](a.size + 1, b.size + 1)

    // initialization
    for (i <- 0 to a.size) d(i)(0) = i
    for (j <- 0 to b.size) d(0)(j) = j

    for (
      i <- 1 to a.size;
      j <- 1 to b.size
    ) {
      d(i)(j) = List(
	d(i - 1)(j) + 1,
	d(i)(j - 1) + 1,
	d(i - 1)(j - 1) + (if (a(i - 1) == b(j - 1)) 0 else 2)
      ).min
    }

    printTable(a, b, d)

    d(a.size)(b.size)
  }

  def printTable(a: String, b: String, d: Array[Array[Int]]) {
    for (
      i <- 0 to a.size reverse;
      row = d(i)
    ) {
      print("%2s ".format(("#" + a)(i)))
      println(row.map("%2d".format(_)).mkString(" "))
    }
    println((" #" + b).map("%2s".format(_)).mkString(" "))
  }
}

scala> Levenshtein.calc("intention", "execution")
 n  9  8  9 10 11 12 11 10  9  8
 o  8  7  8  9 10 11 10  9  8  9
 i  7  6  7  8  9 10  9  8  9 10
 t  6  5  6  7  8  9  8  9 10 11
 n  5  4  5  6  7  8  9 10 11 10
 e  4  3  4  5  6  7  8  9 10  9
 t  3  4  5  6  7  8  7  8  9  8
 n  2  3  4  5  6  7  8  7  8  7
 i  1  2  3  4  5  6  7  6  7  8
 #  0  1  2  3  4  5  6  7  8  9
    #  e  x  e  c  u  t  i  o  n
res1: Int = 8