Java Suffix Trie, превышающий пространство кучи - PullRequest
Новая
       17

Java Suffix Trie, превышающий пространство кучи

0 голосов
/ 04 сентября 2011

Я реализую три-суффикс (это отличается от дерева суффиксов), в котором символы-суффиксы строк хранятся в виде узлов в древовидной структуре, где строка состоит из обхода дерева, пока вы не нажмете '$' или вы достигли конца поиска.

Проблема в том, что для создания этого дерева требуется больше памяти, чем в 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)

Хотя он работает отлично для текстовых файлов меньшего размера, и это первый раз, когда они дают студентам это задание, поэтому преподаватели не знают, выполнимо ли это с суффиксом tree.

Ответы [ 2 ]

0 голосов
/ 04 сентября 2011

Два решения: либо вы создаете более легкую структуру (список массивов и хэш-набор для каждого режима очень много), либо, если это ваше лучшее решение, вы используете опции командной строки -mx и -ms для блокировки ваших программ. обкатка.

0 голосов
/ 04 сентября 2011

Три суффикс собирается использовать много места только для слов (букв).Кроме того, кажется, что вы сохраняете массив каждого предложения, в котором появляется слово с индексом (код, который вы публикуете, является неполным, поправьте меня, если я ошибаюсь).Если файл довольно большой ... это займет некоторое пространство.

Одна вещь, которую вы можете сделать, это сжать предложения при сохранении и распаковать при их получении с использованием deflate / inflate.

Кроме этого, вы, вероятно, захотите увеличить размер кучи для JVM при запуске процесса, используя опцию -Xmx (например, java -Xmx 2GB -jar myJarFile.jar).

...