4

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

我试过的

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

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

我需要的

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

“失踪”的问题

有人抱怨我不问问题。所以缺少的问号在下一句的末尾。理想情况下，如何在不使用约束的情况下更有效地做到这一点？

4

4 回答 4

5

算法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：仅限于长度为 8 个或更多字符的项目，代表我们的候选项目是列表中其他两个单词的组合。
  3. flatMap：对于每个候选，计算所有可能的子词对，确保每个子词至少有 4 个字符长。由于可能有多个结果，这实际上是一个列表列表，因此将其展平为一个单深列表。
    1. rangeClosed：生成所有整数，表示将在我们将检查的对的第一个单词中的字符数。
    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 类就可以了。

于 2018-09-10T06:03:41.840 回答
1

您可以通过避免使用视图进行大多数子创建并更改它们的位置和限制来改进Erik 的答案：StringCharBuffer

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 进行操作。

于 2018-09-10T10:19:19.107 回答
0

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

于 2018-09-10T04:56:50.403 回答
0

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

构建两个Tries，一个以正常顺序排列候选人，另一个将单词颠倒。

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

我Trie过去在这里发布了一个实现https://stackoverflow.com/a/9320920/823393。

于 2018-09-10T06:02:52.567 回答