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

Question

背景：我有一个包含13000个人名记录的列表，其中有一些重复，我想找出相似的来进行手动去重。

对于像这样的数组：

["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个项目列表的结果。请参考talisman。

- Jeff Chung

---

可能是使用JavaScript以最佳性能按“Levenshtein距离”对数组进行排序的重复问题。 - Kevin Kopf

@alex 不要认为一个比较两个字符串的Levenshtein实现会在这里有所帮助。 - Jonas Wilms

我怀疑 removeElementFromArray 函数正在影响你的性能，因为它改变了你正在遍历的数组。删除 suspiciousNames.push(matchingName); 之后的4行内容，并使用 console.time 和 console.timeEnd 在较小的数组上进行性能测试。 - Aadit M Shah

相关 https://cs.stackexchange.com/questions/53299/find-all-pairs-of-strings-in-a-set-with-levenshtein-distance-d - גלעד ברקן

["Jeff", "eff", "effl"]的预期输出是什么？此外，您只对Levenshtein距离为1感兴趣还是它可以是可变的？ - גלעד ברקן

Answer 1

你的问题不在于Levenshtein距离实现的速度，而在于你需要将每个单词与其他所有单词进行比较。这意味着你需要进行13000²次比较（每次还要计算Levenshtein距离）。

因此我的方法是尝试减少比较的数量。

以下是一些想法：

- 单词只有在它们的长度相差不到20%时才相似（只是我的估计） → 我们可以按照长度分组，并且只比较长度上差不到±20% 的单词。 - 单词只有在它们共享很多字母时才相似 → 我们可以创建一个包含3元字母组（全部小写）的列表，这些3元字母组指向它们所属的单词。 → 只比较（例如用Levenshtein距离）与某个单词有多个3元字母组相同的其他单词。

- MrSmith42

---

主要问题是，如果我们有10个长度为[1,2,3,4,5,6,7,8,9,10]的单词，我们如何对它们进行聚类？使用任何聚类方法，都会有两个包含单词的簇，其长度仅相差1。在这种情况下，唯一的方法是将所有单词放在一个组中。 @MrSmith42，您的想法很好，我投了赞成票。但是实现起来不可能没有数据损失。 - Gor

“20%”是一个相当随意的猜测，为什么不直接说只有长度+-1的单词才会被比较呢？这样才符合问题的要求。 - Jonas Wilms

@Jonas Wilms：20% 只是我可能会使用的一个值。Levenshtein 距离至少与长度差异一样大，因此您可以使用最大可容忍的 Levenshtein 距离作为指导，以确定如何设置最大可接受的长度差异。 - MrSmith42

Answer 2

移除相似名称的方法:

1. 使用单词的音标表示。cmudict它可以与python nltk一起使用。您可以找到在音标上相近的名称。
2. 尝试不同形式的词干提取或简化。我会尝试最具攻击性的词干提取器，如波特词干提取器。

3. Levenshtein trie. 您可以创建字典树数据结构，帮助查找与搜索项距离最小的单词，这在一些搜索引擎的全文搜索中使用。据我所知，它已经在Java中实现。在您的情况下，您需要搜索一个项目，然后在每个步骤中将其添加到该结构中，您需要确保搜索的项目尚未在结构中。

4. 手动naive的方法。找到每个单词/名称的所有适当的表示形式，将所有表示形式放入映射中，并查找有超过1个单词的表示形式。如果您有大约15种不同的单词表示形式，您将需要280K次迭代才能生成此对象（比相互比较每个单词需要大约80M次比较与13K个名称）更快。

-- 编辑 --

如果有选择的话，我会使用类似Python或Java而不是JS来完成这个任务。这只是我的个人意见，原因是：我不知道所有的要求，通常使用Java/Python进行自然语言处理，该任务看起来更像是重型数据处理而非前端。

- varela

---

我喜欢这个答案，除了第一句话。即使我也不喜欢JavaScript，但没有真正的理由不使用它来实现算法。我相信你可以找到大多数提到的算法的实现，也可以很容易地将它们翻译成JavaScript。 - MrSmith42

@MrSmith42 我理解你的担忧，我知道使用 JavaScript 可能有其他原因，而且我最终也喜欢它。我更喜欢将 JavaScript 作为前端语言，并且如果需要进行大量数据处理，则不适合作为前端语言。因此，在这种情况下，它将具有较少的现成解决方案。通常使用 Java 和 Python 进行自然语言处理，如果可以选择，为什么不呢？ - varela

如果这个答案不包含那些对其他编程语言的引用，而是专注于具体算法（适用于任何语言），那么它可能会很好。 - Jonas Wilms

@JonasWilms，抱歉，我开始觉得自己对JavaScript有偏见。 - varela

Answer 3

在您的工作代码中，只使用了Levenshtein距离1，因此我将假设不需要找到其他距离。

我将提出与Jonas Wilms发布的类似的解决方案，有以下区别：

• 无需调用isLevenshtein函数
• 仅生成唯一对
• 每个对都按字典顺序排序

// Sample data with lots of similar names
const names = ["Adela","Adelaida","Adelaide","Adele","Adelia","AdeLina","Adeline",
               "Adell","AdellA","Adelle","Ardelia","Ardell","Ardella","Ardelle",
               "Ardis","Madeline","Odelia","ODELL","Odessa","Odette"];

const map = {};
const pairs = new Set;
for (const name of names) {
    for (const i in name+"_") { // Additional iteration to NOT delete a character
        const key = (name.slice(0, i) + name.slice(+i + 1, name.length)).toLowerCase();
        // Group words together where the removal from the same index leads to the same key
        if (!map[key]) map[key] = Array.from({length: key.length+1}, () => new Set);
        // If NO character was removed, put the word in EACH group
        for (const set of (+i < name.length ? [map[key][i]] : map[key])) {
            if (set.has(name)) continue;
            for (let similar of set) pairs.add(JSON.stringify([similar, name].sort()));
            set.add(name);
        }
    }
}
const result = [...pairs].sort().map(JSON.parse); // sort is optional
console.log(result);

我在一组包含至少4000个不同名称的13000个名称上进行了测试，大约在0.3秒内生成了8000对。

- trincot

Answer 4

如果我们从不同的位置删除“Jeff”中的一个字符，我们会得到“eff”，“Jff”，“Jef”和“Jef”。如果我们对“jeff”做同样的操作，我们会得到“eff”，“jff”，“Jef”和“jef”。现在，如果你仔细看，你会发现这两个字符串都产生了“eff”的结果，这意味着我们可以创建一个将这些组合映射到它们的原始版本的Map，然后为每个字符串生成所有组合并在Map中查找它们。

通过查找，您将获得类似的结果，例如“abc”和“cab”，但它们不一定具有1的Levenshtein距离，因此我们必须在之后进行检查。

那么为什么这样更好呢？

嗯，迭代所有名称是O(n)（n是单词数），创建所有组合是O(m)（m是单词中平均字符数），在Map中查找是O(1)，因此这运行时间为O(n * m)，而您的算法是O(n * n * m)，这意味着对于10,000个单词，我的算法比您的算法快10,000倍（或者我的计算是错误的：））。

  // A "OneToMany" Map
  class MultiMap extends Map {
    set(k, v) {
      if(super.has(k)) {
        super.get(k).push(v);
       } else super.set(k, [v]);
     }
     get(k) {
        return super.get(k) || [];
     }
  }

  function* oneShorter(word) {
    for(let pos = 0; pos < word.length; pos++)
       yield word.substr(0, pos) + word.substr(pos + 1);
  }

  function findDuplicates(names) {
    const combos = new MultiMap();
    const duplicates = [];

    const check = (name, combo) => {
      const dupes = combos.get(combo);
      for(const dupe of dupes) {
         if((isInLevenshteinRange(name, combo, 1))
         duplicates.push([name, dupe]);
      }
      combos.set(combo, name);
    };

    for(const name of names) {
      check(name, name);

      for(const combo of oneShorter(name)) {
         check(name, combo);
      }
    }

     return duplicates;
 }

- Jonas Wilms

---

但对于 fn("Jeff ", "Jff") 却失败了。 - Kaiido

@kaiido 如果我重复这个字符并省略一个而不是用下划线替换会怎样？ - Jonas Wilms

在“Jeff”和“Jff”的索引1处仍然没有匹配。还要注意，OP在他们的示例中使用了索引1，但他们也可能想要充分利用过滤器并深入到第2或第3级。这样做，我不确定您的算法是否比真正的Levenshtein更好地执行。 - Kaiido

@kaiido 如果我将名称本身添加到地图中，它就会起作用。从结果中删除一个会得到“eff”，“Jff”，“Jef”。是的，这对于较小的Levenshtein距离可能更好。 - Jonas Wilms

Answer 5

我有一种完全不同的方法来解决这个问题，但我相信我提出了一个相当快速的方法（但是关于它的正确性/错误性还有争议）。我的方法是将字符串映射到数字值，对这些值进行一次排序，然后通过该列表一次运行，将相邻的值进行比较。就像这样：

// Test strings (provided by OP) with some additions
var strs = ["Jeff","mandy","jeff","king","queen","joff", "Queen", "jff", "tim", "Timmo", "Tom", "Rob", "Bob"] 

// Function to convert a string into a numeric representation
// to aid with string similarity comparison
function atoi(str, maxLen){
  var i = 0;
  for( var j = 0; j < maxLen; j++ ){
    if( str[j] != null ){
      i += str.toLowerCase().charCodeAt(j)*Math.pow(64,maxLen-j) - 'a'.charCodeAt(0)*Math.pow(64,maxLen-j)
    } else {
      // Normalize the string with a pad char
      // up to the maxLen (update the value, but don't actually
      // update the string...)
      i += '-'.charCodeAt(0)*Math.pow(64,maxLen-j) - 'a'.charCodeAt(0)*Math.pow(64,maxLen-j)
    }
  }
  valMap.push({
     str,
     i 
  })
  return i;
}

Number.prototype.inRange = function(min, max){ return(this >= min && this <= max) }

var valMap = []; // Array of string-value pairs

var maxLen = strs.map((s) => s.length).sort().pop() // maxLen of all strings in the array
console.log('maxLen', maxLen)
strs.forEach((s) => atoi(s, maxLen)) // Map strings to values

var similars = [];
var subArr = []
var margin = 0.05;
valMap.sort((a,b) => a.i > b.i ? 1 : -1) // Sort the map...
valMap.forEach((entry, idx) => {  
  if( idx > 0 ){
      var closeness = Math.abs(entry.i / valMap[idx-1].i);
      if( closeness.inRange( 1 - margin, 1 + margin ) ){
        if( subArr.length == 0 ) subArr.push(valMap[idx-1].str)
        subArr.push(entry.str)
        if( idx == valMap.length - 1){
          similars.push(subArr)
        }
      } else {
        if( subArr.length > 0 ) similars.push(subArr)
        subArr = []
      }
  }
})
console.log('similars', similars)

我将每个字符串视为一个“64位数字”，其中每个“位”可以取字母数字值，其中'a'表示0。然后我对其进行一次排序。然后，如果遇到与前一个相似的值（即两者之比接近1），则推断出我有相似的字符串。

我还检查最大字符串长度，并在计算“64位值”时将所有字符串归一化为该长度。

--- 编辑：更多压力测试 --- 此外，这里还有一些额外的测试，它会拉取一个大型名称列表并快速执行处理（在20k+名称上约为50ms，有很多误报）。无论如何，这段代码应该使故障排除更容易：

var valMap = []; // Array of string-value pairs

/* Extensions */
Number.prototype.inRange = function(min, max){ return(this >= min && this <= max) }

/* Methods */
// Function to convert a string into a numeric representation
// to aid with string similarity comparison
function atoi(str, maxLen){
  var i = 0;
  for( var j = 0; j < maxLen; j++ ){
    if( str[j] != null ){
      i += str.toLowerCase().charCodeAt(j)*Math.pow(64,maxLen-j) - 'a'.charCodeAt(0)*Math.pow(64,maxLen-j)
    } else {
      // Normalize the string with a pad char
      // up to the maxLen (update the value, but don't actually
      // update the string...)
      i += '-'.charCodeAt(0)*Math.pow(64,maxLen-j) - 'a'.charCodeAt(0)*Math.pow(64,maxLen-j)
    }
  }
  valMap.push({ str, i })
  return i;
}

function findSimilars(strs){
  var maxLen = strs.map((s) => s.length).sort().pop() // maxLen of all strings in the array
  console.log('maxLen', maxLen)
  strs.forEach((s) => atoi(s, maxLen)) // Map strings to values

  var similars = [];
  var subArr = []
  var margin = 0.05;
  valMap.sort((a,b) => a.i > b.i ? 1 : -1) // Sort the map...
  valMap.forEach((entry, idx) => {  
    if( idx > 0 ){
        var closeness = Math.abs(entry.i / valMap[idx-1].i);
        if( closeness.inRange( 1 - margin, 1 + margin ) ){
          if( subArr.length == 0 ) subArr.push(valMap[idx-1].str)
          subArr.push(entry.str)
          if( idx == valMap.length - 1){
            similars.push(subArr)
          }
        } else {
          if( subArr.length > 0 ) similars.push(subArr)
          subArr = []
        }
    }
  })
  console.log('similars', similars)
}

// Stress test with 20k+ names 
$.get('https://raw.githubusercontent.com/dominictarr/random-name/master/names.json')
.then((resp) => {
  var strs = JSON.parse(resp);
  console.time('processing')
  findSimilars(strs)
  console.timeEnd('processing')
})
.catch((err) => { console.err('Err retrieving JSON'); })

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>

由于某种原因，当我在JSFiddle中运行它时，它可以在约50毫秒内运行，但在Stackoverflow片段中，它接近1000毫秒。

- RichS

---

非常好，但这使得第一个字符比最后一个字符更重要。因此，在按字母顺序排序的列表中，兄弟项将始终仅与相邻项匹配。 - varela

不行，这样做行不通。"abc" 和 "zbc" 在你的排序中相距遥远，但Levenshtein距离为1。 - Jonas Wilms

这是一个非常有趣的问题，因为它的措辞方式很特别。如果这些字符串被视为“名称”，那么我的问题是：我们是否希望将“abc”和“zbc”分组为相似？同样，如果我们有Mo或Bo？或者，如果我们有非常相似的名称，比如“Tim”和“Tom”。这些字符串非常相似，但是名称完全不同。或者“Rob”与Bob”？英语有时候非常棘手。 - RichS

我在我的回答中承认，关于我的结果的准确性可以有争议，并且似乎最终会在算法速度和准确性之间进行权衡。如果我们谈论名称作为一组特殊的字符串，那么这就是我按照自己的方式对字符进行加权的原因。 - RichS