Damerau Levenshtein Implementation in Kotlin

Question

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.

Answer 1

On the general algorithm, you made a small change where you do not use the trick where d[][] is indexed down to -1 at value maxdist for transposition and you replaced that by an if-clause. That's valid as far as I can tell.

As already pointed out, requireNotNull are useless and aLength is overkill when a.length will do. Worse is that you use both aLength and a.length.

You mostly just rewrote the algorithm in pseudo-code from wikipedia, but that algorithm is catastrophically unreadable. It might be fine for the people in that community writing pseudo-code and C programs, but I would argue (others might disagree) that it should be made much clearer when coding in Java or Kotlin.

The first issue with the pseudo-code is that the variables all have meaningless names. Name choices are very important in software development.

The other problem is that they use many "clever tricks" like using maxdist to set values of computations which they should not do in the first place. The cost variable which is 0 if the characters match or 1 if it's a character substitution is another such trick. I explained what it does, but it's hard to know looking at their code.

I rewrote it with decent variable names and more explicit logic without using "tricks" (I might have bugs):

fun measureDamerauLevenshtein(a: CharSequence, b: CharSequence): Int {
    val cost = Array(a.length + 1, { IntArray(b.length + 1) })
    for (iA in 0..a.length) {
        cost[iA][0] = iA
    }
    for (iB in 0..b.length) {
        cost[0][iB] = iB
    }
    val mapCharAToIndex = hashMapOf<Char, Int>()

    for (iA in 1..a.length) {
        var prevMatchingBIndex = 0
        for (iB in 1..b.length) {
            val doesPreviousMatch = (a[iA - 1] == b[iB - 1])

            val possibleCosts = mutableListOf<Int>()
            if (doesPreviousMatch) {
                // Perfect match cost.
                possibleCosts.add(cost[iA - 1][iB - 1])
            } else {
                // Substitution cost.
                possibleCosts.add(cost[iA - 1][iB - 1] + 1)
            }
            // Insertion cost.
            possibleCosts.add(cost[iA][iB - 1] + 1)
            // Deletion cost.
            possibleCosts.add(cost[iA - 1][iB] + 1)

            // Transposition cost.
            val bCharIndexInA = mapCharAToIndex.getOrDefault(b[iB - 1], 0)
            if (bCharIndexInA != 0 && prevMatchingBIndex != 0) {
                possibleCosts.add(cost[bCharIndexInA - 1][prevMatchingBIndex - 1]
                        + (iA - bCharIndexInA - 1) + 1 + (iB - prevMatchingBIndex - 1))
            }

            cost[iA][iB] = possibleCosts.min()!!

            if (doesPreviousMatch) prevMatchingBIndex = iB
        }
        mapCharAToIndex[a[iA - 1]] = iA
    }
    return cost[a.length][b.length]
}

I got rid of maxdist altogether.

I don't like that you return both the final cost and the full cost matrix. It's redundant and people won't need the full matrix. However you might have needed it for debugging. Maybe you could have made a hidden function that returns the full matrix and a public function that calls the hidden function and returns the final cost.

There is still an issue which I think is quite confusing but which I did not fix: d[][] uses 1-based indexing, but a and b use 0-based indexing. I think they should both stick to one convention.

Answer 2

For determining correctness of your implementation I recommend referring to an existing implementation such as Apache commons-lang or the newer commons-text:

• commons-lang:
  • StringUtils.java:7997-8254
  • StringUtilsTest.java:2378-2479
• commons-text
  • LevenshteinDistance.java
  • LevenshteinDistanceTest.java
  • ParameterizedLevenshteinDistanceTest.java
  • LevenshteinDetailedDistance.java
  • LevenshteinDetailedDistanceTest.java
  • LevenshteinResults.java

As far as your Kotlin code goes, here are my comments:

1. Kotlin already guarantees that a and b are not null as you've used CharSequence for their type instead of CharSequence?. As such, the requireNotnull statements are unnecessary.
2. I do not believe you gain much from aLength and bLength. a.length and b.length read clearly and are read in constant time so the additional variables seem unnecessary to me.

3. You can place the last lambda argument in a function call into parentheses as you have done but I personally find moving it out of the parentheses easier to read and more idiomatic:

   val d = Array(a.length + 1, { IntArray(b.length + 1) })
   

   becomes

   val d = Array(a.length + 1) { IntArray(b.length + 1) }
   

4. In some languages variable names like maxdist are common and expected but in Kotlin (and Java) I find it more common and expected to have variables names avoid abbreviations, use camel casing, etc. I recommend using maxDistance instead of maxdist.

5. You are returning a Pair<Int, Array<IntArray>>. This is fine but data classes are so much better and Kotlin makes it so easy to define and use them. I recommend creating your own type to return. e.g.:

   data class DamerauLevenshteinResult(val count: Int, val d: Array<IntArray>)