lcs内存不足的两个大型文件之间最长的公共子字符串：java堆空间

Question

在这之后，我完全疯了，我需要在两个文件之间找到最长的公共子字符串，一个小文件和一个大文件。我甚至不知道从哪里开始搜索，以下是我目前掌握的信息

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()];

《战争与和平》有300多万个字符，而《白鲸》大约是它的一半，所以我们保守地说它有100万个字符

您正在尝试为3000000000000个整数分配空间，每个整数是4个字节，计算结果是12000000000000字节或11 TB以下的一位

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

谢天谢地，计算机科学的一个基本理论是，你总是可以用时间换取内存，反之亦然

相反，你想试试generalized suffix tree。它的内存开销为\Theta（n+m），可以在\Theta（n+m）中构造，这更易于管理

Here是生成此类树的O（n）算法的极好指南

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

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

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