feat(@angular-devkit/core): add levenshtein distance utility

hansl · alexeagle · commit 1b5c0082efb2 · 2018-09-06T07:37:48.000-07:00
diff --git a/packages/angular_devkit/core/src/utils/strings.ts b/packages/angular_devkit/core/src/utils/strings.ts
@@ -127,3 +127,52 @@ export function underscore(str: string): string {
 export function capitalize(str: string): string {
   return str.charAt(0).toUpperCase() + str.substr(1);
 }
+
+/**
+ * Calculate the levenshtein distance of two strings.
+ * See https://en.wikipedia.org/wiki/Levenshtein_distance.
+ * Based off https://gist.github.com/andrei-m/982927 (for using the faster dynamic programming
+ * version).
+ *
+ * @param a String a.
+ * @param b String b.
+ * @returns A number that represents the distance between the two strings. The greater the number
+ *   the more distant the strings are from each others.
+ */
+export function levenshtein(a: string, b: string): number {
+  if (a.length == 0) {
+    return b.length;
+  }
+  if (b.length == 0) {
+    return a.length;
+  }
+
+  const matrix = [];
+
+  // increment along the first column of each row
+  for (let i = 0; i <= b.length; i++) {
+    matrix[i] = [i];
+  }
+
+  // increment each column in the first row
+  for (let j = 0; j <= a.length; j++) {
+    matrix[0][j] = j;
+  }
+
+  // Fill in the rest of the matrix
+  for (let i = 1; i <= b.length; i++) {
+    for (let j = 1; j <= a.length; j++) {
+      if (b.charAt(i - 1) == a.charAt(j - 1)) {
+        matrix[i][j] = matrix[i - 1][j - 1];
+      } else {
+        matrix[i][j] = Math.min(
+          matrix[i - 1][j - 1] + 1, // substitution
+          matrix[i][j - 1] + 1, // insertion
+          matrix[i - 1][j] + 1, // deletion
+        );
+      }
+    }
+  }
+
+  return matrix[b.length][a.length];
+}
