diff options
Diffstat (limited to 'src/net/cbaines/suma/StringDistanceComparator.java')
| -rw-r--r-- | src/net/cbaines/suma/StringDistanceComparator.java | 163 |
1 files changed, 82 insertions, 81 deletions
diff --git a/src/net/cbaines/suma/StringDistanceComparator.java b/src/net/cbaines/suma/StringDistanceComparator.java index 9230f1c..d42451f 100644 --- a/src/net/cbaines/suma/StringDistanceComparator.java +++ b/src/net/cbaines/suma/StringDistanceComparator.java @@ -21,113 +21,114 @@ package net.cbaines.suma; import java.util.Comparator; - public class StringDistanceComparator implements Comparator<POI> { - private String userString; + private String userString; - // private static final String TAG = "StringDistanceComparator"; + // private static final String TAG = "StringDistanceComparator"; - public StringDistanceComparator(String userString) { - super(); - this.userString = userString; - } + public StringDistanceComparator(String userString) { + super(); + this.userString = userString; + } - public int compare(POI poi1, POI poi2) { - int distTo1 = LD(userString, poi1.toString()); - // Log.i(TAG, "Comparing " + userString + " and " + poi1.toString() + " got dist " + distTo1); - int distTo2 = LD(userString, poi2.toString()); - // Log.i(TAG, "Comparing " + userString + " and " + poi2.toString() + " got dist " + distTo2); - return distTo1 - distTo2; - } + public int compare(POI poi1, POI poi2) { + int distTo1 = LD(userString, poi1.toString()); + // Log.i(TAG, "Comparing " + userString + " and " + poi1.toString() + + // " got dist " + distTo1); + int distTo2 = LD(userString, poi2.toString()); + // Log.i(TAG, "Comparing " + userString + " and " + poi2.toString() + + // " got dist " + distTo2); + return distTo1 - distTo2; + } - // Below is public domain code from http://www.merriampark.com/ld.htm + // Below is public domain code from http://www.merriampark.com/ld.htm - // **************************** - // Get minimum of three values - // **************************** + // **************************** + // Get minimum of three values + // **************************** - private int Minimum(int a, int b, int c) { - int mi; + private int Minimum(int a, int b, int c) { + int mi; + + mi = a; + if (b < mi) { + mi = b; + } + if (c < mi) { + mi = c; + } + return mi; - mi = a; - if (b < mi) { - mi = b; - } - if (c < mi) { - mi = c; - } - return mi; - - } - - // ***************************** - // Compute Levenshtein distance - // ***************************** - - public int LD(String s, String t) { - int d[][]; // matrix - int n; // length of s - int m; // length of t - int i; // iterates through s - int j; // iterates through t - char s_i; // ith character of s - char t_j; // jth character of t - int cost; // cost - - // Step 1 - - n = s.length(); - m = t.length(); - if (n == 0) { - return m; - } - if (m == 0) { - return n; } - d = new int[n + 1][m + 1]; - // Step 2 + // ***************************** + // Compute Levenshtein distance + // ***************************** + + public int LD(String s, String t) { + int d[][]; // matrix + int n; // length of s + int m; // length of t + int i; // iterates through s + int j; // iterates through t + char s_i; // ith character of s + char t_j; // jth character of t + int cost; // cost + + // Step 1 + + n = s.length(); + m = t.length(); + if (n == 0) { + return m; + } + if (m == 0) { + return n; + } + d = new int[n + 1][m + 1]; + + // Step 2 - for (i = 0; i <= n; i++) { - d[i][0] = i; - } + for (i = 0; i <= n; i++) { + d[i][0] = i; + } - for (j = 0; j <= m; j++) { - d[0][j] = j; - } + for (j = 0; j <= m; j++) { + d[0][j] = j; + } - // Step 3 + // Step 3 - for (i = 1; i <= n; i++) { + for (i = 1; i <= n; i++) { - s_i = s.charAt(i - 1); + s_i = s.charAt(i - 1); - // Step 4 + // Step 4 - for (j = 1; j <= m; j++) { + for (j = 1; j <= m; j++) { - t_j = t.charAt(j - 1); + t_j = t.charAt(j - 1); - // Step 5 + // Step 5 - if (s_i == t_j) { - cost = 0; - } else { - cost = 1; - } + if (s_i == t_j) { + cost = 0; + } else { + cost = 1; + } - // Step 6 + // Step 6 - d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost); + d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost); - } + } - } + } - // Step 7 + // Step 7 - return d[n][m]; + return d[n][m]; - } + } } |