TRIEデータ構造における検索操作の時間複雑度

Question

辞書ベースのトライデータ構造を実装しようとしています。以下のPythonコードを見つけてください。

class Trie: 
    def __init__(self): 
    self.word_end = '_end_' 
    self.root = {} 

    def add_word(self, word): 
    self.add_words([word]) 

    def add_words(self, words): 
    for word in words: 
     current_dict = self.root 
     for letter in word: 
      current_dict = current_dict.setdefault(letter, {}) 
     current_dict[self.word_end] = self.word_end 


    def check_word(self, word): 
    current_dict = self.root 
    for letter in word: 
     if letter in current_dict: 
      current_dict = current_dict[letter] 
     else: 
      return False 
    else: 
     if self.word_end in current_dict: 
      return True 
     else: 
      return False 



tree = Trie() 
tree.add_words(['foo', 'bar', 'baz', 'barz']) 
print tree 
""" 
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
      'z': {'_end_': '_end_'}}}, 
'f': {'o': {'o': {'_end_': '_end_'}}}} 
""" 

print check_word('baz') 
# True 
print check_word('barz') 
# True 
print check_worf('barzz') 
# False 

単語を検索する複雑さはO（m）であり、mは検索する単語の長さです。また、単語を追加することは非常に似通った複雑さを持っています - O（m）ここでmは追加される単語の長さです。

質問： これらの複雑さはあまりにも優れています。誰かがこれらの複雑さを確認できますか？ Trieの実装に何か問題はありますか？

Answer 1

TRIEで検索する時間の複雑さは、実際にはO（k）です。ここで、kは検索する文字列の長さです。これは正確で実証済みの事実です。しかし、ストレージ要件はペナルティが見られる場所です。 Trieの各ノードは複数のブランチで構成されています。各ブランチはキーの可能な文字を表します。すべてのキーの最後のノードを単語の終わりノードとしてマークする必要があります。トライノードフィールドisEndOfWordは、ノードをワードノードの終わりとして区別するために使用されます。

一般に、コストはO（length_of_string）ですが、Trieのメモリ要件はO（ALPHABET_SIZE * length_of_string * N）です（NはTrieのキーの数です）。トライノードのメモリ表現を最小限にするために、トライノード（例えば、圧縮トライ、3進探索木など）の効率的な表現が存在する。