data-structures
Trie（プレフィックスツリー/基数ツリー）
サーチ…
Trieの紹介
検索エンジンの仕組みについて疑問に思ったことはありますか？ Googleは数ミリ秒で何百万という結果をあなたの目の前でどのように整理していますか？何千キロも離れた巨大なデータベースは、あなたが探している情報を見つけてそれをあなたに送り返すのですか？この背後にある理由は、より高速のインターネットとスーパーコンピュータを使用することだけでは不可能です。魅力的な探索アルゴリズムやデータ構造の中には、その背後にあるものがあります。それらの1つはトライです。
トライは 、 デジタルツリーとも呼ばれ、時には基数ツリーやプレフィックスツリー （接頭辞で検索できるように）は検索ツリーの一種であり、動的な集合や連想配列を格納するための順序付けられたツリーデータ構造です通常は文字列です。これは、容易に実装できるデータ構造の1つです。何百万語という巨大なデータベースを持っているとしましょう。トライを使用してこれらの情報を保存することができ、これらの単語の検索の複雑さは、検索している単語の長さだけに依存します。つまり、データベースの大きさには依存しません。驚くべきことではないですか？
これらの単語を含む辞書があるとしましょう：
algo
algea
also
tom
to
私たちは、この辞書を私たちが探している単語を簡単に見つけることができるように記憶しておきたいと思います。方法の1つは、単語を辞書順に並べ替えることです。実際の辞書に単語がどのように格納されているかです。次に、 バイナリ検索を行うことでその単語を見つけることができます。もう一つの方法はPrefix TreeまたはTrieを要約することです。 「 トライ 」という言葉は、 「 トライ・ヴァル」という言葉に由来しています。ここで、 接頭 辞は文字列の接頭 辞を表します。これは次のように定義できます。文字列の先頭から作成できるすべての部分文字列を接頭辞と呼びます。たとえば、 'c'、 'ca'、 'cat'はすべて文字列 'cat'の接頭辞です。
さあ、 トライに戻ってみましょう。名前が示すように、ツリーを作成します。最初は、ルートだけの空のツリーがあります。
単語'algo'を挿入します。新しいノードを作成し、この2つのノード「a」の間にエッジを指定します。新しいノードから「l」という別のエッジを作成し、それを別のノードに接続します。このようにして、 'g'と'o'の 2つの新しいエッジを作成します。ノードに情報を格納していないことに注意してください。ここでは、これらのノードから新しいエッジを作成することのみを検討します。これから、 'x'という名前のエッジを呼びましょう - edge-x
ここで、 「algea」という単語を追加します。私たちは既に持っている根から縁を必要とします 。だから新しいエッジを追加する必要はありません。同様に、私たちは'a'から'l'と'l'から'g'の端を持っています。つまり、 「alg」はすでにトライに入っています。 edge-eとedge-aを追加するだけです。
私たちは、「同じ」という言葉を追加します。ルートから接頭辞'al'があります。私たちはそれに「so」を追加します。
'tom'を追加しましょう。今回は、以前に作成したtomという接頭辞がないため、ルートから新しいエッジを作成します。
では、どのように'to'を追加するべきですか？ 'to'は完全に'tom'の接頭辞なので、エッジを追加する必要はありません。私たちができることは、いくつかのノードにエンドマークを付けることです。少なくとも1つの単語が完成したノードに終わり記号を付けます。緑色の円は終了マークを示します。トライは次のようになります：
なぜエンドマークを追加したのかを簡単に理解することができます。トライに格納されている単語を決定することができます。文字は端にあり、ノードには終了記号が含まれます。
今、あなたはこのような単語を保存する目的は何ですか？たとえば、辞書に「アリス」という言葉を見つけるように求められます。あなたはトライを横断します。ルートからエッジ -aがあるかどうかをチェックします。それから、 'a'からエッジlがあるかどうかを確認します。その後、あなたはどんなエッジも見つけられません。だから、 アリスという言葉は辞書にはないという結論に至ることができます。
辞書に「alg」という単語がある場合は、 ルート→a 、 a→l 、 l→gをたどりますが、末尾に緑色のノードはありません。したがって、その単語は辞書には存在しません。 'tom'を検索すると緑色のノードになります。これはその単語が辞書に存在することを意味します。
複雑：
トライで単語を検索するために必要なステップの最大量は、私たちが探している単語の長さです。複雑さはO（長さ）です。挿入の複雑さは同じです。 トライを実装するのに必要なメモリ量は、実装によって異なります。我々はトライで10 6文字（ない言葉、文字）を格納することができ、別の例では、実装が表示されます。
トライの使用：
- 辞書に単語を挿入、削除、検索する。
- 文字列が別の文字列の接頭辞であるかどうかを調べる。
- 共通プレフィックスを持つ文字列の数を調べる。
- 私たちが入力するプレフィックスに応じて、携帯電話の連絡先の名前を提案します。
- 2つの文字列の「最長共通部分文字列」を見つける。
- 'Longest Common Ancestor'を使用して2つの単語の '共通接頭辞'の長さを見つける
トライの実装
この例を読む前に、最初にTrieの紹介を読むことを強くお勧めします。
Trieを実装する最も簡単な方法の1つは、リンクされたリストを使用することです。
ノード：
ノードは次のもので構成されます。
- エンドマークの変数。
- 次のノードへのポインタ配列。
エンドマーク変数は、それがエンドポイントであるかどうかを単に示します。ポインタ配列は、作成可能なすべてのエッジを示します。英語のアルファベットでは、1つのノードから最大26の辺を作成できるため、配列のサイズは26になります。各ポインタ配列の最初の値はNULLになり、end-mark変数はfalseになります。
Node:
Boolean Endmark
Node *next[26]
Node()
endmark = false
for i from 0 to 25
next[i] := NULL
endfor
endNode
next []配列内のすべての要素は別のノードを指します。 次の[0]共有ノードを指すエッジ 、 次の[1]のようにエッジBと共有ノードにポイント。 Endmarkをfalseに初期化するNodeのコンストラクタを定義し、 next []ポインタ配列のすべての値にNULLを入れました。
Trieを作成するには、まずrootをインスタンス化する必要があります。次に、 ルートから、情報を格納するための他のノードを作成します。
挿入：
Procedure Insert(S, root): // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
id := S[i] - 'a'
if curr -> next[id] == NULL
curr -> next[id] = Node()
curr := curr -> next[id]
endfor
curr -> endmark = true
ここではazと協力しています。したがって、ASCII値を0〜25に変換するには、 'a'の ASCII値を減算します。現在のノード（curr）に現在のキャラクタのエッジがあるかどうかを確認します。そうであれば、新しいノードを作成しない場合は、そのエッジを使用して次のノードに移動します。最後に、エンドマークをtrueに変更します。
検索：
Procedure Search(S, root) // S is the string we are searching
curr := root
for i from 1 to S.length
id := S[i] - 'a'
if curr -> next[id] == NULL
Return false
curr := curr -> id
Return curr -> endmark
このプロセスはインサートに似ています。最後に、エンドマークを返します。したがって、 エンドマークが真の場合、その単語が辞書に存在することを意味します。それが偽であれば、単語は辞書に存在しません。
これが私たちの主な実装でした。これでトライに単語を挿入して検索することができます。
削除：
時々、メモリを節約するために使用されなくなる単語を消去する必要があります。この目的のために、未使用の単語を削除する必要があります：
Procedure Delete(curr): //curr represents the current node to be deleted
for i from 0 to 25
if curr -> next[i] is not equal to NULL
delete(curr -> next[i])
delete(curr) //free the memory the pointer is pointing to
この関数は、 currのすべての子ノードに行き、それらを削除し、 currを削除してメモリを解放します。 delete（root）を呼び出すと、 Trie全体が削除されます。
Trieは配列を使って実装することもできます。