Java后缀Trie超出堆空间

Question

我正在实现一个后缀特里树(这与后缀树不同)，它将字符串的字符后缀存储为树结构中的节点，其中字符串是通过遍历树直到击中“$”或您已完成搜索。

问题在于，在使用大型文本文件时，构造此 trie 比 Java 消耗更多内存。就数据结构而言，有什么地方可以减少内存使用吗？这是家庭作业，并不需要使其成为压缩后缀树(基本上是后缀树)。

这是我目前拥有的基本结构(如果您确实需要，我可以提供实现细节):

//SuffixTrie.java

public class SuffixTrie {
    private SuffixTrieNode root = new SuffixTrieNode();

    // implementation of insertions into tree etc..


    public static void main(String[] args) throws FileNotFoundException {   
        String fileName = "Frankenstein.txt";
        SuffixTrie st = readInFromFile(fileName);
        String[] ss = {"without","hideous", "the only", "onster", ", the", "ngeuhhh"};
        for (String s: ss) {
            SuffixTrieNode sn = st.get(s);
            System.out.println("[" + s + "]: " + sn);
        }
    }
}

每个节点是:

// SuffixTrieNode.java
public class SuffixTrieNode {
    private char label; // Indicates the letter for this node
    private boolean isTerminal = false;
    private SuffixTrieData data;
    private HashSet<SuffixTrieNode> children; 
 // Inserting adds more SuffixTrieNodes to the children of the node

每个节点保存的数据为:

public class SuffixTrieData {
    private ArrayList<Pair> startIndexes = new ArrayList<Pair>();

    public SuffixTrieData(int sentence, int index){
        addStartIndex(sentence, index);
    }   
    public class Pair{
        public int sentence;
        public int index;
        public Pair(int sentence, int index){
            this.sentence = sentence;
            this.index = index;
        }
    }
}

我得到的错误是:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.ArrayList.<init>(Unknown Source)
    at java.util.ArrayList.<init>(Unknown Source)
    at SuffixTrieData.<init>(SuffixTrieData.java:7)
    at SuffixTrie.insert(SuffixTrie.java:20)
    at SuffixTrie.insert(SuffixTrie.java:11)
    at SuffixTrie.readInFromFile(SuffixTrie.java:77)
    at SuffixTrie.main(SuffixTrie.java:89)

不过，它对于较小的文本文件来说效果很好，这是他们第一次给学生布置这项作业，因此教师不知道这是否可以使用后缀特里树来实现。

Answer 1

后缀特里树将仅用于单词(字母)就使用大量空间。此外，您似乎正在存储该单词出现的每个句子的数组以及索引(您发布的代码不完整，如果我错了，请纠正我)。如果文件相当大......这将占用一些空间。

您可以做的一件事是在存储时压缩句子，并在检索它们时使用 deflate/inflate 解压缩。

除此之外，您可能希望在运行进程时使用 -Xmx 选项(例如 java -Xmx 2GB -jar myJarFile.jar )。