How to Implement the Edit Distance Algorithm

Introduction

Edit distance, also known as Levenshtein distance, measures how many single-character operations are required to convert one string into another. These operations include insertion, deletion, and substitution. It is commonly applied in areas like spell correction, genetic sequence analysis, and language understanding tasks..

How Edit Distance Works

To compute the edit distance between two strings, a dynamic programming approach is commonly used. The idea is to construct a 2D array where the value at each cell (i, j) represents the minimum edit distance between the first i characters of the first string and the first j characters of the second string.

The recurrence relations used are:

• If characters match: dp[i][j] = dp[i - 1][j - 1]
• If they don’t match:
  dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

Here,

• dp[i - 1][j] represents a deletion
• dp[i][j - 1] represents an insertion
• dp[i - 1][j - 1] represents a substitution

Java Example of Edit Distance

Below is an original Java implementation that calculates the edit distance between two strings:

public class EditDistance {

    public static int computeEditDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();

        int[][] dpArr = new int[l1 + 1][l2 + 1];

        for (int i = 0; i <= l1; i++) {
            dpArr[i][0] = i;
        }

        for (int j = 0; j <= l2; j++) {
            dpArr[0][j] = j;
        }

        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dpArr[i][j] = dpArr[i - 1][j - 1];
                } else {
                    int insert = dpArr[i][j - 1];
                    int delete = dpArr[i - 1][j];
                    int replace = dpArr[i - 1][j - 1];
                    dpArr[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
                }
            }
        }

        return dpArr[l1][l2];
    }

    public static void main(String[] args) {
        String word1 = "kitten";
        String word2 = "sitting";
        int distance = computeEditDistance(word1, word2);
        System.out.println("Edit distance between \"" + word1 + "\" and \"" + word2 + "\" is: " + distance);
    }
}

Output Explanation

Running the above code will output:

Edit distance between "kitten" and "sitting" is: 3

This result is expected because:

• “kitten” → “sitten” (substitute ‘k’ with ‘s’)
• “sitten” → “sittin” (substitute ‘e’ with ‘i’)
• “sittin” → “sitting” (insert ‘g’)

Conclusion

Edit distance provides a powerful and flexible metric to compare text similarity. With dynamic programming, it can be computed efficiently even for long strings. The example in Java demonstrates how this technique can be implemented from scratch to solve real-world problems like typo correction and pattern recognition.

You can find the example code on Github.