Clean Markup

Space-Optimized String Similarity with Levenshtein Distance in JavaScript

Space-Optimized String Similarity with Levenshtein Distance in JavaScript

Levenshtein distance quantifies how different two strings are by counting the minimum number of single-character insertions, deletions, and substitutions required to transform one string into the other. It underpins client-side typo tolerance, fuzzy command palettes, spell-check suggestions, and record deduplication. The classic textbook Wagner-Fischer dynamic programming formulation builds an (m + 1) x (n + 1) matrix, which works fine for short words but allocates unnecessary megabytes of heap memory when comparing longer paragraphs, multi-field search indexes, or large candidate lists inside a browser main thread or Web Worker.

Because each cell in row i only reads values from the immediately preceding row i - 1 and the cell to its left, the entire 2D matrix can collapse into a single linear typed array of length min(m, n) + 1, cutting space complexity from O(m * n) down to O(min(m, n)). In modern JavaScript, pairing this single-row Uint32Array pass with common prefix/suffix trimming and Unicode code-point iteration ([...str]) avoids splitting emoji or surrogate pairs in half, eliminates garbage-collection pressure, and optionally supports early termination when a distance exceeds a caller's maximum typo threshold.

Example

function levenshtein(a, b) {
  let left = Array.from(a);
  let right = Array.from(b);
  if (left.length < right.length) [left, right] = [right, left];

  const row = new Uint32Array(right.length + 1);
  for (let j = 0; j <= right.length; j++) row[j] = j;

  for (let i = 1; i <= left.length; i++) {
    let prevDiagonal = row[0];
    row[0] = i;

    for (let j = 1; j <= right.length; j++) {
      const above = row[j];
      const cost = left[i - 1] === right[j - 1] ? 0 : 1;
      row[j] = Math.min(above + 1, row[j - 1] + 1, prevDiagonal + cost);
      prevDiagonal = above;
    }
  }

  return row[right.length];
}

Implementation

/**
 * Computes space-optimized Levenshtein edit distance in O(min(m, n)) memory.
 * Uses Unicode code-point arrays so surrogate pairs count as single characters,
 * trims shared prefixes/suffixes, and supports an optional maxDistance cutoff.
 */
export function levenshteinDistance(source, target, { maxDistance = Infinity } = {}) {
  if (source === target) return 0;

  let a = Array.from(source);
  let b = Array.from(target);

  // Trim identical leading and trailing code points to shrink the DP window
  let start = 0;
  while (start < a.length && start < b.length && a[start] === b[start]) {
    start++;
  }

  let endA = a.length;
  let endB = b.length;
  while (endA > start && endB > start && a[endA - 1] === b[endB - 1]) {
    endA--;
    endB--;
  }

  a = a.slice(start, endA);
  b = b.slice(start, endB);

  if (a.length === 0) return b.length <= maxDistance ? b.length : Infinity;
  if (b.length === 0) return a.length <= maxDistance ? a.length : Infinity;

  // Ensure b is always the shorter sequence so row allocation is O(min(m, n))
  if (a.length < b.length) {
    [a, b] = [b, a];
  }

  const m = a.length;
  const n = b.length;

  // Lower bound on edits from length difference alone enables O(1) rejection
  if (m - n > maxDistance) {
    return Infinity;
  }

  const row = new Uint32Array(n + 1);
  for (let j = 0; j <= n; j++) {
    row[j] = j;
  }

  for (let i = 1; i <= m; i++) {
    let prevDiagonal = row[0];
    row[0] = i;
    let rowMin = row[0];
    const charA = a[i - 1];

    for (let j = 1; j <= n; j++) {
      const above = row[j];
      const substitutionCost = charA === b[j - 1] ? 0 : 1;

      const deletion = above + 1;
      const insertion = row[j - 1] + 1;
      const substitution = prevDiagonal + substitutionCost;

      // Branchless three-way minimum
      let best = deletion < insertion ? deletion : insertion;
      if (substitution < best) best = substitution;

      row[j] = best;
      if (best < rowMin) rowMin = best;
      prevDiagonal = above;
    }

    // If every cell in this row already exceeds maxDistance, further rows cannot recover
    if (rowMin > maxDistance) {
      return Infinity;
    }
  }

  const distance = row[n];
  return distance <= maxDistance ? distance : Infinity;
}

/**
 * Returns a normalized similarity score in [0, 1] for ranking fuzzy matches.
 */
export function normalizedSimilarity(source, target) {
  const lenA = Array.from(source).length;
  const lenB = Array.from(target).length;
  const maxLen = Math.max(lenA, lenB);
  if (maxLen === 0) return 1;

  const dist = levenshteinDistance(source, target);
  return 1 - dist / maxLen;
}

Main Point: Collapsing the Levenshtein matrix into a single rolling Uint32Array over the shorter code-point sequence delivers exact edit distances and early threshold pruning in linear O(min(m, n)) memory.

Credits

Photo by H&CO on Unsplash

← Home