Levenshtein Distance Computing Algorithm in Java

This is a java program to implement Levenshtein Distance Computing Algorithm. In computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of macromolecules such as DNA, which can be viewed as strings of the letters A, C, G and T. Several definitions of edit distance exist, using different sets of string operations. One of the most common variants is called Levenshtein distance.

Here is the source code of the Java Program to Implement Levenshtein Distance Computing Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
 
```
```
package com.sanfoundry.setandstring;
```
```
 
```
```
import java.util.ArrayList;
```
```
import java.util.Collections;
```
```
import java.util.List;
```
```
import java.util.Scanner;
```
```
 
```

public class ApproxStringMatchingUsingLevenshteinDistance

```
{
```

    public static int distance(String a, String b)

```
    {
```
```
        a = a.toLowerCase();
```
```
        b = b.toLowerCase();
```

        int[] costs = new int[b.length() + 1];

        for (int j = 0; j < costs.length; j++)

```
            costs[j] = j;
```

        for (int i = 1; i <= a.length(); i++)

```
        {
```
```
            costs[0] = i;
```
```
            int nw = i - 1;
```

            for (int j = 1; j <= b.length(); j++)

```
            {
```

                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]),

                        a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);

```
                nw = costs[j];
```
```
                costs[j] = cj;
```
```
            }
```
```
        }
```
```
        return costs[b.length()];
```
```
    }
```
```
 
```

    public static void main(String[] args)

```
    {
```

        Scanner sc = new Scanner(System.in);

        String text = "In computer science, approximate string matching, "

                + "often colloquially referred to as fuzzy string searching is the technique of finding strings that match a pattern approximately rather than exactly. "

                + "The problem of approximate string matching is typically divided into two sub-problems: finding approximate substring matches inside a given string and finding "

                + "dictionary strings that match the pattern approximately.";

        System.out.println("System genetated string is: \n'" + text + "'");

        System.out.println("Enter the keyword to search: ");

```
        String keyword = sc.nextLine();
```

        String[] data = text.split(" ");

        List<Integer> dist = new ArrayList<Integer>();

        for (int i = 0; i < data.length; i++)

```
        {
```

            dist.add(distance(data[i], keyword));

```
        }
```
```
        Collections.sort(dist);
```

        System.out.print("Did you mean: ");

        for (int i = 0; i < data.length; i++)

```
        {
```

            if (distance(data[i], keyword) == dist.get(0))

```
            {
```

                System.out.print(data[i] + " ");

```
            }
```
```
        }
```
```
        sc.close();
```
```
    }
```
```
}
```

Output:

$ javac ApproxStringMatchingUsingLevenshteinDistance.java
$ java ApproxStringMatchingUsingLevenshteinDistance
 
System genetated string is: 
'In computer science, approximate string matching, often colloquially referred to as fuzzy string searching is the technique of finding strings that match a pattern approximately rather than exactly. The problem of approximate string matching is typically divided into two sub-problems: finding approximate substring matches inside a given string and finding dictionary strings that match the pattern approximately.'
Enter the keyword to search: 
cpmputer
Did you mean: computer

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Wagner and Fisher Algorithm for Online String Matching

» Next - Java Program to Solve Approximate String Matching using Dynamic Programming

Related Posts:

Recommended Articles: