Skip to content

Instantly share code, notes, and snippets.

@umitanuki
Created April 25, 2011 12:17
Show Gist options
  • Save umitanuki/940429 to your computer and use it in GitHub Desktop.
Save umitanuki/940429 to your computer and use it in GitHub Desktop.
levenshtein in scala
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package scalaapplication1
object Main {
def lv2(s1:String, s2:String, n1:Int, n2:Int):Int = {
(n1, n2) match{
case (i, 0) => i
case (0, j) => j
case _ => List(lv2(s1, s2, n1 - 1, n2) + 1,
lv2(s1, s2, n1, n2 - 1) + 1,
lv2(s1, s2, n1 - 1, n2 - 1) + (if(s1(n1 - 1) == s2(n2 - 1)) 0 else 1)
).min
}
}
/**
* recursive version
*/
def levenshtein2(s1:String, s2:String):Int = lv2(s1, s2, s1.length, s2.length)
/**
*
*/
def levenshtein(str1:String, str2:String):Int = {
val m = new Array[Array[Int]](str1.length + 1)
for(i <- 0 to str1.length) m(i) = new Array[Int](str2.length + 1)
for(i <- 0 to str1.length) m(i)(0) = i
for(j <- 0 to str2.length) m(0)(j) = j
for(i <- 1 to str1.length; j <- 1 to str2.length) {
val x = if(str1(i - 1) == str2(j - 1))
0
else
1
m(i)(j) = List(m(i - 1)(j) + 1, m(i)(j - 1) + 1, m(i - 1)(j - 1) + x).min
}
m(str1.length)(str2.length)
}
/**
* @param args the command line arguments
*/
def main(args: Array[String]): Unit = {
val s = "abc"
println(levenshtein2("kitten", "sitting"))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment