Created
May 10, 2017 04:30
-
-
Save scorta/7c2ae042992c0225dc1aa50cbec8d056 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Collections; | |
/** | |
* Created by Scorta on 09/05/2017. | |
*/ | |
class LevenshteinEditDistance { | |
private enum Operation {COPY, DELETE, INSERT, REPLACE} | |
private static ArrayList<String> operationSequence = new ArrayList<>(); | |
private static int[][] costs; | |
private static String x = "algorithm", y = "altruistic"; | |
public static void main(String[] args) { | |
System.out.println("The Levenshtein Distance between " + x + " and " + y + " is: " + distance(x, y)); | |
System.out.println(trackBack()); | |
} | |
private static int distance(String x, String y) { | |
costs = new int[x.length() + 1][]; | |
for (int row = 0; row < x.length() + 1; row++) { | |
costs[row] = new int[y.length() + 1]; | |
} | |
if (x.length() == 0) { | |
return y.length(); | |
} | |
if (y.length() == 0) { | |
return x.length(); | |
} | |
for (int row = 0; row <= x.length(); row++) { | |
costs[row][0] = row; | |
} | |
for (int column = 0; column <= y.length(); column++) { | |
costs[0][column] = column; | |
} | |
for (int target = 1; target <= y.length(); target++) | |
for (int source = 1; source <= x.length(); source++) { | |
if (x.charAt(source - 1) == y.charAt(target - 1)) { | |
costs[source][target] = costs[source - 1][target - 1]; | |
} else { | |
costs[source][target] = min( | |
costs[source - 1][target] + 1, | |
costs[source][target - 1] + 1, | |
costs[source - 1][target - 1] + 1 | |
); | |
} | |
} | |
return costs[x.length()][y.length()]; | |
} | |
private static int min(int... numbers) { | |
int minTmp = numbers[0]; | |
for (int index = 1; index < numbers.length; index++) { | |
if (minTmp > numbers[index]) { | |
minTmp = numbers[index]; | |
} | |
} | |
return minTmp; | |
} | |
private static String trackBack() { | |
Cell currentCell = new Cell(x.length(), y.length()); | |
do | |
operationSequence.add(previous(currentCell)); | |
while (currentCell.getRow() != 0 || currentCell.getColumn() != 0); | |
Collections.reverse(operationSequence); | |
return "Optimal operation: " + operationSequence.toString(); | |
} | |
private static String previous(Cell c) { | |
String operation = ""; | |
int newRow = 0; | |
int newColumn = 0; | |
int costTmp = Integer.MAX_VALUE; | |
if (c.getColumn() > 0 && c.getRow() > 0 && x.charAt(c.getRow() - 1) == y.charAt(c.getColumn() - 1)) { | |
operation = Operation.COPY.toString(); | |
newRow = c.getRow() - 1; | |
newColumn = c.getColumn() - 1; | |
c.set(newRow, newColumn); | |
return operation; | |
} | |
if(c.getRow() > 0 && costs[c.getRow() - 1][c.getColumn()] <= costTmp){ | |
costTmp = costs[c.getRow() - 1][c.getColumn()]; | |
operation = Operation.DELETE.toString(); | |
newRow = c.getRow() - 1; | |
newColumn = c.getColumn(); | |
} | |
if (c.getColumn() > 0 && costs[c.getRow()][c.getColumn() - 1] <= costTmp) { | |
costTmp = costs[c.getRow()][c.getColumn() - 1]; | |
operation = Operation.INSERT.toString(); | |
newRow = c.getRow(); | |
newColumn = c.getColumn() - 1; | |
} | |
if (c.getColumn() > 0 && c.getRow() > 0 && costs[c.getRow() - 1][c.getColumn() - 1] <= costTmp) { | |
operation = Operation.REPLACE.toString(); | |
newRow = c.getRow() - 1; | |
newColumn = c.getColumn() - 1; | |
} | |
c.set(newRow, newColumn); | |
return operation; | |
} | |
} | |
class Cell { | |
private int row; | |
private int column; | |
public Cell(int row, int column) { | |
set(row, column); | |
} | |
public int getRow() { | |
return row; | |
} | |
public int getColumn() { | |
return column; | |
} | |
public void set(int row, int column) { | |
this.row = row; | |
this.column = column; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment