Для входной строки с несколькими словами - какой самый эффективный способ проверить, начинаются ли какие-либо из них с какой-либо другой строки?

Question

Мне нужно реализовать метод java, который получает набор строк и входную строку и возвращает подмножество строк, содержащее все строки из исходного набора, любое слово которого начинается с входной строки. Например, если строка «Переполнение стека», а ввод «Сверх», она должна быть в подмножестве. Но если строка «Переполнение стека», а вход «поток», она не должна быть в подмножестве.

public Set<String> findMatches (Set<String> names, String input);

Поскольку размер набора огромен (100 миллионов), мне нужно сделать это в самый эффективный способ. Три способа, которые я до сих пор пробовал, привели к сбивающим с толку результатам:

1. Разделить каждую строку на пустое место и получить массив строк, а затем, на каждом из элементов в массиве - Вызвать метод StarsWithWithWith.
2. Для каждой строки, проверить, начинается ли она с ввода, содержит "" + input (пробел, за которым следует ввод).
3. Regex.

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

Итак, какой из них будет наиболее эффективным? Есть ли другой вариант, о котором я не подумал?

Answer 1

Нужная вам структура данных: tr ie.

В этом объяснении я имею в виду, что t_i - это небольшие строки, которые должны быть префиксами слов, а s - это большая строка, которая содержит много слов, разделенных пробелами.

Просто добавьте все t_i в tr ie. Затем выполните итерацию по s символам:

• Если вы встретите пробел, go до root из tr ie.

• Если вы встречаете письмо, go от текущего узла tr ie до его дочернего элемента, связанного с этим письмом. Если пути нет, просто пропустите все буквы, пока не встретите следующий пробел. Если вы достигнете узла, который связан с одним из t_i, добавьте эту строку в ответ.

Этот алгоритм работает в O(sum(length(t_i)) + length(s)). При необходимости я могу написать некоторый код.

Все ваши алгоритмы и алгоритмы, предложенные @DudeDoesThings, работают в O(sum(length(t_i)) * length(s)), что намного медленнее, особенно когда речь идет о больших входах.

Answer 2

Если у вас действительно есть много миллионов строк и вам нужна эффективность, я бы советовал не использовать ни split, ни регулярные выражения Возможно, вы захотите взглянуть на Stream API, особенно на параллельные потоки, если вам важна скорость вычислений:

public static void main(String[] args) {
    Set<String> s = Arrays.stream(new String[] {
        "Stack Overflow",
        "Flowover Stack",
        "Overflow Stack",
        "Stackover Flow"
    }).collect(Collectors.toSet());
    System.out.println(findMatches(s, "Over"));
}

public static Set<String> findMatches (Set<String> names, String input) {
    int inputLength = input.length();
    return names.stream().parallel().filter(name -> {
        int offset = 0;
        while (offset >= 0 && offset + inputLength < name.length()) {
            if (name.startsWith(input, offset)) {
                return true;
            }
            offset = name.indexOf(" ", offset);
            if (offset != -1) {
                offset++;
            }
        }
        return false;
    }).collect(Collectors.toSet());
}