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

Question

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

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

谢谢

编辑：包含方法执行的代码已经检查了 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是否包含每对a的b，反之亦然，并从一组大约 3500 万个单词中b。有很多对要检查。

您应该能够通过预先计算单词包含的 n 元语法来缩小搜索范围：如果a包含一些 n-gram，那么如果b包含a，则必须包含相同的 n-gramb。例如，您可以预先计算列表中每个单词包含的所有三元组，同时预先计算包含给定三元组的所有单词，然后您可以在这些字典中查找单词，并通过一些集合操作获得一小组候选正确检查。

在伪代码中：

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

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