DEV Community

BeGoodTool.com profile image Joe Lin
Joe Lin for BeGoodTool.com

Posted on

The fastest part of this fuzzy duplicate finder is the comparison it never does

#javascript #vue #algorithms

A while back I needed the annoying middle ground between exact dedupe and "just ask an AI." Not "remove rows that are byte-for-byte identical," but "tell me whether john.smith@example.com and jon.smith@example.com are probably the same person" — at list sizes where you actually want a deterministic answer, not a chatbot taking a best guess.

I assumed I'd end up reaching for embeddings or some search index. The Vue file for this tool is much more old-school than that, in a good way: normalize each line, compare strings with Levenshtein distance, skip huge chunks of impossible pairs before the expensive work starts, then merge the surviving matches into groups. Reading the source, the clever part isn't the fuzzy metric itself. It's how much work the component avoids.

The "ignore whitespace" switch is doing more than its name suggests

The normalization step is short, but it explains a lot of the tool's behavior:

const normalize = (str) => {
  let s = str;
  if (ignoreCase.value) s = s.toLowerCase();
  if (ignoreWhitespace.value) {
    s = s.replace(/\s+/g, " ").trim();
    s = s.replace(/[.,\-_/#!$%^&*;:=`~()"'·、，。]/g, "");
  }
  return s;
};
Enter fullscreen mode Exit fullscreen mode

This is not semantic matching. It's still raw string comparison after a bit of cleanup. If the boxes are left at their defaults, the tool lowercases everything, collapses repeated whitespace, trims the ends, and removes a hand-picked set of punctuation characters.

That one regex is more important than it looks. It means Acme, Inc. and Acme Inc get closer because commas and periods disappear. But it also means the option labeled "ignore whitespace" is really "ignore whitespace plus some punctuation." And because the cleanup stops there, the tool does not know that Corp and Corporation are related tokens, or that St. and Street are the same word, or that accented characters should be folded together.

That matters when you look at the threshold math later. After normalization, john.smith@example.com vs jon.smith@example.com is one deletion away and scores extremely high. Acme Corp. vs Acme Corporation is a human-obvious near-duplicate, but as plain edit distance it's still a lot of edits apart. The component is honest about that: it doesn't pretend to understand abbreviations; it just compares cleaned strings.

The real performance trick is proving most pairs can never qualify

The tool says it can chew through thousands of rows in the browser, which sounds suspicious if you think "Levenshtein on every pair." The reason it gets away with it is that it doesn't actually do that.

First, it sorts the normalized entries by length. Then it uses the threshold to derive a hard upper bound on what lengths could still possibly match:

const order = items.map((_, idx) => idx).sort((a, b) => items[a].length - items[b].length);

const maxLenB = threshold > 0 ? Math.floor(lenA / threshold) : Infinity;
for (let oj = oi + 1; oj < order.length; oj++) {
  const j = order[oj];
  const textB = items[j];
  const lenB = textB.length;
  if (lenB > maxLenB) break;

  const maxLen = Math.max(lenA, lenB);
  const maxDist = Math.floor((1 - threshold) * maxLen);
  if (maxDist < Math.abs(lenA - lenB)) continue;
  // ...
}
Enter fullscreen mode Exit fullscreen mode

The scoring formula later is 1 - dist / maxLen. So if your threshold is 80%, the edit distance has to be at most 20% of the longer string. But edit distance can never be smaller than the length gap alone — if one string is four characters longer, you're already on the hook for at least four insertions/deletions before you even think about substitutions.

That's why the length sort is such a good trick. Once lenB grows beyond Math.floor(lenA / threshold), every later string is also too long, so the loop can break entirely instead of just continue. The component turns "compare everything with everything" into "only compare pairs that are mathematically capable of clearing the threshold."

The Levenshtein implementation itself also bails out early:

function levDist(a, b, maxDist) {
  const la = a.length, lb = b.length;
  if (Math.abs(la - lb) > maxDist) return maxDist + 1;
  let prev = new Array(lb + 1);
  for (let j = 0; j <= lb; j++) prev[j] = j;
  for (let i = 1; i <= la; i++) {
    const curr = new Array(lb + 1);
    curr[0] = i;
    let rowMin = curr[0];
    const ca = a.charCodeAt(i - 1);
    for (let j = 1; j <= lb; j++) {
      const cost = ca === b.charCodeAt(j - 1) ? 0 : 1;
      const val = Math.min(prev[j] + 1, curr[j - 1] + 1, prev[j - 1] + cost);
      curr[j] = val;
      if (val < rowMin) rowMin = val;
    }
    if (rowMin > maxDist) return maxDist + 1;
    prev = curr;
  }
  return prev[lb];
}
Enter fullscreen mode Exit fullscreen mode

That rowMin > maxDist check is the nice bit. As soon as a row in the dynamic-programming table proves there's no path back under the allowed distance budget, the function aborts. And all of this heavy work runs inside a Web Worker created from a Blob, so the page can keep updating a progress bar instead of freezing while the browser burns through comparisons.

The output groups are connected components, not pairwise cliques

Another implementation detail I wouldn't have guessed from the UI: the tool doesn't think in terms of "best match for each row." It builds a graph of successful pairs and then unions connected rows together.

edges.forEach((edge) => {
  const ra = find(edge[0]), rb = find(edge[1]);
  if (ra !== rb) parent[ra] = rb;
});

const groups = Object.keys(groupsMap)
  .map((root) => groupsMap[root])
  .filter((members) => members.length >= 2)
  .map((members) => ({
    indices: members,
    scores: members.map((m) => (bestScore[m] !== undefined ? bestScore[m] : 1)),
  }))
  .sort((a, b) => b.indices.length - a.indices.length);
Enter fullscreen mode Exit fullscreen mode

Then, back on the main thread, it turns those indices back into original strings and shows each item with a single percentage badge:

members: g.indices
  .map((memberIdx, mi) => ({
    text: entries[memberIdx],
    score: Math.round(g.scores[mi] * 100),
  }))
  .sort((a, b) => b.score - a.score),
Enter fullscreen mode Exit fullscreen mode

That means a "group" is really a connected component: if A is similar enough to B, and B is similar enough to C, all three land in one bucket even if A and C would not pass the threshold directly.

That behavior is probably what you want for cleanup work, because duplicate chains are common in real data. But it also creates a subtle interpretation trap: the percentage shown beside a row is that row's best edge anywhere in the group, not its similarity to every other row in the group, and not necessarily its similarity to the row displayed above it.

So a group can look tighter than it really is. A toy example at an 80% threshold is abcd, abcde, and abce: the middle string matches both neighbors at 80%, which is enough to union all three, even though abcd and abce are only 75% similar to each other. The source code is very clear on this once you notice the union-find step, but it isn't the kind of behavior users usually infer from a "similarity %" badge.

Honest gotchas

A few limitations fall straight out of the implementation, and I actually like that they're visible in the source instead of being hand-waved away.

First, the CSV upload path is intentionally lightweight, not a real CSV parser:

if (trimmed.includes(",")) {
  const first = trimmed.split(",")[0].trim();
  return first.replace(/^"(.*)"$/, "$1");
}
Enter fullscreen mode Exit fullscreen mode

So it only keeps the first comma-separated chunk of each line. That's fine for simple one-column exports, but a quoted field like "Acme, Inc.",123 will get mangled because .split(",")[0] stops inside the quoted name.

Second, the distance function works on JavaScript UTF-16 code units (length and charCodeAt). That's perfectly fine for most Latin text, CJK, and the normal customer-name/address cases this tool is clearly aimed at. But emoji and other astral-plane characters count as two code units, so their edit distance can be a little less intuitive than a human would expect.

And third, the default 80% threshold is stricter than a lot of people assume. It catches typos beautifully; it does not magically understand business abbreviations. If your real problem is Co. vs Company, St vs Street, or domain-specific aliases, you'd need extra normalization rules before Levenshtein even starts.

I turned this into a small free tool if you want to throw a messy list at it without wiring up your own worker, distance matrix, and CSV export: Fuzzy Duplicate Finder.

Available in other languages

Top comments (0)