从Node.js中的数组中对类似的字符串进行分组

Question

假设我在数组中有一组不同的URL:

var source = ['www.xyz.com/Product/1', 'www.xyz.com/Product/3', 'www.xyz.com/Category/1', 'somestring']

迭代数组并将类似字符串分组到单独数组中的好方法是什么？上面示例中的所需输出将是:

var output = [
    ['www.xyz.com/Product/1', 'www.xyz.com/Product/3'],
    ['www.xyz.com/Category/1'],
    ['somestring']
];

条件

• 其中的所有项目都source可以是随机字符串
• 逻辑必须能够在有意义的时间内对100'000个项目进行比较和分组

我找到了字符串相似性库,它可以将一个字符串与字符串集合进行比较.一种方法是迭代源,将每个项目与源集合进行比较,并应用规则对具有相似分数的项目进行分组.但是,我想这将是非常低效的.

有人可以建议我一个有效的方法来完成我需要的东西吗？

Answer 1

我能想到的最好的解决方案是将字符串相互比较并测试它们之间的差异.有一种算法可以做到这一点,即Levenshtein距离算法:

Levenshtein距离是用于测量两个序列之间差异的字符串度量.非正式地,两个单词之间的Levenshtein距离是将一个单词更改为另一个单词所需的单字符编辑(即插入,删除或替换)的最小数量.

我们可以在fast-levenshtein模块上轻松创建Levenshtein过滤器:

const levenshtein = require('fast-levenshtein'); 

const levenshteinFilter = (source, maximum = 5) => {
  let _source, matches, x, y;
  _source = source.slice();
  matches = [];
  for (x = _source.length - 1; x >= 0; x--) {
    let output = _source.splice(x, 1);
    for (y = _source.length - 1; y >= 0; y--) {
      if (levenshtein.get(output[0], _source[y]) <= maximum) {
        output.push(_source[y]);
        _source.splice(y, 1);
        x--;
      }
    }
    matches.push(output);
  }
  return matches;
}

let source = ['www.xyz.com/Product/1', 'www.xyz.com/Product/3', 'www.xyz.com/Category/1', 'somestring'];
let output = levenshteinFilter(source);
// [ [ 'www.xyz.com/Product/1', 'www.xyz.com/Product/3' ],
//   [ 'www.xyz.com/Category/1' ],
//   [ 'somestring' ] ]

您可以在函数的2参数中定义最大可接受距离(默认为5).