サイズの違いはどこから来ていますか？

Question

英語の辞書にすべての単語（定義ではない）を保存するためのトライを作成しました。そのポイントは、与えられた範囲内の文字だけを含むすべての単語を得ることができるようになったことです。

すべての単語を含むテキストファイルは約2.7MBですが、ツリーを作成してpickleを使用してファイルに書き込むと、ファイルは> 33MBです。

このサイズの違いはどこから生じますか？私は別の単語のために同じ文字の複数のコピーを格納する必要がないことによってスペースを節約すると思った。例えば、単語appとappleの場合、a - > p - > p - > l - > e 。次のように

私のコードは次のとおりです。トライの

import pickle 

class WordTrieNode: 
    def __init__(self, nodeLetter='', parentNode=None, isWordEnding=False): 
     self.nodeLetter = nodeLetter 
     self.parentNode = parentNode 
     self.isWordEnding = isWordEnding 
     self.children = [None]*26 # One entry for each lowercase letter of the alphabet 

    def getWord(self): 
     if(self.parentNode is None): 
      return '' 

     return self.parentNode.getWord() + self.nodeLetter 

    def isEndOfWord(self): 
     return self.isWordEnding 

    def markEndOfWord(): 
     self.isWordEnding = True 

    def insertWord(self, word): 
     if(len(word) == 0): 
      return 

     char = word[0] 
     idx = ord(char) - ord('a') 
     if(len(word) == 1): 
      if(self.children[idx] is None): 
       node = WordTrieNode(char, self, True) 
       self.children[idx] = node 
      else: 
       self.children[idx].markEndOfWord() 
     else: 
      if(self.children[idx] is None): 
       node = WordTrieNode(char, self, False) 
       self.children[idx] = node 
       self.children[idx].insertWord(word[1:]) 
      else: 
       self.children[idx].insertWord(word[1:]) 

    def getAllWords(self): 
     for node in self.children: 
      if node is not None: 
       if node.isEndOfWord(): 
        print(node.getWord()) 
       node.getAllWords() 

    def getAllWordsInRange(self, low='a', high='z'): 
     i = ord(low) - ord('a') 
     j = ord(high) - ord('a') 
     for node in self.children[i:j+1]: 
      if node is not None: 
       if node.isEndOfWord(): 
        print(node.getWord()) 
       node.getAllWordsInRange(low, high) 



def main(): 

    tree = WordTrieNode("", None, False) 

    with open('en.txt') as file: 
     for line in file: 
      tree.insertWord(line.strip('\n')) 
    with open("treeout", 'wb') as output: 
     pickle.dump(tree, output, pickle.HIGHEST_PROTOCOL) 

    #tree.getAllWordsInRange('a', 'l') 
    #tree.getAllWords() 
if __name__ == "__main__": 
    main() 

Answer 1

ノード、彼らはすべての可能な次の文字へのリンクを保存して巨大です。コードでわかるように、すべてのノードには26のリンク（子）のリストがあります。

もっと複雑なスキームが可能ですが（https://en.wikipedia.org/wiki/Trie#Compressing_tries）、複雑さが増しスピードが遅くなります。