Use a Levenshtein calculating algorithm with a threshold.

pkg/analysis_services/lib/src/correction/levenshtein.dart

Index: pkg/analysis_services/lib/src/correction/levenshtein.dart
diff --git a/pkg/analysis_services/lib/src/correction/levenshtein.dart b/pkg/analysis_services/lib/src/correction/levenshtein.dart
index f25d07edbd459d016c620e7bd88d6d299b507eed..080549d7c2b132ddd6c7c1d4899ed705b4387113 100644
--- a/pkg/analysis_services/lib/src/correction/levenshtein.dart
+++ b/pkg/analysis_services/lib/src/correction/levenshtein.dart
@@ -1,46 +1,126 @@
 library levenshtein;
 
-import 'dart:math';
+import 'dart:math' as math;
+
+/**
+ * The value returned by [levenshtein] if the distance is determined
+ * to be over the specified threshold.
+ */
+const int LEVENSHTEIN_MAX = 1 << 20;
+
+const int _MAX_VALUE = 1 << 10;
+
+/**
+ * Find the Levenshtein distance between two [String]s if it's less than or
+ * equal to a given threshold.
+ *
+ * This is the number of changes needed to change one String into another,
+ * where each change is a single character modification (deletion, insertion or
+ * substitution).
+ *
+ * This implementation follows from Algorithms on Strings, Trees and Sequences
+ * by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance
+ * algorithm.
+ */
+int levenshtein(String s, String t, int threshold, {bool caseSensitive: true}) {
+  if (s == null || t == null) {
+    throw new ArgumentError('Strings must not be null');
+  }
+  if (threshold < 0) {
+    throw new ArgumentError('Threshold must not be negative');
+  }
 
-/// Levenshtein algorithm implementation based on:
-/// http://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
-///
-/// Implementation: https://github.com/conradkleinespel/levenshtein-dart
-int getLevenshteinDistance(String s, String t, {bool caseSensitive: true}) {
   if (!caseSensitive) {
     s = s.toLowerCase();
     t = t.toLowerCase();
   }
 
-  if (s == t) {
-    return 0;
-  }
-  if (s.length == 0) {
-    return t.length;
+  int n = s.length;
+  int m = t.length;

[Paul Berry, 2014/07/25 19:53:26]

Minor nit: can we swap the meanings of n and m?  I keep expecting m = s.length
and n = t.length because of alphabetical order.

Or alternatively, rename to something like s_len and t_len.

[scheglov, 2014/07/25 21:18:24]

Done.

+
+  // if one string is empty,
+  // the edit distance is necessarily the length of the other
+  if (n == 0) {
+    return m <= threshold ? m : LEVENSHTEIN_MAX;
+  } else if (m == 0) {
+    return n <= threshold ? n : LEVENSHTEIN_MAX;
   }
-  if (t.length == 0) {
-    return s.length;
+

[Paul Berry, 2014/07/25 19:53:26]

The Levenshtein distance can never be less than abs(m - n), so it's probably
worth adding a check like:

if ((m - n).abs() > threshold) {
  return LEVENSHTEIN_MAX;
}

[scheglov, 2014/07/25 21:18:24]

Done.

+  // swap the two strings to consume less memory
+  if (n > m) {
+    String tmp = s;
+    s = t;
+    t = tmp;
+    n = m;
+    m = t.length;
   }
 
-  List<int> v0 = new List<int>.filled(t.length + 1, 0);
-  List<int> v1 = new List<int>.filled(t.length + 1, 0);
+  // 'previous' cost array, horizontally
+  List<int> p = new List<int>.filled(n + 1, 0);
+  // cost array, horizontally
+  List<int> d = new List<int>.filled(n + 1, 0);
+  // placeholder to assist in swapping p and d
+  List<int> _d;
 
-  for (int i = 0; i < t.length + 1; i < i++) {
-    v0[i] = i;
+  // fill in starting table values
+  int boundary = math.min(n, threshold) + 1;
+  for (int i = 0; i < boundary; i++) {
+    p[i] = i;
   }
 
-  for (int i = 0; i < s.length; i++) {
-    v1[0] = i + 1;
+  // these fills ensure that the value above the rightmost entry of our
+  // stripe will be ignored in following loop iterations
+  _setRange(p, boundary, p.length, _MAX_VALUE);
+  _setRange(d, 0, d.length, _MAX_VALUE);
+
+  // iterates through t
+  for (int j = 1; j <= m; j++) {
+    // jth character of t
+    int t_j = t.codeUnitAt(j - 1);
+    d[0] = j;
 
-    for (int j = 0; j < t.length; j++) {
-      int cost = (s[i] == t[j]) ? 0 : 1;
-      v1[j + 1] = min(v1[j] + 1, min(v0[j + 1] + 1, v0[j] + cost));
+    // compute stripe indices, constrain to array size
+    int min = math.max(1, j - threshold);
+    int max = math.min(n, j + threshold);
+
+    // the stripe may lead off of the table if s and t are of different sizes
+    if (min > max) {
+      return LEVENSHTEIN_MAX;
+    }
+
+    // ignore entry left of leftmost
+    if (min > 1) {
+      d[min - 1] = _MAX_VALUE;
     }
 
-    for (int j = 0; j < t.length + 1; j++) {
-      v0[j] = v1[j];
+    // iterates through [min, max] in s
+    for (int i = min; i <= max; i++) {
+      if (s.codeUnitAt(i - 1) == t_j) {
+        // diagonally left and up
+        d[i] = p[i - 1];
+      } else {
+        // 1 + minimum of cell to the left, to the top, diagonally left and up
+        d[i] = 1 + math.min(math.min(d[i - 1], p[i]), p[i - 1]);
+      }
     }
+
+    // copy current distance counts to 'previous row' distance counts
+    _d = p;
+    p = d;
+    d = _d;
   }
 
-  return v1[t.length];
+  // if p[n] is greater than the threshold,
+  // there's no guarantee on it being the correct distance
+  if (p[n] <= threshold) {
+    return p[n];
+  }
+
+  return LEVENSHTEIN_MAX;
+}
+
+void _setRange(List<int> a, int start, int end, int value) {
+  for (int i = start; i < end; i++) {
+    a[i] = value;
+  }
 }