X-Git-Url: http://git.polytechnique.org/?a=blobdiff_plain;f=ekit%2Fcom%2Fswabunga%2Fspell%2Fengine%2FEditDistance.java;fp=ekit%2Fcom%2Fswabunga%2Fspell%2Fengine%2FEditDistance.java;h=1cfa73adedb028e33865f4c3cefb5f500142f3d1;hb=6dd702802493556cff5e55eb4982d23e79a30832;hp=0000000000000000000000000000000000000000;hpb=c47fa64d719ab7f5062a87fbf5cc55a7916c5c53;p=old-projects.git

diff --git a/ekit/com/swabunga/spell/engine/EditDistance.java b/ekit/com/swabunga/spell/engine/EditDistance.java
new file mode 100644
index 0000000..1cfa73a
--- /dev/null
+++ b/ekit/com/swabunga/spell/engine/EditDistance.java
@@ -0,0 +1,58 @@
+package com.swabunga.spell.engine;

+

+import java.io.BufferedReader;

+import java.io.InputStreamReader;

+

+/** JMH Again, there is no need to have a global class matrix variable

+ *  in this class. I have removed it and made the getDistance static final

+ */

+public class EditDistance {

+

+	public static Configuration config = Configuration.getConfiguration();

+

+    public static final int getDistance(String word, String similar) {

+        int a_size = word.length() + 1;

+        int b_size = similar.length() + 1;

+        int[][] matrix = new int[a_size][b_size];

+        matrix[0][0] = 0;

+        for (int j = 1; j != b_size; ++j)

+            matrix[0][j] = matrix[0][j - 1] + config.getInteger(Configuration.EDIT_DEL1);

+        word = " " + word;

+        similar = " " + similar;

+        int te;

+        for (int i = 1; i != a_size; ++i) {

+            matrix[i][0] = matrix[i - 1][0] + config.getInteger(Configuration.EDIT_DEL2);

+            for (int j = 1; j != b_size; ++j) {

+                if (word.charAt(i) == similar.charAt(j)) {

+                    matrix[i][j] = matrix[i - 1][j - 1];

+                } else {

+                    matrix[i][j] = config.getInteger(Configuration.EDIT_SUB) + matrix[i - 1][j - 1];

+                    if (i != 1 && j != 1 &&

+                            word.charAt(i) == similar.charAt(j - 1) && word.charAt(i - 1) == similar.charAt(j)) {

+                        te = config.getInteger(Configuration.EDIT_SWAP) + matrix[i - 2][j - 2];

+                        if (te < matrix[i][j]) matrix[i][j] = te;

+                    }

+                    te = config.getInteger(Configuration.EDIT_DEL1) + matrix[i - 1][j];

+                    if (te < matrix[i][j]) matrix[i][j] = te;

+                    te = config.getInteger(Configuration.EDIT_DEL2) + matrix[i][j - 1];

+                    if (te < matrix[i][j]) matrix[i][j] = te;

+                }

+            }

+        }

+        return matrix[a_size - 1][b_size - 1];

+    }

+

+    public static void main(String[] args) throws Exception {

+        EditDistance ed = new EditDistance();

+        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

+        String input = "";

+        String input2 = "";

+        while (input != null) {

+            input = stdin.readLine();

+            input2 = stdin.readLine();

+            System.out.println(ed.getDistance(input, input2));

+        }

+    }

+}

+

+