0

私は、文字列の文字サフィックスをツリー構造のノードとして格納するサフィックス トライ (これはサフィックス ツリーとは異なります) を実装しています。このツリー構造では、'$' にヒットするか、またはあなたの検索の終わり。

問題は、このトライを作成すると、大きなテキスト ファイルを使用する場合に 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 は、単語 (文字) だけで多くのスペースを使用します。さらに、単語がインデックス付きで表示されるすべての文の配列を格納しているようです (投稿したコードは不完全です。間違っている場合は修正してください)。ファイルがかなり大きい場合...それはいくらかのスペースを占有します。

できることの 1 つは、保存時に文を圧縮し、deflate/inflate を使用して文を取得するときに解凍することです。

それとは別に、-Xmxオプション (例: java -Xmx 2GB -jar myJarFile.jar) を使用して、プロセスを実行するときに JVM のヒープ サイズを増やしたいと思うでしょう。

于 2011-09-04T05:45:00.207 に答える
0

2 つの解決策: より軽量な構造を構築する (配列リストとモードごとのハッシュセットが多い) か、それが最善の解決策である場合は、プログラムを実行するジャムに対してコマンド ライン オプション-mxとコマンド ライン オプションを使用します。-ms

于 2011-09-04T05:45:48.973 に答える