Группируйте аналогичные строки из массива в Node.js

Скажем, у меня есть набор различных 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 элементов в значимое время.

Я нашел библиотеку схожести строк, которая дает возможность сравнить одну строку с коллекцией строк. Один из способов - перебрать исходный код, сравнить каждый элемент с исходной коллекцией и применить правило для группировки элементов с аналогичным счетом. Однако, я думаю, это было бы ужасно неэффективно.

Может ли кто-нибудь предложить мне эффективный способ выполнить то, что мне нужно?

Ответ 1

Лучшее решение, о котором я могу думать, - сравнить строки друг с другом и проверить, насколько они отличаются друг от друга. Существует алгоритм, который выполняет алгоритм Levenshtein distance:

Расстояние Левенштейна является строковой метрикой для измерения разница между двумя последовательностями. Неформально расстояние Левенштейн между двумя словами - минимальное количество односимвольных изменений (то есть вставки, удаления или замены), необходимые для изменения одного слово в другое.

Мы можем легко создать фильтр Левенштейна поверх модуль fast-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).

Ответ 2

Как насчет MinHash (https://en.wikipedia.org/wiki/MinHash)?

Он был разработан для поиска повторяющихся веб-страниц. Поэтому я предполагаю, что вы можете url.split('/') и обрабатывать каждый URL как набор слов.

Ответ 3

Вы не воплощаете свои намерения, но если перед вами стоит задача найти выбранные предметы ближайших соседей из случайного стога сена, я бы, вероятно, попытался построить дерево хешей.

Или, и это может быть обманом, я позволю библиотеке сделать это для меня. lunr.js - это в основном чистый индекс JS lucene, я бы подталкивал ваш массив к нему и запрашивал его, чтобы получить аналогичные строки. Раньше у меня были довольно большие наборы данных в lunr.js, и он очень эффективен, и нет свечи, когда поблизости есть кластер elasticsearch, но все же впечатляющий.

Если вы предоставите более подробную информацию о том, что вы пытаетесь сделать, я мог бы дать более подробную информацию и, возможно, даже пример кода.

Ответ 4

Если источник содержит все случайные URL-адреса, функция ниже даст ожидаемый результат, как показано в вопросе.

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
}

Ответ 5

Основываясь на ваших примерах тестов, я могу предложить вам реализовать дерево Radix или дерево префикса для хранения строк. После этого вы можете определить критерии для группировки этих строк.