1
\$\begingroup\$

I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment:

LevenshteinEditDistance.java:

package net.coderodde.string.levenshtein;

import java.awt.Point;
import java.util.HashMap;
import java.util.Map;

/**
 * This class implements the Levenshtein edit distance algorthm.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 20, 2016)
 */
public class LevenshteinEditDistance {

    /**
     * Denotes the fact that one character in one input string was removed.
     */
    public static final String GAP = "-";

    public static final class LevenshteinEditDistanceResult {
        private final int distance;
        private final String editSequence;
        private final String topAlignmentRow;
        private final String bottomAlignmentRow;

        LevenshteinEditDistanceResult(final int distance,
                                      final String editSequence,
                                      final String topAlignmentRow,
                                      final String bottomAlignmentRow) {
            this.distance           = distance;
            this.editSequence       = editSequence;
            this.topAlignmentRow    = topAlignmentRow;
            this.bottomAlignmentRow = bottomAlignmentRow;
        }

        public int getDistance() {
            return distance;
        }

        public String getEditSequence() {
            return editSequence;
        }

        public String getTopAlignmentRow() {
            return topAlignmentRow;
        }

        public String getBottomAlignmentRow() {
            return bottomAlignmentRow;
        }
    }

    private static enum EditOperation {
        INSERT     ("I"),
        SUBSTITUTE ("S"),
        DELETE     ("D"),
        NONE       ("N");

        private final String s;

        private EditOperation(String s) {
            this.s = s;
        }

        @Override
        public String toString() {
            return s;
        }
    }

    public static LevenshteinEditDistanceResult compute(String s, String z) {
        // This is required to keep the parent map invariant. If we did not do
        // this, the very first edit operation would not end up in the output.
        // For more details, comment out the following two rows and see what 
        // happens.
        s = "\u0000" + s;
        z = "\u0000" + z;

        final int n = s.length();
        final int m = z.length();
        final int[][] d = new int[m + 1][n + 1];
        final Map<Point, Point> parentMap = new HashMap<>();

        for (int i = 1; i <= m; ++i) {
            d[i][0] = i;
        }

        for (int j = 1; j <= n; ++j) {
            d[0][j] = j;
        }

        for (int j = 1; j <= n; ++j) {
            for (int i = 1; i <= m; ++i) {
                final int delta = (s.charAt(j - 1) == z.charAt(i - 1)) ? 0 : 1;

                int tentativeDistance = d[i - 1][j] + 1;
                EditOperation editOperation = EditOperation.INSERT;

                if (tentativeDistance > d[i][j - 1] + 1) {
                    tentativeDistance = d[i][j - 1] + 1;
                    editOperation = EditOperation.DELETE;
                }

                if (tentativeDistance > d[i - 1][j - 1] + delta) {
                    tentativeDistance = d[i - 1][j - 1] + delta;
                    editOperation = EditOperation.SUBSTITUTE;
                }

                d[i][j] = tentativeDistance;

                switch (editOperation) {
                    case SUBSTITUTE:
                        parentMap.put(new Point(i, j), new Point(i - 1, j - 1));
                        break;

                    case INSERT:
                        parentMap.put(new Point(i, j), new Point(i - 1, j));
                        break;

                    case DELETE:
                        parentMap.put(new Point(i, j), new Point(i, j - 1));
                        break;
                }
            }
        }

        final StringBuilder topLineBuilder      = new StringBuilder(n + m);
        final StringBuilder bottomLineBuilder   = new StringBuilder(n + m);
        final StringBuilder editSequenceBuilder = new StringBuilder(n + m);
        Point current = new Point(m, n);

        while (true) {
            Point predecessor = parentMap.get(current);

            if (predecessor == null) {
                break;
            }

            if (current.x != predecessor.x && current.y != predecessor.y) {
                final char schar = s.charAt(predecessor.y);
                final char zchar = z.charAt(predecessor.x);

                topLineBuilder.append(schar);
                bottomLineBuilder.append(zchar);
                editSequenceBuilder.append(schar != zchar ? 
                                           EditOperation.SUBSTITUTE :
                                           EditOperation.NONE);
            } else if (current.x != predecessor.x) {
                topLineBuilder.append(GAP);
                bottomLineBuilder.append(z.charAt(predecessor.x));
                editSequenceBuilder.append(EditOperation.INSERT);
            } else {
                topLineBuilder.append(s.charAt(predecessor.y)); 
                bottomLineBuilder.append(GAP);
                editSequenceBuilder.append(EditOperation.DELETE);
            }

            current = predecessor;
        }

        // Remove the last characters that correspond to the very beginning 
        // of the alignments and edit sequence (since the path reconstructoin
        // proceeds from the "end" to the "beginning" of the distance matrix.
        topLineBuilder     .deleteCharAt(topLineBuilder.length() - 1);
        bottomLineBuilder  .deleteCharAt(bottomLineBuilder.length() - 1);
        editSequenceBuilder.deleteCharAt(editSequenceBuilder.length() - 1);

        // Our result data is backwards, reverse them.
        topLineBuilder     .reverse();
        bottomLineBuilder  .reverse();
        editSequenceBuilder.reverse();

        return new LevenshteinEditDistanceResult(d[m][n],
                                                 editSequenceBuilder.toString(),
                                                 topLineBuilder.toString(),
                                                 bottomLineBuilder.toString());
    }

    public static void main(String[] args) {
        LevenshteinEditDistanceResult result = compute("aballad", "handball");
        System.out.println("Distance: " + result.getDistance());
        System.out.println("Edit sequence: " + result.getEditSequence());
        System.out.println("Alignment:");
        System.out.println(result.getTopAlignmentRow());
        System.out.println(result.getBottomAlignmentRow());
    }
}

Output:


Distance: 5
Edit sequence: INIINNNNDD
Alignment:
-a--ballad
handball--

Any critique much appreciated.

\$\endgroup\$
1
  • \$\begingroup\$ So, this is the Wagner–Fischer algorithm, right? \$\endgroup\$
    – ZeroOne
    Apr 20, 2016 at 20:33

1 Answer 1

4
\$\begingroup\$

Variable naming

First, you should give descriptive names to your variables. It's incredibly taxing on one's working memory to work with half a dozen one letter variables. Try something like this for the beginning of your class:

    final int string1Length = string1.length();
    final int string2Length = string2.length();
    final int[][] distanceMatrix = new int[string2Length + 1][string1Length + 1];
    final Map<Point, Point> parentMap = new HashMap<>();

    for (int column = 1; column <= string2Length; ++column) {
        distanceMatrix[column][0] = column;
    }

Much better, huh? You don't need to scroll back all the time to find the initialization of mystery variables "z", "n" or "j", because the variable name tells the purpose of that variable.

Methods

Your compute method is waaaay too long, thus difficult to read. You need to scroll back and forth to understand all the context. You could easily extract some methods, like in the beginning. Instead of this:

    final int[][] distanceMatrix = new int[string2Length + 1][string1Length + 1];
    final Map<Point, Point> parentMap = new HashMap<>();

    for (int column = 1; column <= string2Length; ++column) {
        distanceMatrix[column][0] = column;
    }

    for (int row = 1; row <= string1Length; ++row) {
        distanceMatrix[0][row] = row;
    }

do this:

    final int[][] distanceMatrix = initializeDistanceMatrix(string2Length, string1Length);
    final Map<Point, Point> parentMap = new HashMap<>();

and have the initializeDistanceMatrix method do just that and nothing else. Then, when you are reading the code, you can just skip that line with "oh, that initializes the matrix, OK" and only dive into the method if you really want to know how the matrix is actually initialized.

The part where I struggled the most is the inside of the two for loops. Lots of comparisons, assignments and magic happening. Consider extracting methods here as well:

private static int findInsertDistance(final int[][] distanceMatrix, final int column, final int row) {
    return distanceMatrix[column - 1][row] + 1;
}

private static int findDeleteDistance(final int[][] distanceMatrix, final int column, final int row) {
    return distanceMatrix[column][row - 1] + 1;
}

// .....

int tentativeDistance = findInsertDistance(distanceMatrix, column, row);
EditOperation editOperation = EditOperation.INSERT;  

final int deleteDistance = findDeleteDistance(distanceMatrix, column, row);
if (tentativeDistance > deleteDistance) {
    tentativeDistance = deleteDistance;
    editOperation = EditOperation.DELETE;
}

It's still not perfect, but it does wonders for readability.

Now, the next conditional has the extra magic variable delta which complicates the already complicated condition even further. Try this instead:

final boolean charactersAreSame = string1.charAt(row - 1) == string2.charAt(column - 1);
if (charactersAreSame) {
    final int noOpDistance = findNoOpDistance(distanceMatrix, column, row);
    if (tentativeDistance > noOpDistance) {
        tentativeDistance = noOpDistance;
        editOperation = EditOperation.NONE;
    }
} else {
    final int substitutionDistance = findSubstitutionDistance(distanceMatrix, column, row);
    if (tentativeDistance > substitutionDistance) {
        tentativeDistance = substitutionDistance;
        editOperation = EditOperation.SUBSTITUTE;
    }
}

// .....

switch (editOperation) {
    case SUBSTITUTE:
    case NONE:
        parentMap.put(new Point(column, row), new Point(column - 1, row - 1));
        break;

Now we actually differentiate between the substitution and the none operation, which you did not do before.

Having extracted the descriptive deleteDistance, substitutionDistance and noOpDistance variables I'm tempted to add insertDistance as well -- that's what you had as your initial value for the tentativeDistance, which was rather confusing too. I also think it would look nice if we grouped the variables next to each other, since we need them all anyway. The tentativeDistance is also not a very good name -- it's the distance we are trying to minimize, and it is changed when we obtain more measurements. I find currentMinimumDistance would be a better name. So:

final boolean charactersAreSame = string1.charAt(row - 1) == string2.charAt(column - 1);
final int insertDistance = findInsertDistance(distanceMatrix, column, row);
final int deleteDistance = findDeleteDistance(distanceMatrix, column, row);
final int noOpDistance = findNoOpDistance(distanceMatrix, column, row);
final int substitutionDistance = findSubstitutionDistance(distanceMatrix, column, row);
int currentMinimumDistance = insertDistance;
EditOperation editOperation = EditOperation.INSERT;

if (currentMinimumDistance > deleteDistance) {
    currentMinimumDistance = deleteDistance;
    editOperation = EditOperation.DELETE;
}
if (charactersAreSame && currentMinimumDistance > noOpDistance) {
    currentMinimumDistance = noOpDistance;
    editOperation = EditOperation.NONE;
} else if (!charactersAreSame && currentMinimumDistance > substitutionDistance) {
    currentMinimumDistance = substitutionDistance;
    editOperation = EditOperation.SUBSTITUTE;
}

distanceMatrix[column][row] = currentMinimumDistance;

Still not perfect, but not too bad either! I'm just a bit sad about the triad functions, i.e. those functions that take three parameters. The distanceMatrix argument is actually pointless, we could have instantiated this class and had the matrix as a field, instead of doing all the calculation in a static method, forcing us to use cumbersome method signatures.

Also, now we hit the parentMap object which, again, took me a long time to understand. I now know it saves pointers between the cells of the matrix so that the correct edit sequence route can be navigated. I find this route is an integral part of the matrix and it doesn't make any sense to me to have the map in a different object. What you should do is to create a new class, say Matrix, to hold the matrix data and those pointers, and use that. And please do seriously consider instantiating the class and having the instance of that class as a field in it. You can, still, have a static LevenshteinEditDistance.compute(...) method, but at the same time you can have a private constructor and some fields in there!

Skipping to the end of the method, there's a long piece of code dedicated to rendering the result. Please extract that into its own method as well:

return buildResult(distanceMatrix, string1, string2, parentMap);

In fact, your compute method should look like this:

public static LevenshteinEditDistanceResult compute(String string1, String string2) {
    final Matrix matrix = calculateMatrix(string1, string2);
    return buildResult(matrix);
}

or, actually, like this:

public static LevenshteinEditDistanceResult compute(String string1, String string2) {
    return new LevenshteinEditDistance(string1, string2).compute();
}

because that, my friend, is clean code! :)

\$\endgroup\$
2
  • \$\begingroup\$ If I could upvote an answer multiple times, I would have done so here :) \$\endgroup\$
    – sudshekhar
    Apr 21, 2016 at 6:29
  • \$\begingroup\$ Awesome review. Keep doing that. \$\endgroup\$
    – coderodde
    Apr 21, 2016 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.