在一个巨大的集合中找到两个字符串的所有连接

Question

给定一组 50k 个字符串，我需要找到所有对 (s, t)，这样 s、t 和 s + t 都包含在这个集合中。

我试过的

，还有一个额外的约束：s.length() >= 4 && t.length() >= 4。这使得可以按长度 4 个前缀和单独的后缀对字符串进行分组。然后对于长度至少为 8 的每个字符串 composed，我使用 composed 的前四个字符和 t 的候选集查找 s 的候选集使用它的最后四个字符。这可行，但它需要查看 3000 万个候选对 (s, t) 才能找到 7k 个结果。

这个数量惊人的候选人来自这样一个事实，即字符串（主要是德语）来自有限词汇表的单词并且单词的开头和结尾通常相同。它仍然比尝试所有 2.5G 对要好得多，但比我希望的要差得多。

我需要什么

由于附加约束可能会被删除并且集会增长，我正在寻找更好的算法。

"missing" 问题

有人抱怨我没有提出问题。所以缺少的问号在下一句的末尾。 如何在不使用约束的情况下更有效地完成这项工作？

Answer 1

可能的解决方案可能是这样。您以第一个字符串作为前缀，第二个字符串作为后缀开始。你遍历每个字符串。如果字符串以第一个字符串开头，则检查它是否以第二个字符串结尾。并一直坚持到最后。为了在检查字母本身是否相同之前节省一些时间，您可以进行长度检查。这几乎就是您所做的，但是通过增加长度检查，您可以 trim 减少一些。至少这是我的看法。

Answer 2

不确定这是否比您的解决方案更好，但我认为值得一试。

建两个Tries，一个是正常顺序的考生，另一个是倒序的单词。

从深度 4 向内向前走 Trie 并使用叶子的剩余部分来确定后缀（或类似的东西）并向后查找 Trie .

我过去曾在此处 Trie 发布过一个实施。

Answer 3

算法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)。有关算法复杂性的更多信息，请参阅 hash table。

说明

将所有长度为四个或更多字符的字符串放入一个散列集中（这需要平均 O(1) 的搜索复杂度）。为了方便起见，我使用了 Guava 的 ImmutableSet。随心所欲。
filter：限制为仅长度为八个或更多字符的项目，代表我们的候选人是列表中其他两个单词的组合。
flatMap：对于每个候选，计算所有可能的子词对，确保每个子词的长度至少为 4 个字符。由于可能有多个结果，这实际上是一个列表列表，因此将其展平为一个单层列表。
1. rangeClosed：生成所有整数，表示我们将检查的对中第一个单词中的字符数。
2. mapToObj：使用每个整数与我们的候选字符串相结合来输出两个项目的列表（在生产代码中你可能想要更清晰的东西，比如两个-属性值class，或适当的现有 class).
3. 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

因此，如果保留所有要检查的项目的运行集，我们可以在基本恒定的时间内找到每个词的候选复合词，然后直接探查剩余词的散列 table：

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 class 或使用一些现有的 Java class 都可以。

Answer 4

您可以通过使用 CharBuffer 视图避免大多数子 String 创建并改变它们的位置和限制来改进：

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);

这是相同的算法，因此不会改变时间复杂度，除非您合并隐藏字符数据复制成本，这将是另一个因素（乘以平均字符串长度）。

当然，只有当您使用与打印匹配项不同的终端操作时，差异才会变得显着，因为打印是一项非常昂贵的操作。同样，当源是大文件上的流时，I/O 将主导操作。除非你进入完全不同的方向，比如使用内存映射并重构此操作以在 ByteBuffers 上运行。

在一个巨大的集合中找到两个字符串的所有连接

Find all concatenations of two string in a huge set

java

algorithm

string-algorithm

我试过的

我需要什么

"missing" 问题