Найти все конкатенации двух строк в огромном наборе

Алгоритм 1. Тестируйте пары, а не одиночки

Один из способов может заключаться в том, что вместо того, чтобы работать со всеми возможными парами со всеми возможными составными строками, содержащими эти пары, работать со всеми возможными составными строками и посмотреть, содержат ли они пары. Это меняет проблему с n^2 поиска (где n - количество строк> = 4 символа) на m * n поиска (где m - средняя длина всех строк> = 8 символов, минус 7, а n теперь количество строк> = 8 символов). Вот одна из реализаций этого:

int minWordLength = 4;
int minPairLength = 8;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downstream", "stream"
   )
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

strings
   .stream()
   .filter(s -> s.length() >= minPairLength)
   .flatMap(s -> IntStream
      .rangeClosed(minWordLength, s.length() - minWordLength)
      .mapToObj(splitIndex -> ImmutableList.of(
         s.substring(0, splitIndex),
         s.substring(splitIndex)
      ))
      .filter(pair ->
          strings.contains(pair.get(0))
          && strings.contains(pair.get(1))
      )
   )
   .map(pair ->
      pair.get(0) + pair.get(1) + " = " + pair.get(0) + " + " + pair.get(1)
   )
   .forEach(System.out::println);

Дает результат:

downstream = down + stream

Это имеет среднюю алгоритмическую сложность m * n, как показано выше. Итак, по сути, O(n). В худшем случае O(n^2). См. хеш-таблицу для получения дополнительной информации об алгоритмической сложности.

Объяснение

1. Поместите все строки длиной четыре или более символа в хэш-набор (который занимает в среднем O (1) сложность поиска). Для удобства я использовал ImmutableSet Гуавы. Используйте все, что вам нравится.
2. filter: Ограничение только элементами, длина которых составляет восемь или более символов, представляющих наших кандидатов на то, чтобы быть составной частью двух других слов в списке.
3. flatMap: For each candidate, compute all possible pairs of sub-words, ensuring each is at least 4 characters long. Since there can be more than one result, this is in effect a list of lists, so flatten it into a single-deep list.
   1. rangeClosed: Generate all integers representing the number of characters that will be in the first word of the pair we will check.
   2. mapToObj: используйте каждое целое число в сочетании со строкой кандидата для вывода списка из двух элементов (в производственном коде вам, вероятно, понадобится что-то более четкое, например, класс значений с двумя свойствами или соответствующий существующий класс).
   3. filter: Ограничить только парами, в которых оба присутствуют в списке.
4. map: Немного улучшили результаты.
5. forEach: вывод на консоль.

Выбор алгоритма

Этот алгоритм настроен на слова, которые намного короче, чем количество элементов в списке. Если бы список был очень коротким, а слова были бы очень длинными, то переключение обратно на задачу композиции вместо задачи декомпозиции сработало бы лучше. Учитывая, что размер списка составляет 50 000 строк, и маловероятно, что длина немецких слов превышает 50 символов, это фактор 1: 1000 в пользу этого алгоритма.

С другой стороны, если бы у вас было 50 строк, длина которых в среднем составляла 50 000 символов, другой алгоритм был бы гораздо более эффективным.

Алгоритм 2. Сортировка и сохранение списка кандидатов

Один алгоритм, о котором я подумал некоторое время, заключался в сортировке списка, зная, что если строка представляет начало пары, все строки-кандидаты, которые могут быть одной из ее пар, будут сразу после нее по порядку среди набора элементов, которые начинаются с этой строки. Сортировка моих сложных данных выше и добавление некоторых мешающих факторов (downer, downs, downregulate) мы получаем:

a
abc
abcdef
bear
bearhug
cur
curl
curlique
def
down ---------\
downs         |
downer        | not far away now!
downregulate  |
downstream ---/
hug
shine
stream
sun
sunshine

Таким образом, если бы был сохранен текущий набор всех проверяемых элементов, мы могли бы найти подходящие композиты практически за постоянное время для каждого слова, а затем напрямую исследовать хеш-таблицу для оставшегося слова:

int minWordLength = 4;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downs", "downer", "downregulate", "downstream", "stream")
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

ImmutableList<String> orderedList = strings
   .stream()
   .sorted()
   .collect(ImmutableList.toImmutableList());
List<String> candidates = new ArrayList<>();
List<Map.Entry<String, String>> pairs = new ArrayList<>();

for (String currentString : orderedList) {
   List<String> nextCandidates = new ArrayList<>();
   nextCandidates.add(currentString);
   for (String candidate : candidates) {
      if (currentString.startsWith(candidate)) {
         nextCandidates.add(candidate);
         String remainder = currentString.substring(candidate.length());
         if (remainder.length() >= minWordLength && strings.contains(remainder)) {
            pairs.add(new AbstractMap.SimpleEntry<>(candidate, remainder));
         }
      }
   }
   candidates = nextCandidates;
}
pairs.forEach(System.out::println);

Результат:

down=stream

Алгоритмическая сложность здесь немного сложнее. Я считаю, что поисковая часть является O(n) средней, с O(n^2) худшим случаем. Самой дорогой частью может быть сортировка, которая зависит от используемого алгоритма и характеристик несортированных данных. Так что используйте это с недоверием, но у него есть возможность. Мне кажется, что это будет намного дешевле, чем создание Trie из огромного набора данных, потому что вы только один раз всесторонне исследуете его и не получите никакой амортизации стоимости сборки.

Кроме того, на этот раз я выбрал Map.Entry, чтобы держать пару. Совершенно произвольно, как вы это делаете. Было бы хорошо создать собственный класс Pair или использовать какой-либо существующий класс Java.

Вы можете улучшить ответ Эрика, избегая большей части создания под-String с использованием CharBuffer представлений и изменяя их положение и ограничение:

Set<CharBuffer> strings = Stream.of(
    "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
    "bear", "hug", "bearhug", "cur", "curlique", "curl",
    "down", "downstream", "stream"
 )
.filter(s -> s.length() >= 4) // < 4 is irrelevant
.map(CharBuffer::wrap)
.collect(Collectors.toSet());

strings
    .stream()
    .filter(s -> s.length() >= 8)
    .map(CharBuffer::wrap)
    .flatMap(cb -> IntStream.rangeClosed(4, cb.length() - 4)
        .filter(i -> strings.contains(cb.clear().position(i))&&strings.contains(cb.flip()))
        .mapToObj(i -> cb.clear()+" = "+cb.limit(i)+" + "+cb.clear().position(i))
    )
    .forEach(System.out::println);

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

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

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

Не уверен, что это лучше, чем ваше решение, но я думаю, что стоит попробовать.

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

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

Ранее я публиковал Trie реализацию здесь, https://stackoverflow.com/a/9320920/823393.