Подтвердить что ты не робот

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

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

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

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

  //do some stuff
  } else continue;
}

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

Спасибо,

Эллиот

4b9b3361

ОТВЕТЫ

Ответ 1

Я думаю, что вы ищете такой алгоритм, как Rabin-Karp или Aho-Corasick, которые предназначены для параллельного поиска для большого количества подстрок в тексте.

Ответ 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|), что асимптотически лучше, чем наивная реализация.

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

bidTextSet.retainAll(mainWordsSet);

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

Ответ 6

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

Ответ 7

Я боюсь, что это вообще неэффективно!

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

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

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

Ответ 8

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

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

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