gistfile1.scala

package com.puttyjar.metagame

import scalala.scalar._;
import scalala.tensor.::;
import scalala.tensor.mutable._;
import scalala.tensor.dense._;
import scalala.tensor.sparse._;
import scalala.library.Library._;
import scalala.library.LinearAlgebra._;
import scalala.library.Statistics._;
import scalala.library.Plotting._;
import scalala.operators.Implicits._;

object Distance {
  def levenshtein(seq1: Array[Byte], seq2: Array[Byte]) = {
    val matrix = DenseMatrix.zeros[Int](seq1.size + 1, seq2.size + 1)

    matrix(::, 0) := DenseVector(0 to seq1.size: _*)
    matrix(0, ::) := DenseVector(0 to seq2.size: _*).t

    (1 to seq1.size).foreach { i =>
      (1 to seq2.size).foreach { j =>
        matrix(i, j) = if (seq1(i - 1) == seq2(j - 1)) {
          matrix(i - 1, j - 1)
        }
        else {
          List(
            matrix(i - 1, j) + 1, // deletion
            matrix(i, j - 1) + 1, // insertion
            matrix(i - 1, j - 1) + 1 // substitution
          ).min
        }
      }
    }

    matrix(seq1.size, seq2.size)
  }

  def main(args: Array[String]) {
    levenshtein(Array(1.byteValue, 3.byteValue), Array(1.byteValue, 2.byteValue))
  }
}