如何在 JavaScript 中的唯一字符串中有效地找到相似的字符串？

Question

背景：我有一个包含 13,000 条人名记录的列表，其中一些是重复的，我想找出相似的来进行手动复制过程。

对于像这样的数组：

["jeff","Jeff","mandy","king","queen"] 

什么是获得的有效方法：

[["jeff","Jeff"]]

解释， ["jeff","Jeff"]因为他们的 Levenshtein 距离是 1（可以像 3 一样可变）。

/* 
Working but a slow solution
*/
function extractSimilarNames(uniqueNames) {
  let similarNamesGroup = [];

  for (let i = 0; i < uniqueNames.length; i++) {
    //compare with the rest of the array
    const currentName = uniqueNames[i];

    let suspiciousNames = [];

    for (let j = i + 1; j < uniqueNames.length; j++) {
      const matchingName = uniqueNames[j];
      if (isInLevenshteinRange(currentName, matchingName, 1)) {
        suspiciousNames.push(matchingName);
        removeElementFromArray(uniqueNames, matchingName);
        removeElementFromArray(uniqueNames, currentName);
        i--;
        j--;
      }
    }
    if (suspiciousNames.length > 0) {
      suspiciousNames.push(currentName);
    }
  }
  return similarNamesGroup;
}

我想通过 Levenshtein 距离找到相似性，而不仅仅是小写/大写相似性

我已经找到了最快的 Levenshtein 实现之一， 但我仍然需要 35 分钟才能获得 13000 个项目列表的结果。

Answer 1

您的问题不是 Levenshtein 距离实现的速度。你的问题是你必须将每个单词与其他单词进行比较。这意味着您进行 13000\xc2\xb2 比较（并且每次都计算 Levenshtein 距离）。

\n\n

所以我的方法是尝试减少比较的次数。

\n\n

以下是一些想法：

\n\n

\n

• 仅当长度差异小于 20% 时，单词才相似（只是我的估计）
  \n\xe2\x86\x92 我们可以按长度分组，并且仅将单词与长度为 \xc2\xb120% 的其他单词进行比较

\n

• 仅当单词共享许多字母时，它们才是相似的
  \n\xe2\x86\x92 我们可以创建一个例如 3-gram（全部小写）的列表，以引用它们所属的单词。
  \n\xe2\x86\x92 仅将一个单词与具有多个 3-gram 共同点的其他单词进行比较（例如，使用 Levenshtein 距离）。

\n

\n