Skip to content

Instantly share code, notes, and snippets.

@tixxit
Created September 28, 2011 03:10
Show Gist options
  • Select an option

  • Save tixxit/1246894 to your computer and use it in GitHub Desktop.

Select an option

Save tixxit/1246894 to your computer and use it in GitHub Desktop.
Short Levenshtein distance implementation in Scala
package net.tixxit.levenshtein
import scala.math.min
object EditDistance {
def editDist[A](a: Iterable[A], b: Iterable[A]) =
((0 to b.size).toList /: a)((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
}
@Samuel-William

Copy link
Copy Markdown

Could you please give an example of usage please?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment