diff options
Diffstat (limited to 'java/src/com/android/inputmethod/latin/Utils.java')
| -rw-r--r-- | java/src/com/android/inputmethod/latin/Utils.java | 27 |
1 files changed, 22 insertions, 5 deletions
diff --git a/java/src/com/android/inputmethod/latin/Utils.java b/java/src/com/android/inputmethod/latin/Utils.java index 7b334ac0a..f01a81d6e 100644 --- a/java/src/com/android/inputmethod/latin/Utils.java +++ b/java/src/com/android/inputmethod/latin/Utils.java @@ -258,6 +258,8 @@ public class Utils { } } + + /* Damerau-Levenshtein distance */ public static int editDistance(CharSequence s, CharSequence t) { if (s == null || t == null) { throw new IllegalArgumentException("editDistance: Arguments should not be null."); @@ -273,12 +275,27 @@ public class Utils { } for (int i = 0; i < sl; ++i) { for (int j = 0; j < tl; ++j) { - if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(t.charAt(j))) { - dp[i + 1][j + 1] = dp[i][j]; - } else { - dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], - Math.min(dp[i + 1][j], dp[i][j + 1])); + final char sc = Character.toLowerCase(s.charAt(i)); + final char tc = Character.toLowerCase(t.charAt(j)); + final int cost = sc == tc ? 0 : 1; + dp[i + 1][j + 1] = Math.min( + dp[i][j + 1] + 1, Math.min(dp[i + 1][j] + 1, dp[i][j] + cost)); + // Overwrite for transposition cases + if (i > 0 && j > 0 + && sc == Character.toLowerCase(t.charAt(j - 1)) + && tc == Character.toLowerCase(s.charAt(i - 1))) { + dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i - 1][j - 1] + cost); + } + } + } + if (LatinImeLogger.sDBG) { + Log.d(TAG, "editDistance:" + s + "," + t); + for (int i = 0; i < dp.length; ++i) { + StringBuffer sb = new StringBuffer(); + for (int j = 0; j < dp[i].length; ++j) { + sb.append(dp[i][j]).append(','); } + Log.d(TAG, i + ":" + sb.toString()); } } return dp[sl][tl]; |