эффективный поиск одной из множества подстрок в большей строке

Question

Я ищу функцию, которая находит подстроку из массива строк («иглы») в более длинной строке («стог сена»). По сути, я хочу, чтобы это работало так, как в этом примере:

var haystack = "abcdefghijklmnopqrstuvwxyz";
var needles = [
  'bcd',
  'pqr',
  'hi',
  'ghi',
  'g',
  'stuv'
  ];

var output = findSubstring (haystack, needles, 2, 20);

Вывод теперь должен иметь:

 {index: 6, which: 3}

, что означает, что он нашел «ghi» (игла 3) в позиции 6. Он получает «ghi», а не «hi», потому что «ghi» начинается раньше в стоге сена, но не получает «g», потому что ghi 'находится ранее в массиве игл.

Это лучшее из того, что я придумал, но оно кажется довольно медленным на очень больших кусках текста и на очень больших массивах игл (что я и использую), и я уверен, что есть что-то лучшее , Это довольно критично для производительности, поэтому мне бы хотелось чего-то быстрее.

Я мог бы придумать лучшие способы сделать это (вероятно, не используя indexOf), и, поскольку (вероятно) это довольно распространенная вещь, у кого-то, имеющего больший опыт работы с такими вещами, мог бы быть лучший путь об этом. (то есть я бы предпочел не изобретать велосипед)

function findSubstring (haystack, needles, startIndex, endIndex) {
  var min = Infinity, best = -1;
  var numNeedles = needles.length;
  if (!startIndex)
    startIndex = 0;

  for (var i=0; i<numNeedles; i++) {
    var index = haystack.indexOf(needles[i], startIndex);
    if (index != -1 && index < min) {
      min = index;
      best = i;
    }
  }
  return (best == -1 || (endIndex && best >= endIndex)) ?
      null : 
      {index: min, which: best};
}

Answer 1

Предложите объединить ваши иглы в одно регулярное выражение: "bcd | pqr | hi | ghi | g | stuv".

Механизм регулярных выражений объединит их в один эффективный конечный автомат.

Answer 2

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm найдет весь произвольный набор строк, где они встречаются.Стоимость - это размер искомой строки плюс постоянная сумма для каждого найденного совпадения, а также время установки, которое является линейным по размеру набора строк, которые нужно найти.Вам нужно будет добавить дополнительную логику, чтобы отменить совпадения, которые вам не нужны.

Answer 3

Взгляните на алгоритм Кнута-Морриса-Пратта, он может быть полезен для вашей проблемы

Answer 4

Если heyStack будет очень большим текстом, тогда «возможно» будет лучше отрезать остальную часть heyStack каждый раз, когда найдена игла:

if (index != -1 && index < min) {
    min = index;
    best = i;
    hayStack = hayStack.substring(0, index + indles[i].length);
}

Answer 5

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

После этого вы просто находите наименьшее число в массиве (это не -1), и это первое совпадение в строке. Затем вы просто обновляете элементы в массиве, которые меньше, чем символ, следующий за совпадением (а не -1). Повторяйте, пока не дойдете до конца строки, или все элементы в массиве будут -1.

Answer 6

Сортировка подстрок в отдельные массивы по первому символу ... массив для слов, начинающихся с 'a', другой массив для 'b' и т. Д.

Превратите вашу строку в массив.

Анализирует массив по одному символу за раз, проверяя соответствие каждого соответствующего массива подстрок. Используйте бинарный поиск, чтобы ускорить проверку массивов подстрок, если это улучшит производительность.