
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.