检查非常非常长的字符串时发生 Java 堆空间错误

Question

我有一个指定的字符串，我需要检查该字符串是否有指定长度的相同部分。例如，如果字符串为“abcdab”且长度指定为 2，则该字符串中的相同部分为“ab”(始终查找重复次数最多的部分)。为了获得最佳性能，我重新设计了算法 4-5 次，但最终，如果 String 的长度超过 1m+，则会抛出 Java 堆空间错误。

所以我的问题是:如何解决错误，也许有另一种方法来检查相同的部分，或者也许有其他方法来构建整个算法。我想出了一种可能的解决方案，但它的工作速度非常慢，所以我只要求与我当前算法一样快的解决方案，或者甚至更快的解决方案。这是当前代码:

int length = 2;
String str = "ababkjdklfhcjacajca";
ArrayList<String> h = new ArrayList<String>(); 
h.add(str.substring(0, length));
ArrayList<Integer> contains = new ArrayList<Integer>();
contains.add(1);

String c;
for (int g = 1; g < str.length()-length+1; g++) {
    c = str.substring(g, length+g);
    for (int e = 0; e < h.size(); e++) {
        if (h.get(e).charAt(0) == c.charAt(0) && h.get(e).charAt(length-1) == c.charAt(length-1)) {
            if (h.get(e).equals(c)) {
                contains.set(e, contains.get(e)+1);
                break;
            }
        }
        else if (e+1 == h.size()) {
            h.add(c);
            contains.add(1);
            break;
        }
    }

}

ArrayList h 存储字符串的每个唯一部分，ArrayList 包含表示字符串的每个唯一部分的重复次数。String c 是主要问题(这里是java堆空间点)。它在存储到 ArrayList h 之前逐渐表示字符串的每个部分(如果该 c 是唯一的)。之后，我将使用 ArrayLists 找到最重复的列表并打印它们。

Answer 1

如果您想在时间和内存方面高效地进行搜索，我建议您执行以下操作:

1. 首先，创建一个简单的字符直方图，其中包含每个字符出现的次数。如果子字符串的第一个字符的出现次数少于我们迄今为止找到的最常见子字符串，我们可以跳过该子字符串。

2. 我们不使用创建包含字符内容副本的子字符串，而是使用 CharBuffer其中wraps字符串并调整其 position和 limit来表示一个子序列。当然，一旦缓冲区作为键存储在映射中，我们就不能修改它，因此当每个键存储在映射中时，我们为每个键创建一个新的缓冲区。因此，我们最多为每个不同的子字符串创建一个 CharBuffer，这些缓冲区仍然只包装 String 而不是复制任何字符数据

public static Map<String,Integer> mostCommonSubstring(String s, int len) {
    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);
    int most = 0;
    HashMap<Buffer, Integer> subStrings = new HashMap<>();
    CharBuffer cb = CharBuffer.wrap(s);
    for(int ix = 0, e = s.length()-len; ix <= e; ix++) {
        if(charHistogram[s.charAt(ix)] < most) continue;
        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);
        if(num == 1) cb = CharBuffer.wrap(s);
        if(num > most) most = num;
    }
    final int mostOccurences = most;
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));
}

前两行创建我们的直方图

    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);

循环内

        if(charHistogram[s.charAt(ix)] < most) continue;

检查当前子字符串的第一个字符的出现次数是否少于我们迄今为止找到的最常见字符串，并在这种情况下跳过后续测试。

下一行调整当前缓冲区来表示子字符串，并更新映射，将缓冲区与 1 关联(如果不存在)，或者将 1 添加到子字符串的计数中现有的映射。

        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);

我们使用返回值来检测merge操作是否在映射中创建了一个新的关联，只有当结果为1时才会出现这种情况。在这种情况下，我们之后不能修改缓冲区，因此，创建一个新的

        if(num == 1) cb = CharBuffer.wrap(s);

然后，我们使用结果来跟踪最高出现次数

        if(num > most) most = num;

循环后的最后一步很简单。我们已经拥有最高的出现次数，过滤映射以保留具有匹配编号的条目(可能存在平局)并创建一个新映射，现在将缓冲区转换为 String 实例，就像我们所做的那样。不想保留对原始 String 的引用，而且它只影响少数结果子字符串。

    final int mostOccurences = most; // needed because most is not “effectively final”
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));