Secret Staircase

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

スタンフォードのフリーオンライン講義の Natural Language Processing をはじめました。

第 1 週の講義で出てきたレーベンシュタイン距離が興味深かったので距離を計算するプログラムを書いてみました。(※ 課題じゃないですよ)

レーベンシュタイン距離は 2 つの文字列が異なる度合を表す値で、スペルチェッカーなどで利用されます。Wikipedia

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)
  }

  private 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&gt; Levenshtein.calc(&quot;intention&quot;, &quot;execution&quot;)
 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

まとめ

  • Scala で多次元配列を生成するには Array.ofDim が便利
  • 関係ないけど (結果表出力で調べてて見つけた) String.format の書式で %1$s みたいに位置指定できるんですね 書式付き出力メモ