TRIE構造

트라이(Trie)は、文字列を格納および効率的に参照するためのツリー構造です.
Trieは迅速な時間的複雑さを有するため,検索エンジンサイトが提供する自動補完や検索語推奨機能などの文字列をナビゲートする際にTrieアルゴリズムを用いた.

こうぞう

["frodo", "front", "kakao", "kaggle"]次の単語をtrie構造として保存すると、構造ツリーが作成されます.

構造をより詳細に説明するには、次の手順に従います.

特長

ツリーアルゴリズムは、ノードのツリーから構成されます.

文字列の末尾を示すフラグがあります.

きおくコード

head = {}

def add(word):
    node = head
    for w in word:
        if w not in node:
            node[w]={}
        node = node[w]
    node['end'] = True

文字'ab'にTrie構造でデータを入れると、次の順序になります.

for文で「ab」を1つずつ挿入するために、for文を回します.

nodeに「a」という鍵が存在しない場合、「a」というディックシーケンスが作成されます.

その後、node['a']はdicksherryのメモリアドレスをnodeに渡す.

node[「a」に「b」という鍵が存在しない場合、「b」というバイナリファイルが作成されます.

そしてnode['a']['b']のディックシャーキャンプメモリアドレスをnodeに渡します.

すべての文字が含まれているため、for文を閉じます.

ノード["end"]=Trueを挿入し、文字列が終了したことを示します.

headとnodeの共有メモリ領域が理解できない場合は、まず勉強することをお勧めします.

コードの検索

def search(word):
    node = head
    for w in word:
        if w not in node:
            return False
        node = node[w]
    if 'end' in node:
        return True
    else:
        return False

長所

트라이(Trie)|文字列をすばやく検索できます.

|文字列を検索する場合、時間の複雑さは、比較検索よりも効率的です.

短所

各ノードはサブノードのポインタを配列として格納するため、大きな記憶領域が必要となる.

推薦練習問題
文字列セット-標準シルバー3