2

我正在尝试在 Java 中为文本编辑器实现一个包含 203675 ​​个单词的 trie 结构。

以前，我使用 ArrayList 来存储单词，这需要 90 兆字节的空间。所以我想用一个 trie 来最小化空间消耗。

这是我到目前为止所拥有的，但现在空间消耗为 250 兆字节。这种增加的原因是什么？

package TextEditor;

import java.io.*;
import java.util.*;
import javax.swing.JOptionPane;

class Vertex {
    int words;
    Map<Character, Vertex> child;
    public Vertex() {
        words = 0;
        child = new HashMap<>();
    }
}
class Trie {
    private Vertex root;
    private InputStream openFile;
    private OutputStream openWriteFile;
    private BufferedReader readFile;
    private BufferedWriter writeFile;
    public Trie() {
        root = new Vertex();
    }
    public Trie(String path) {
         try {
            root = new Vertex();
            openFile = getClass().getResourceAsStream(path);
            readFile = new BufferedReader( new InputStreamReader(openFile));
            String in = readFile.readLine();
                    while(readFile.ready()) {
                        this.insert(in);
                    try {
                        in = readFile.readLine();
                    } catch (IOException ex) {
                        JOptionPane.showMessageDialog(null, 
                            "TRIE CONSTRUCTION ERROR!!!!");
                    }
                    }
        } catch (IOException ex) {
            JOptionPane.showMessageDialog(null, 
                "TRIE CONSTRUCTION ERROR!!!!");
        }
    }
    private void addWord(Vertex vertex, String s, int i) {
        try {
        if(i>=s.length()) {
            vertex.words += 1;
            return;
        }
        char ind  = s.charAt(i);
        if(!vertex.child.containsKey(ind)) {
            vertex.child.put(ind, new Vertex());
        }
    addWord(vertex.child.get(ind), s, i+1);
        } catch(Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
    final void insert(String s) {
        addWord(root, s.toLowerCase(), 0);
    }
    private void DFS(Vertex v, String s, ArrayList list, 
        boolean store, String startsWith, int ind) {
    if(v != null && v.words != 0) {
            if(!store) {
                System.out.println(s);
            }
            else {
                if(s.length() >= startsWith.length()) {
                    list.add(s);
                }
            }
        }
        for (Map.Entry<Character, Vertex> entry : v.child.entrySet()) {
            Character c = entry.getKey();
            if((startsWith ==  null) || (ind>=startsWith.length()) || 
                (startsWith.charAt(ind) == c)) {
                    DFS(v.child.get(c), s + c, list, store, startsWith, ind+1);
             }
        }
    }
    public void Print() {
        DFS(root, new  String(""), null, false, null, 0);
    }
    ArrayList<String> getAsList(String startsWith) {
        ArrayList ret = new ArrayList();
        DFS(root, new  String(""), ret, true, startsWith, 0);
        return ret;
    }
    int count(Vertex  vertex, String s, int i) {
    if(i >= s.length()) {
            return vertex.words;
        }
    if(!vertex.child.containsKey(s.charAt(i))) {
            return 0;
        }
        return count(vertex.child.get(s.charAt(i)), s, i+1);
    }
    int count(String s) {   
        return count(root, s, 0);
    }
}

有我可以使用的 trie 结构的工作示例吗？

4

2 回答 2

1

您对“空间”一词的使用含糊不清。根据您的描述，听起来您在谈论堆。如果是这样，内存使用量增加的原因是像 trie 这样的数据结构实际上确实占用了额外的内存来存储节点之间的引用。一个ArrayList只是把所有的东西都打包进去，一个String接一个的引用，除了数组的长度之外，它没有任何额外的信息。trie 有更多的簿记来指定所有节点之间的关系。

特别是，HashMap每个顶点中的 都将非常昂贵；默认情况下，Sun 实现为 16 项映射分配足够的空间，这需要存储映射自己的内存分配记录hashCodes（32 位ints，而不是chars），每个对象包装器Character......

于 2013-07-30T20:20:37.570 回答
0

首先，将数据结构（您的 trie）与填充它的任何代码分开。它只需要以结构化的形式保存数据，并提供一些基本功能，就是这样。填充它应该发生在该数据结构本身之外，以便您可以正确处理流。没有一个很好的理由让您的 trie 通过提供路径作为参数来填充自己。为了澄清我的第一点 - 将填充从树中取出：目前，流在树中吞噬了大量内存，因为它们被保存在私有变量中，并且流永远不会关闭或销毁。这意味着您将加载到内存中的文件保留在填充的数据结构之上。否则垃圾收集可以像使用 arraylist 一样清理这些项目。

请不要重新发明轮子并使用如下的基本实现。让它与这个基本设置一起工作，然后担心以后改进它。

public class Trie {

    private Map<String, Node> roots = new HashMap<>();

    public Trie() {}

    public Trie(List<String> argInitialWords) {
            for (String word:argInitialWords) {
                    addWord(word);
            }
    }

    public void addWord(String argWord) {
            addWord(argWord.toCharArray());
    }

    public void addWord(char[] argWord) {
            Node currentNode = null;

            if (!roots.containsKey(Character.toString(argWord[0]))) {
                    roots.put(Character.toString(argWord[0]), new Node(argWord[0], "" + argWord[0]));
            }

            currentNode = roots.get(Character.toString(argWord[0]));

            for (int i = 1; i < argWord.length; i++) {
                    if (currentNode.getChild(argWord[i]) == null) {
                            currentNode.addChild(new Node(argWord[i], currentNode.getValue() + argWord[i]));
                    }

                    currentNode = currentNode.getChild(argWord[i]);
            }

            currentNode.setIsWord(true);
    }

    public boolean containsPrefix(String argPrefix) {
            return contains(argPrefix.toCharArray(), false);
    }

    public boolean containsWord(String argWord) {
            return contains(argWord.toCharArray(), true);
    }

    public Node getWord(String argString) {
            Node node = getNode(argString.toCharArray());
            return node != null && node.isWord() ? node : null;
    }

    public Node getPrefix(String argString) {
            return getNode(argString.toCharArray());
    }

    @Override
    public String toString() {
            return roots.toString();
    }

    private boolean contains(char[] argString, boolean argIsWord) {
            Node node = getNode(argString);
            return (node != null && node.isWord() && argIsWord) || (!argIsWord && node != null);
    }

    private Node getNode(char[] argString) {
            Node currentNode = roots.get(Character.toString(argString[0]));

            for (int i = 1; i < argString.length && currentNode != null; i++) {
                    currentNode = currentNode.getChild(argString[i]);

                    if (currentNode == null) {
                            return null;
                    }
            }

            return currentNode;
    }
}

public class Node {

    private final Character ch;
    private final String value;
    private Map<String, Node> children = new HashMap<>();
    private boolean isValidWord;

    public Node(char argChar, String argValue) {
            ch = argChar;
            value = argValue;
    }

    public boolean addChild(Node argChild) {
            if (children.containsKey(Character.toString(argChild.getChar()))) {
                    return false;
            }

            children.put(Character.toString(argChild.getChar()), argChild);
            return true;
    }

    public boolean containsChildValue(char c) {
            return children.containsKey(Character.toString(c));
    }

    public String getValue() {
            return value.toString();
    }

    public char getChar() {
            return ch;
    }

    public Node getChild(char c) {
            return children.get(Character.toString(c));
    }

    public boolean isWord() {
            return isValidWord;
    }

    public void setIsWord(boolean argIsWord) {
            isValidWord = argIsWord;

    }

    public String toString() {
            return value;
    }

}

如果您正在考虑改进内存使用（以性能为代价），您可以通过以下方式（单独或组合）进行

  • 通过将对象 Character 切换为其原始 char 形式，这将为您节省用于对象的字节以及任何内部私有变量的开销
  • 通过将节点的 value 参数切换为 char[] 类型，您将在每个节点中为自己保存另一个 String 对象
  • 通过实现 trie 压缩和合并公共分支。这将消除对一堆节点的需要。将保留多少节点将取决于实际的内容输入和输入的单词之间的相似性。相似词越多，可以压缩的树越少，节省的节点就越少。因此将释放更少的内存
  • 通过将 hashmap 实现切换到对内存更友好的实现（以查找和插入速度为代价）。最有效的是一个数据结构，它不会占用比保存密钥所需更多的内存。例如：如果已知一个节点恰好持有 3 个键，那么就内存消耗而言，长度为 3 的数组最适合该节点。实际上，在内存消耗方面，具有低起始容量的 sortedSet 应该比 hashmap 工作得更好，因为你不需要保存 hashcode，但比数组更容易插入和搜索。

一般来说，一个实现良好的 trie，我强调实现良好的尝试应该大约等于您输入的同一数据集的 90Mb 的内存消耗，尽管它完全取决于实际的数据集。

如果您设法整理出一个单词列表，其中大多数单词不是任何其他单词的前缀。您的内存使用量将远远大于 ArrayList，因为您需要更多的节点来表示同一事物。

如果你真的想为真正的随机数据集节省一些内存，你应该看看Burst Trys，另一个可行的选择可能是 patricia trie。

于 2013-07-30T20:02:30.933 回答