Алгоритм 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). См. хеш-таблицу для получения дополнительной информации об алгоритмической сложности.
Пояснение
- Поместите все строки длиной четыре или более символов в набор хэшей (который требует средней сложности O (1) для поиска). Я использовал гуаву
ImmutableSet для удобства. Используйте все, что вам нравится.
filter: ограничивается только элементами длиной восемь или более символов, представляющих наших кандидатов в состав двух других слов в списке. flatMap: Для каждого кандидата вычислите все возможные пары подслов, убедившись, что длина каждого из них не менее 4 символов. Поскольку может быть несколько результатов, это фактически список списков, поэтому сведите его в один глубокий список.
rangeClosed: Генерация всех целых чисел, представляющих количество символов, которое будет в первом слове пары, которую мы будем проверять. mapToObj: Используйте каждое целое число в сочетании с нашей строкой-кандидатом для вывода списка из двух элементов (в производственном коде вы, вероятно, захотите что-то более понятное, например, класс значений с двумя свойствами или соответствующий существующий класс). filter: ограничение только парами, в которых есть оба.
map: немного подвести итоги. 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.