集团在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件物品在有意义的时间

我找到了string-similarity library，它提供了将一个字符串与字符串集合进行比较的可能性。一种方法是迭代源代码，将每个项目与源集合进行比较，并应用规则对具有相似分数的项目进行分组。不过我想这样做效率很低。

有人可以建议我一种有效的方法来完成我所需要的吗？

Answer 1

我能想到的最佳解决方案是将字符串与对方进行比较，并测试它们的不同之处。存在着这样做，这是Levenshtein distance算法的算法：

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

---

我们可以很容易对fast-levenshtein module顶部创建的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）。

Answer 2

你没有充实你的意图，但如果面临从随机干草堆中找到最近邻居的选定项目的任务，我可能会尝试构建一棵哈希树。或者，这可能是作弊，我会让图书馆为我做。 lunr.js基本上是一个纯JS的lucene索引，我会推入你的数组，并查询它以获得相似的字符串。我之前在lunr.js中有非常大的数据集，并且性能非常高，在附近的elasticsearch集群上没有蜡烛，但仍然令人印象深刻。

如果你提供了一些你想要做什么的更多细节，我可以给出一些更多的细节，甚至可能是一些示例代码。

Answer 3

如果源代码包含所有随机地址，则下面的函数将给出问题中所示的预期输出。

function filter (source) { 
    var output = [] 
    source.forEach((svalue) => { 
    if (output.length === 0) { 
     output.push([svalue]) 
    } else { 
     var done = false 
     output.forEach((tarr) => { 
     if (!done) { 
      tarr.forEach((tvalue) => { 
      if (svalue.indexOf('/') > -1 && svalue.split('/').slice(0, 2).join('/') == tvalue.split('/').slice(0, 2).join('/')) { 
       tarr.push(svalue) 
       done = true 
      } 
      }) 
     } 
     }) 
     if (!done) { 
     output.push([svalue]) 
     done = true 
     } 
    } 
    }) 
    return output 
} 

Answer 4

MinHash（https://en.wikipedia.org/wiki/MinHash）？

它旨在查找重复的网页。所以我想你可以将url.split（'/'）作为一组单词处理。

Answer 5

根据您的示例测试，我建议您实施Radix Tree or Prefix Tree来存储字符串。之后，您可以定义一个标准来对这些字符串进行聚类。