Scala > Calculate Levenshtein distance

LevenshteinDistance.scala

package util

import scala.math.min

object LevenshteinDistance {

  def apply[A](expected: Iterable[A], actual: Iterable[A]) = round(100.0 * editDist(expected, actual) / expected.size)

  def pair[A](expectedLeft: Iterable[A], actualLeft: Iterable[A], expectedRight: Iterable[A], actualRight: Iterable[A]) = {
    val leftDistance = apply(expectedLeft, actualLeft)
    val rightDistance = apply(expectedRight, actualRight)
    val leftWeight = expectedLeft.size
    val rightWeight = expectedRight.size
    val totalWeight = leftWeight + rightWeight
    round((leftDistance * leftWeight + rightDistance * rightWeight) / totalWeight)
  }

  private def editDist[A](a: Iterable[A], b: Iterable[A]) =
    (a foldLeft (0 to b.size).toList)((prev, x) =>
      (prev zip prev.tail zip b).scanLeft(prev.head + 1) {
        case (h, ((d, v), y)) =>
          min(min(h + 1, v + 1), d + (if (x == y) 0 else 1))
    }) last

  private def round(result: Double) = BigDecimal(result).setScale(2, BigDecimal.RoundingMode.HALF_UP).toDouble
}