Самый эффективный способ поиска массива строк в другой строке

Question

У меня есть большой массив строк, который выглядит примерно так: String temp [] = new String [200000].

У меня есть другая строка, назовем ее bigtext.Что мне нужно сделать, так это перебрать каждую запись temp, проверить, найдена ли эта запись в большом тексте, а затем выполнить некоторую работу на ее основе.Итак, скелетный код выглядит примерно так:

for (int x = 0; x < temp.length; x++) {
  if (bigtext.indexOf(temp[x]) > -1 {

  //do some stuff
  } else continue;
}

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

Спасибо,

Эллиот

Answer 1

Я думаю, что вы ищете алгоритм типа Рабина-Карпа или Ахо-Корасика , который предназначен для параллельного поиска большого количества подстрок в тексте. .

Answer 2

Обратите внимание, что ваша текущая сложность равна O(|S1|*n), где |S1| - это длина bigtext, а n - количество элементов в вашем массиве, поскольку каждый поиск на самом деле O(|S1|).

.

Путем построения дерева суффиксов из bigtext и итерации по элементам в массиве вы можете довести эту сложность до O(|S1| + |S2|*n), где |S2| - это длина самой длинной строки в массиве. Если предположить |S2| << |S1|, это может быть намного быстрее!

Построение дерева суффиксов - O(|S1|), а каждый поиск - O(|S2|). Вам не нужно проходить через bigtext, чтобы найти его, просто на соответствующем куске дерева суффиксов. Поскольку это делается n раз, вы получите в сумме O(|S1| + n*|S2|), что асимптотически лучше, чем наивная реализация.

Answer 3

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

Вы также можете сократить время, затрачиваемое на параллелизацию итерации.

Answer 4

Эффективность во многом зависит от того, что ценно для вас.

Готовы ли вы увеличить память за меньшее время? Готовы ли вы увеличить время для эффективной обработки больших массивов данных? Готовы ли вы увеличить конкуренцию за ядра процессоров? Готовы ли вы выполнить предварительную обработку (возможно, одну или несколько форм индексации), чтобы сократить время поиска в критическом разделе.

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

Answer 5

Используйте алгоритм поиска, такой как Бойер-Мур.Google Boyer Moore, и в нем много ссылок, объясняющих, как это работает.Например, есть пример Java .

Answer 6

Альтернативным подходом может быть маркировка текста - скажем, деление на пунктуацию.Затем поместите эти токены в Set, а затем найдите пересечение с основным контейнером.

Вместо массива, удерживайте слова в Set.Пересечение можно вычислить, просто выполнив

bidTextSet.retainAll(mainWordsSet);

. Остаться будут слова, которые встречаются в bigText в вашем «словаре».

Answer 7

Боюсь, это неэффективно в любом случае!

Чтобы выбрать правильный алгоритм, вам нужно дать несколько ответов:

1. Что можно вычислить внелиния?То есть bigText известно заранее?Я думаю, temp не от его имени.
2. Вы действительно ищете слова?Если это так, индексируйте их . Фильтр Блума тоже может помочь.
3. Если вам нужно немного нечеткости, может ли стебель или soundex справиться с этой задачей?

Придерживаться строгого теста на включениевы можете создать trie из вашего temp массива.Это предотвратит поиск одной и той же подстроки несколько раз.

Answer 8

То, что - это очень эффективный подход.Вы можете немного улучшить его, только оценив temp.length один раз

for(int x = 0, len = temp.length; x < len; x++)

Хотя вы не предоставляете достаточно подробных сведений о вашей программе, вполне возможно, что вы сможете найти более эффективный подход, изменив дизайн вашей программы.