This is an implementation of the Damerau-Levenshtein distance in Kotlin which I created as an exercise, but might be also useful, if it proves to be correct.
The implementation is based on this Wikipedia article, even though it does not 100% follow the suggested pseudo-code.
fun damerauLevenshteinCount(a: CharSequence, b: CharSequence): Int {
return damerauLevenshtein(a, b).first
}
/**
* According to Wikipedia:
* <cite>Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions,
* deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other</cite>
*/
fun damerauLevenshtein(a: CharSequence, b: CharSequence): Pair<Int, Array<IntArray>> {
requireNotNull(a) { "First string should not be null. Make sure you specify the first string." }
requireNotNull(b) { "Second string should not be null. Make sure you specify the second string." }
val aLength = a.length
val bLength = b.length
val d = Array(aLength + 1, { IntArray(bLength + 1) })
val daMap = hashMapOf<Char, Int>()
val maxdist = a.length + b.length
for (i in 0..aLength) {
d[i][0] = i
}
for (j in 0..bLength) {
d[0][j] = j
}
for (i in 1..aLength) {
var db = 0
for (j in 1..bLength) {
val k = daMap.getOrDefault(b[j - 1], 0)
val l = db
var cost = 0
if (a[i - 1] == b[j - 1]) {
db = j
} else {
cost = 1
}
val substitution = d[i - 1][j - 1] + cost
val insertion = d[i][j - 1] + 1
val deletion = d[i - 1][j] + 1
val transposition = if (k == 0 || l == 0) maxdist else d[k - 1][l - 1] + (i - k - 1) + 1 + (j - l - 1)
d[i][j] = intArrayOf(substitution, insertion, deletion, transposition).min() as Int
}
daMap[a[i - 1]] = i
}
return Pair(d[aLength][bLength], d)
}
Here is a unit test which shows the behaviour of this implementation:
@Test
fun damerauLevenshteinDistanceCount() {
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("h1", "h1")).isEqualTo(0)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("gil", "gil")).isEqualTo(0)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("gil", "gill")).isEqualTo(1)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("ca", "abc")).isEqualTo(2) // Differs from optimal string alignment distance distance
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("waht", "what")).isEqualTo(1)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("thaw", "what")).isEqualTo(2)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("waht", "wait")).isEqualTo(1)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "uameraD")).isEqualTo(2)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "Daremau")).isEqualTo(2)
Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "Damreau")).isEqualTo(1)
Assertions.assertThat(wagnerDamerau.osaDistanceCount("waht", "whit")).isEqualTo(2)
Assertions.assertThat(wagnerDamerau.osaDistanceCount("what", "wtah")).isEqualTo(2)
}
I want to check for its correctness as well if I am using Kotlin in the best possible idiomatic manner.