0

我正在实现一个后缀树（这与后缀树不同），它将字符串的字符后缀存储为树结构中的节点，其中通过遍历树直到你点击'$'或者你点击您的搜索结束。

问题在于，在使用大型文本文件时，构造这个 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)

虽然它适用于较小的文本文件，但这是他们第一次给学生这个作业，所以教师不知道这是否可以使用后缀 trie..

4

2 回答 2

1

后缀 trie 将仅用于单词（字母）的大量空间。此外，您似乎正在存储带有索引的单词出现的每个句子的数组（您发布的代码不完整，如果我错了，请纠正我）。如果文件相当大……那会占用一些空间。

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

除此之外，您可能希望在运行进程时使用-Xmx选项（例如java -Xmx 2GB -jar myJarFile.jar）增加 JVM 的堆大小。

于 2011-09-04T05:45:00.207 回答
0

两种解决方案：要么构建一个更轻的结构（每个模式一个数组列表和一个哈希集很多），或者，如果这是你最好的解决方案，你可以使用-mx命令-ms行选项来控制你的程序运行。

于 2011-09-04T05:45:48.973 回答