有没有更有效的方法来评估字符串的包含性？

Question

我必须执行这行cose数百万次，我想知道是否有一种方法可以对其进行优化（也许是预先计算的东西？）。

a.contains(b) || b.contains(a)

谢谢

编辑：由contains方法执行的代码已经检查a.length <b.length。

public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
    byte first = str[0];
    int max = (valueCount - strCount);
    for (int i = fromIndex; i <= max; i++) {
        [...]
    }
    return -1;
}

Answer 1

据我了解，这个任务需要检查大约 3500 万个单词中的每对和是否a包含b，反之亦然。有很多对需要检查。ab

您应该能够通过预先计算单词包含哪些 n-gram 来显着缩小搜索范围：如果a包含一些 n-gram，则b必须包含相同的 n-gram if bcontains a。例如，您可以预先计算列表中每个单词包含的所有三元组，同时计算包含给定三元组的所有单词，然后您可以在这些字典中查找单词，并通过一些集合操作得到一小组考生要好好检查。

在伪代码中：

• 选择 n 元语法的大小（见下文）
• 初始化一个Map<String, Set<String>> ngram_to_word
• 第一次迭代：对于a数据集中的 每个单词
  • 迭代所有 n 元语法（例如使用某种滑动窗口）a
  • 对于每个，添加a到包含这些 n 元语法的单词集合中ngrams_to_words
• 第二次迭代：对于a数据集中的 每个单词
  • 再次获取所有 n 元语法a包含的内容
  • 对于其中的每一个，获取包含该 n-gram 的单词集ngrams_to_words
  • 获取这些单词集的交集
  • 对于b该交集中包含所有 n 元语法的每个单词a（但可能以不同的顺序或数量），正确检查是否b包含a

根据这些 n 元语法（例如二元语法、三元语法等）中的字母数量，它们在时间和空间上的预计算成本会更高，但效果也会更大。在最简单的情况下，您甚至可以预先计算哪些单词包含给定字母（即“1-grams”）；这应该很快，并且已经相当大地缩小了要检查的单词范围。当然，n-gram 不应短于数据集中最短的单词，但您甚至可以使用两个长度的 n-gram，例如使用两个映射letter_to_words和trigrams_to_words。