java - 2 个巨大文件之间的最长公共(public)子字符串 - 内存不足 : java heap space

Question

在此之后我完全被烧坏了，我需要找到两个文件(一个小文件和一个巨大文件)之间最长的公共(public)子字符串。我什至不知道从哪里开始搜索，这就是我到目前为止所拥有的

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class MyString
{
    public static void main (String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new FileReader("MobyDick.txt"));
        BufferedReader br2 = new BufferedReader(new FileReader("WarAndPeace.txt"));
        String md, wp;
        StringBuilder s = new StringBuilder();
        while ((md = br.readLine()) != null)
        {
            s.append(md).append(" ");
        }
        md = s + "";
        s.setLength(0);
        while ((wp = br2.readLine()) != null)
        {
            s.append(wp).append(" ");
        }
        wp = s + "";
        s.setLength(0);

        md = md.replaceAll("\\s+", " "); //rids of double spaces
        wp = wp.replaceAll("\\s+", " "); //rids of double spaces
    }
}

到目前为止，我所做的是将每个文件放入字符串生成器中，然后放入字符串中以消除双空格(它在 MobyDick.txt 中出现过很多次)。我找到了这段代码

public static String longestSubstring(String str1, String str2) {

StringBuilder sb = new StringBuilder();
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
  return "";

// ignore case
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// java initializes them already with 0
int[][] num = new int[str1.length()][str2.length()];
int maxlen = 0;
int lastSubsBegin = 0;

for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j)) {
if ((i == 0) || (j == 0))
   num[i][j] = 1;
else
   num[i][j] = 1 + num[i - 1][j - 1];

if (num[i][j] > maxlen) {
  maxlen = num[i][j];
  // generate substring from str1 => i
  int thisSubsBegin = i - num[i][j] + 1;
  if (lastSubsBegin == thisSubsBegin) {
     //if the current LCS is the same as the last time this block ran
     sb.append(str1.charAt(i));
  } else {
     //this block resets the string builder if a different LCS is found
     lastSubsBegin = thisSubsBegin;
     sb = new StringBuilder();
     sb.append(str1.substring(lastSubsBegin, i + 1));
  }
  }
  }
  }}

  return sb.toString();
  }

这段代码有帮助，但仅限于小文件，每次我用大文件运行它时，我都会得到一个“内存不足:java 堆空间”错误。我需要正确的算法来摆脱堆空间问题，不，我无法增加 java 内存，任何人都可以帮助我或为我指出正确的方向吗？

Answer 1

首先，您需要准确地确定为什么会如此占用内存，然后您就可以开始解决它。

这个声明是一个潜在的问题:

int[][] num = new int[str1.length()][str2.length()];

《 war 与和平》的长度超过 300 万个字符，而《白鲸》的长度大约是它的一半，因此我们保守地说它的长度为 100 万个字符。

您尝试为 3,000,000,000,000 个整数分配空间，每个整数为 4 个字节，计算结果为 12,000,000,000,000 个字节或略低于 11 TB。

希望大家清楚为什么该算法不适合这种长度的字符串。

值得庆幸的是，计算机科学的基本理论之一是，你总是可以用时间换取内存，反之亦然。

相反，您想尝试 generalized suffix tree 。它的内存成本为\Theta(n + m)，并且可以在\Theta(n + m) 中构造，这更易于管理。

Here是生成此类树的 O(n) 算法的优秀指南。

一旦后缀树就位，通过查找树中最深的节点(其子树包含两个输入字符串的子字符串)，可以在恒定时间内找到 LCS。典型的策略是如果所有节点“v”满足以下属性，则用标志“i”标记它们:

以 v 为根的子树包含字符串 S_i 的子串

然后找到最深的节点 v，其中 v 被标记为范围内所有 i 的 i(在本例中，只有 0 和 1)。