集團在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來存儲字符串。之後，您可以定義一個標準來對這些字符串進行聚類。