Trie - Реализация в java

Question

Я знаю, что есть много материалов, касающихся этого, но у меня были довольно конкретные вопросы. У меня есть файл, содержащий почтовые коды, и мне нужно создать структуру данных 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+ кодов, составляет около 190 КБ, и я проверил размер объекта trie, используя профилировщик, который вышел намного больше. Связаны ли эти два размера? Должен ли размер trie быть меньше размера исходного текстового файла?

Спасибо, Ouney

Answer 1

предположив, что ~ 9/10 узлы листья (не содержат детей), вы можете значительно уменьшить пространство, что вся структура занимает от ленивой инициализации children массива:

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; 
}