Skip to content

Instantly share code, notes, and snippets.

@aartajew
Created April 20, 2023 10:05
Show Gist options
  • Save aartajew/526b22b2e13d5cda1ce56877991ec3d8 to your computer and use it in GitHub Desktop.
Save aartajew/526b22b2e13d5cda1ce56877991ec3d8 to your computer and use it in GitHub Desktop.
Scala > Calculate Levenshtein distance
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment