Trie

Question

我知道有很多 material 可用，但我有非常具体的问题。我有一个包含邮政编码的文件，我必须使用这些代码创建 trie 数据结构。我已经写了我的实现是 -

public class Trie{

TrieNode root = null;

public void addWord(String zipCodeStr){
    if(root==null){
        root = new TrieNode();
    }
    TrieNode current = root;
    for(char c : zipCodeStr.toCharArray()){
        if(current.childern[Character.getNumericValue(c)]==null){
            current.childern[Character.getNumericValue(c)] = new TrieNode();
        }
        current = current.childern[Character.getNumericValue(c)];
    }
    current.isWord = true;
}

public boolean exists(String zipCodeStr){
    boolean result = true;
    TrieNode current = root;
    for(char c : zipCodeStr.toCharArray()){
        if(current.childern[Character.getNumericValue(c)]==null){
            result = false;
            break;
        }
        current = current.childern[Character.getNumericValue(c)];
    }
    if(result && current.isWord){
        result = true;
    }else{
        result = false;
    }
    return result;
}

private static class TrieNode{

    TrieNode[] childern = new TrieNode[10];
    boolean isWord = false;

    public TrieNode() {
    }

}
}

在这里，我没有存储任何值，因为位置提供了该信息。

问题 - i) 可以进一步即兴创作吗？ ii) 包含 27000+ 个代码的原始文本文件大小约为 190kb，我使用分析器检查了 trie 对象的大小，结果发现要大得多。这两个尺寸有关系吗？ trie 大小应该小于原始文本文件大小吗？

谢谢，乌尼

Answer 1

假设约 9/10 个节点是叶节点（不包含子节点），您可以通过延迟初始化 children 数组显着减少 space 整个结构占用：

private static class TrieNode {
    TrieNode[] children = null;  
    boolean isWord = false;
}

现在只有在实际需要时才需要创建一个新数组：

public void addWord(String zipCodeStr) {
   if (root == null){
        root = new TrieNode();
   }
   TrieNode current = root;
   for (char c : zipCodeStr.toCharArray()) {
       if (current.children == null) {
           current.children = new TrieNode[10];
       }
       if (current.children[Character.getNumericValue(c)] == null) {
           current.children[Character.getNumericValue(c)] = new TrieNode();
       }
       current = current.children[Character.getNumericValue(c)];
   }
   current.isWord = true;
}

Trie - 在 java 中实现

Trie - Implementation in java

java