时间戳

首页 > 解决方案 > 是否有更有效的方法来评估字符串的包含情况？

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

问题描述

我必须执行这行 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;
}

标签： javaperformancemath

解决方案

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

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

在伪代码中：

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

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

推荐阅读