grupowe podobne sznurki z tablicy w node.js

Question

Powiedzmy mam zbiór różnych adresów URL w tablicy:

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

Jaki byłby dobry sposób iteracyjne nad tablicy i grup podobnych do strun osobna tablica? Pożądana wyjście z powyższego przykładu będzie:

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

Warunki

• Wszystkie elementy w source może być losowe ciągi
• Logika musi być w stanie porównać i grupa około 100' 000 produktów w znaczącym czasie

Znalazłem string-similarity library, co daje możliwość porównania jednego ciągu z kolekcją ciągów. Jednym ze sposobów jest powtórzenie źródła, porównanie każdego elementu z kolekcją źródłową i zastosowanie reguły do ​​grupowania elementów o podobnym wyniku. Jednak myślę, że byłoby to okropnie nieefektywne.

Czy ktoś może zaproponować mi skuteczny sposób osiągnięcia tego, czego potrzebuję?

Answer 1

Najlepsze rozwiązanie, jakie mogę wymyślić, to porównać ze sobą strun i sprawdzić, jak są różne. Jest to algorytm, który robi to, co jest algorytm Levenshtein distance:

Odległość Levenshteina jest ciągiem metryki do pomiaru różnicy między dwiema sekwencjami. Nieformalnie odległość Levenshteina między dwoma słowami to minimalna liczba edycji jednoznakowych (tj. Insercje, delecje lub substytucje) wymaganych do zmiany jednego słowa na inny.

---

Możemy łatwo utworzyć filtr Levenshteina na szczycie fast-levenshtein module:

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' ] ] 

Można zdefiniować maksymalną dopuszczalną odległość w 2 argumentu funkcji (domyślnie 5).

Answer 2

Nie masz zamiaru wypracować swojego zamiaru, ale jeśli będziesz musiał znaleźć wybrane przedmioty najbliższej sąsiadki z losowego stogu siana, prawdopodobnie spróbuję zbudować drzewo z haszami.

Albo, a to może być oszustwo, pozwoliłbym bibliotece zrobić to za mnie. lunr.js jest po prostu czystym indeksem JS lucene, wepchnęłabym do niego tablicę i zapytałabym o to, aby uzyskać podobne ciągi. Wcześniej miałem dość duże zbiory danych w serwisie lunr.js i jest to wysoce wydajne, nie ma świec, by mieć klastry z elastycznym wyszukiwaniem w pobliżu, ale nadal cholernie imponujące.

Jeśli podasz więcej szczegółów na temat tego, co próbujesz zrobić, mogę podać więcej szczegółów, a może nawet przykładowy kod.

Answer 3

Jeśli źródło zawiera wszystkie losowe adresy URL, poniżej funkcja wyświetli oczekiwane wyniki, jak pokazano w pytaniu.

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

Co powiecie na MinHash (https://en.wikipedia.org/wiki/MinHash)?

Został zaprojektowany do wyszukiwania duplikatów stron internetowych. Więc przypuszczam, że możesz url.split ("/") i traktować każdy adres URL jako zestaw słów.

Answer 5

Na podstawie przykładowych testów mogę zaproponować wprowadzenie Radix Tree or Prefix Tree do przechowywania ciągów. Następnie możesz zdefiniować kryteria zgrupowania tych łańcuchów.