java - 是否有更有效的方法来评估字符串的包含？

Question

我必须执行这行 cose 几百万次，我想知道是否有优化它的方法(也许预先计算一些东西？)。

a.contains(b) || b.包含(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

据我了解任务，你必须检查是否a包含 b每对 a 反之亦然和 b来自一组大约 3500 万个单词。有很多对要检查。

通过预先计算一个单词包含哪些 n-gram，您应该能够大大缩小搜索范围:如果 a包含一些 n-gram，那么 b如果 b 必须包含相同的 n-gram包含 a .你可以例如预先计算列表中每个单词包含的所有三元组，同时计算包含给定三元组的所有单词，然后您可以在这些词典中查找单词，并通过一些集合操作得到一小组候选对象来检查

在伪代码中:

• 为 n-gram 选择一个大小(见下文)
• 初始化Map<String, Set<String>> ngram_to_word
• 第一次迭代:对于每个单词 a在你的数据集中
  • 迭代 a 的所有 n-gram(例如使用某种滑动窗口)
  • 为每个添加a包含 ngrams_to_words 中那些 n-gram 的单词集
• 第二次迭代:对于每个单词 a在你的数据集中
  • 再次获取所有 n-grams a包含
  • 对于其中的每一个，从 ngrams_to_words 中获取包含该 n-gram 的单词集
  • 得到那些词组的交集
  • 对于每个单词 b在那个包含 a 的所有 n-gram 的交叉点中包含(但可能顺序或数量不同)，正确检查是否 b包含 a

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