Поиск, если строка содержит любую строку в коллекции

Ответ 1

Можно значительно ускорить его с помощью алгоритма Ахо-Корасика.

Вы можете построить автомат Aho-Corasick для коллекции, используя O (общая длина всех строк в коллекциях) время и пространство. Тогда можно будет проверить, является ли одна из строк в коллекции подстрокой заданной строки S в O (S.lenght), пройдя этот автомат.

Ответ 2

// Make a regex pattern (once only):
StringBuilder pattern = new StringBuilder();
for (String sought : searchCollection) {
    if (!Util.isNullOrEmpty(sought)) {
        if (pattern.length() != 0) {
            pattern.append('|');
        }
        pattern.append(Pattern.quote(sought));
    }
}
final Pattern PATTERN = Pattern.compile("(" + pattern + ")");

Это создает шаблон альтернатив, например "(abc|def|ghi)". Вы можете рассмотреть поиск без учета регистра.

И в функции containsAny:

Matcher m = PATTERN.matcher(searchString);
return m.find();

Компиляция регулярных выражений относительно умна. Это было бы сопоставимо с использованием дерева поиска вашей коллекции искомых слов: "agent" and "agitator" to ("ag", ("ent", "itator"))

Ответ 3

Это интенсивная работа с ЦП и не долгая работа или блокировка ввода-вывода. Если вы используете Java 8, вы можете использовать параллельные потоки для параллельной обработки, как показано ниже. Этот метод был изменен для использования Collection вместо List, чтобы он был более гибким.

public static boolean containsAny(final String searchString,
        final Collection<String> searchCollection) {
    return searchCollection.stream().parallel()
            .anyMatch(x -> searchString.indexOf(x) > -1);
}

Кроме того, вместо List, a Set следует использовать в качестве базовой структуры данных, чтобы дублировать записи, если они есть, будут устранены.

Ответ 4

Вы можете завершить поиск примерно через 2/3 времени, используя алгоритм Aho Corasick.

Принятый ответ от @user2040251 среди других (включая меня) предложил алгоритм Ахо Корасика.

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

@Vlad создал возможный набор тестов для оценки некоторых предлагаемых решений.

Тесты, выполненные @Marco13 в реализации Java в http://ahocorasick.org/, показывают, что ваша первоначальная реализация была быстрее.

Ваши комментарии предоставили существенные дополнительные сведения о проблеме, которую вы пытаетесь решить:

• Примерно 30 строк для поиска
• Строки для поиска длиной от 10 до 40 символов.
• Строка для поиска обычно составляет около 100 символов.
• Строка, которую вы ищете, - это путь к файлу.

Я сделал пару быстрых изменений в @Vlad gist, чтобы лучше соответствовать специфике описанной вами проблемы.

Ранее я прокомментировал, что другие протестированные Ахо-Корасиком испытания находили все возможные матчи. Метод, который возвращался после первого совпадения, был намного быстрее. Чтобы узнать, была ли моя интуиция правильной, я создал ветку Robert Bor java Aho -Corasick. Эта ветвь теперь слита в Ахо-Корасик!

• Завершено 100000 содержитAny в 4337 мс (avg 0 мс)
• Завершено 100000 содержитAnyWithRegex в 41153 мс (avg 0 мс)
• Завершено 100000 содержитAnyWithOffset в 23624 мс (avg 0 мс)
• Завершено 100000 содержитAnyAhoCorasickDotOrg в 7956 мс (avg 0 мс)
• Завершено 100000 содержитAnyAhoCorasickDotOrgMatches в 5351 мс (avg 0 мс)
• Завершено 100000 содержитAnyAhoCorasickDYoo в 2948 мс (avg 0 мс)
• Завершено 100000 содержитAnyHospool в 7052 мс (avg 0 мс)
• Завершено 100000 содержит AnyRaita в 5397 мс (avg 0 мс)
• Завершено 100000 содержитAnyJava8StreamParallel в 8285 мс (avg 0 мс)

Я также реализовал метод, который выполнял каждый поиск в своем потоке. Эта реализация была ужасной и выполнялась примерно в 10 раз медленнее.

Обновление: С момента моего первоначального тестирования я столкнулся с Еще быстрее Aho-Corasick реализация.

Я включил контрольный пример реализации параллельного потока Java 8, предложенный @GladwinB, а также две com.eaio.stringsearch.

По-прежнему можно получить прибыль. В этой статье, например, описывается набор вариантов соответствия Aho-Corasick, который кажется подходящим для вашей проблемы. К более быстрому соответствию строк для обнаружения вторжений

Ответ 5

Можете ли вы попробовать с этим решением:

    final String[] searchList = searchCollection.toArray(new String[0]);
    Arrays.sort(searchList, new Comparator<String>() {
        @Override
        public int compare(final String o1, final String o2) {
            if (o1 == null && o2 == null) {
                return 0;
            }
            if (o1 == null || o1.isEmpty()) {
                return 1;
            }
            if (o2 == null || o2.isEmpty()) {
                return -1;
            }
            return o1.compareTo(o2);
        }
    });
    final int result = Arrays.binarySearch(searchList, searchString);
    return result >= 0 ? true : false;

Ответ 6

Сравните с этим своего рода инвертированную и оптимизированную версию:

  public static boolean containsAny(String searchString, List<String> searchCollection) {
    for (int offset = 0; offset < searchString.length(); offset++) {
      for (String sought: searchCollection) {
        int remainder = searchString.length() - offset;
        if (remainder >= sought.length && searchString.startsWith(sought, offset)) {
          return true;
        }
      }
    }
    return false;
  }

Обратите внимание на использование startWith со смещением.

Ответ 7

Я считаю, что наиболее подходящая структура данных для этого - это Дерево суффикса. Для строки размера n, построение дерева принимает Theta(n) и ищет в нем подстроку длиной m, принимает O(m).

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

Ответ 8

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

Не поймите меня неправильно, ваше узкое место - это строка indexOf. Похоже, что на нее приходится 95% обработки. Но если другие структуры данных не помогают (я попробовал готовый Aho-Corasick Trie, и это было в два раза медленнее), вот что проверить...

Комментарий об использовании indexOf, а не содержит сомнительный. В моих тестах. Я видел около 1,5 млн поисков в секунду с "содержит" и только около 700 тыс. С помощью indexOf. Если у вас есть те же результаты, это удвоит скорость прямо там.

Изменить

// This is a performance optimization of contains.
if (searchString.indexOf(stringInCollection, 0) > -1) {

[назад] на

if (searchString.contains(stringInCollection)) {

Если вам интересно, трю, с которым я тестировал, здесь: http://ahocorasick.org/, и код довольно прост. Проблема, которую я видел, это то, что у нее нет функции для раннего выхода после первого совпадения. Он анализирует всю строку и находит все совпадения. Это было быстрее, чем indexOf() для случаев, когда совпадений не было (830K/sec), но все еще медленнее, чем contains().

Ответ 9

@Yrlec из вашего комментария, что searchCollection можно считать постоянным с небольшим количеством изменений, вы можете сортировать его и кэшировать, или вы можете реализовать собственный класс List, который хранит ссылку на отсортированные элементы, которые добавляются в он.

Причиной этого является то, что у вас есть сортировка searchCollection, тогда вы можете использовать метод compareTo для String и уменьшить количество итераций, тем самым увеличивая производительность вашего метода.

public static boolean containsAny(String searchString, List<String> searchCollectionSorted) {
    int size = searchCollectionSorted.size();
    for (int i = 0; i < size; i++) {
            String stringInCollection = searchCollectionSorted.get(i);
            if (!Util.isNullOrEmpty(stringInCollection)) {
                if(stringInCollection.compareToIgnoreCase(searchString) > 0) {
                    if (searchString.startsWith(stringInCollection) {
                            return true;
                    } else {
                              // No point of iterating if we reach here as the searchstring is greater and hence iterations are saved improving performance
                            break;
                    }
                }
            }
        }    return false;
}

Ответ 10

Вы можете использовать структуру данных HashSet. Но хэш-набор не позволит дублировать. Например, вы не можете иметь строку "foo" дважды в HashSet.

С положительной стороны сложность должна быть O (1).

http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

Ответ 11

TreeSet, HashSet или PrefixTree - неплохие решения. Вы должны предпочесть PrefixTree, если вам нужно будет найти, существует ли данный префикс в коллекции (сложность O (длина (S)), в противном случае используйте HashSet. http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html