从Node.js中的数组中分组类似的string
比方说，我有一个数组中的不同的URL的集合：
var source = ['www.xyz.com/Product/1', 'www.xyz.com/Product/3', 'www.xyz.com/Category/1', 'somestring'] 迭代数组并将类似的string分组到一个单独的数组中是什么方法？ 上面例子中的期望输出是：
var output = [ ['www.xyz.com/Product/1', 'www.xyz.com/Product/3'], ['www.xyz.com/Category/1'], ['somestring'] ];
条件
-
source内的所有项目都可以是随机string - 逻辑必须能够在有意义的时间比较和分组大约100000个项目
我find了string相似性库 ，它可以将一个string与一个string集合进行比较。 一种方法是迭代源代码，将每个项目与源集合进行比较，并应用规则对具有相似分数的项目进行分组。 不过我想这样做效率太差。
有人可以build议我一个有效的方法来完成我所需要的？
我能想到的最好的解决办法是比较string和testing他们是如何不同。 有一种algorithm可以做到这一点，即Levenshtein距离algorithm：
Levenshtein距离是测量两个序列之间差异的string度量。 非正式地，两个单词之间的Levenshtein距离是将一个单词换成另一个单词所需的单字符编辑（即插入，删除或replace）的最小数量。
我们可以很容易地在快速通道模块上创build一个Levenshteinfilter：
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）。
如何MinHash（ https://en.wikipedia.org/wiki/MinHash ）？
它旨在查找重复的网页。 所以我想你可以url.split（'/'），并把每个url作为一组单词。
你没有充实你的意图，但是如果面临从随机的干草堆中find最近邻居的select项目的任务，我可能会尝试构build一个哈希树。
或者，这可能是作弊，我会让图书馆为我做。 lunr.js基本上是一个纯粹的JS lucene索引，我会推入你的数组，然后查询，得到类似的string。 我以前在lunr.js里有非常大的数据集，而且性能非常高，在附近find一个弹性search集群，但是仍然令人印象深刻。
如果你提供了一些你想要做的更多的细节，我可以给出一些更多的细节，甚至可能是一些示例代码。
如果源代码包含所有随机地址，则下面的函数将给出问题中所示的预期输出。
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 }
根据您的示例testing，我可以build议您实施基数树或前缀树来存储string。 之后，您可以定义一个标准来对这些string进行聚类。