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

Question

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

我试过的

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

这个令人惊讶的大量候选人来自这样一个事实,即字符串是来自有限词汇表的(主要是德语)单词,而单词的开头和结尾通常是相同的.它仍然比尝试所有2.5G对要好得多,但比我希望的要糟糕得多.

我需要的

由于附加约束可能会被删除而且集合会增长,我正在寻找更好的算法.

"失踪"的问题

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

Answer 1

算法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:对于每个候选者,计算所有可能的子词对,确保每个子词长度至少为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类就可以了.