トライ

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
トライ
タイプ
発明された1960年
によって発明されたエドワード・フレドキンアクセル・トゥエ、レネ・デ・ラ・ブリアンダイ
ビッグO表記時間計算量
アルゴリズム 平均 最悪の場合
スペース O(n O(n
検索 O(n O(n
入れる O(n O(n
消去 O(n O(n
トライの描写。 ルートノードを表す単一の空の円は、3つの子を指します。 各子への矢印は、異なる文字でマークされています。 子自体にも同様の矢印と子ノードのセットがあり、ノードは青い整数値を持つ完全な単語に対応しています。
キー「A」、「to」、「tea」、「ted」、「ten」、「i」、「in」、および「inn」のトライ。完全な英語の各単語には、任意の整数値が関連付けられています。

コンピュータサイエンスでは、デジタルツリーまたはプレフィックスツリーとも呼ばれるトライは、 k-ary検索ツリーの一種であり、セット内から特定のキーを見つけるために使用されるツリーデータ構造です。これらのキーはほとんどの場合文字列であり、ノード間のリンクはキー全体ではなく、個々の文字によって定義されます。キーにアクセスする(値を回復する、変更する、または削除する)ために、キー内の各文字を表すノード間のリンクをたどって 、トライが深さ優先でトラバースされます。

二分探索木とは異なり、トライ内のノードは関連するキーを保存しません。代わりに、トライ内のノードの位置によって、ノードが関連付けられているキーが定義されます。これは、各キーの値をデータ構造全体に分散し、すべてのノードに必ずしも関連付けられた値があるとは限らないことを意味します。

ノードのすべての子には、その親ノードに関連付けられた文字列の共通のプレフィックスがあり、ルートは空の文字列に関連付けられています。プレフィックスでアクセス可能なデータを格納するこのタスクは、基数木を使用することにより、メモリに最適化された方法で実行できます。

試行は文字列でキー設定できますが、そうである必要はありません。同じアルゴリズムを、数字や形の順列など、基礎となるタイプの順序付きリストに適合させることができます。特に、ビット単位のトライは、整数やメモリアドレスなどの固定長のバイナリデータを構成する個々のビットに対応しています

歴史、語源、発音

文字列のセットを表すためのトライのアイデアは、1912年にAxelThueによって最初に抽象的に記述されました。 [1] [2]トライは、1959年にRenédelaBriandaisによってコンピュータコンテキストで最初に記述されました。[3] [2] [ 4] :336 このアイデアは、1960年にEdward Fredkin [5]によって独自に説明されました。は、検索の中央の音節の後に、トライという用語を作成し、/ ˈ triː / (「ツリー」としてと発音しました[6] [7]しかし、他の著者はそれを発音します/ ˈ t r /(「try」として)、「tree」と口頭で区別しようとします。[6][7][2]

操作

海の表現を試して、売って、彼女。

試行は、文字列キーの挿入、削除、検索など、さまざまな操作をサポートします。トライはで構成されています他の子サフィックス子ノードへの参照であるリンク、またはルートを除いて、各ノードは、と呼ばれる他の1つのノードによってポイントされます。各ノードにはリンク、ここでアルファベットのセットのカーディナリティですが、試行にはかなりの数がありますリンク。ほとんどの場合、配列は文字エンコードのビット長です-(符号なし) ASCIIの場合は256です。[8] :732 

内のリンク次の特性を強調します:[8] :734  [4] :336 

  1. 文字と文字列キーは、トライデータ構造表現に暗黙的に格納され、文字列の終了を示す文字番兵の値が含まれます。
  2. 各ノードには、セットの強力なキーのプレフィックスへの1つの可能なリンクが含まれています。

トライ内のノードの基本的な構造タイプは次のとおりです。オプションを含めることができます、文字列の最後の文字に格納されている各キー、またはターミナルノードに関連付けられています。

 構造ノードノード[アルファベット-サイズ] 
   Is-ターミナルブールデータ型
 終了構造

検索

検索トライ内の各ノードには、指定された文字列内の可能な各文字への対応するリンクが含まれているため、トライ内の文字は検索文字列キーの文字によってガイドされます。したがって、トライ内の文字列をたどると、関連する指定された文字列キーに対して。A検索実行内のリンクは、キーが存在しないことを示します。[8] :732-733 

次の擬似コードは、指定された文字列キーの検索手順を実装します()根付いたトライで()。[9] :135 

Trie-Find(x、key)
    for0≤i <key.length do 
     if x.Children [key [i]] = nil then 
       return false
      end if
     x:= x.Children [key [i]]
   
   リターンx.Value
を繰り返します

上記の擬似コードでは、トライのルートノードのポインタと文字列キーにそれぞれ対応します。標準的なトライでの検索操作には、文字列パラメータのサイズです、 とアルファベットサイズに対応します[10] :一方、754  の二分探索木は最悪の場合、検索は木の高さに依存するため()BSTの(バランスの取れた木の場合)、ここでキーの数とキーの長さです。ノードが共通の初期文字列サブシーケンスを共有し、構造に暗黙的にキーを格納するため、BSTが多数の短い文字列を含む場合、BSTと比較して占有するスペースが少なくなります。[11] :358 ツリーのターミナルノードにnil以外が含まれています、および関連付けられた値がトライで見つかった場合は検索ヒットであり、見つからなかった場合は検索ミスです。[8] :733 

挿入

トライへの挿入は、文字セットをインデックスとして使用することによってガイドされます。文字列キーの最後の文字に到達するまで配列します。[8] :733-734 トライ構造はトップダウン基数ソートのパッテンの実行を反映しているため、トライの各ノードは基数ソートルーチンの1回の呼び出しに対応します。[9] :135 

1 Trie-Insert(x、key、value)
2for0≤i       <key.lengthdo3 if 
x.Children         [ key [i]] = nil then
4 x.Children [key [i]]:= Node()
5        終了する場合
6 x:= x.Children [key [i]]
7      リピート
8 x.Value:= value
9 x.Is-Terminal:= True

もし文字列キーの最後の文字である新しい文字に到達する前にリンクが検出されました3〜5行目に沿って作成されます。[8] :745  入力に割り当てられます; もしもではなかった挿入時に、指定された文字列キーに関連付けられた値が現在の値に置き換えられます。

削除

トライからのキーと値のペアの削除には、対応する文字列キーを使用してターミナルノードを検索し、ターミナルインジケーターと値をfalseにマークしてそれに応じて。[8] :740 

以下は、文字列キーを削除するための再帰的な手順です()根付いたトライから()。

1 Trie-Delete(x、key)
2       if key = nil then 
3         if x.Is-Terminal = True then then
4 x.Is-ターミナル:= False
5 x.Value:= nil
7        がnilを返す場合は
6        終了
8      終了する場合
9 x.Children [key [0]]:= Trie-Delete(x.Children [key [0]]、key [1:])
10     リターンx

手順は、;ターミナルノードの到着または文字列キーの終わりを示します。ターミナルの場合、ノードはトライから削除されます(9行目で文字インデックスを)。ただし、ノードが終端になっていない文字列キーの終わりは、キーが存在しないことを示しているため、プロシージャはトライを変更しません。再帰は増分によって進行しますのインデックス。

他のデータ構造の置き換え

ハッシュテーブルの置き換え

トライを使用してハッシュテーブルを置き換えることができます。これには、次の利点があります。[11] :358 

  • サイズのキーが関連付けられているノードを検索するの複雑さを持っています、一方、不完全なハッシュ関数には多数の衝突するキーが含まれる可能性があり、そのようなテーブルの最悪の場合のルックアップ速度は次のようになります。、 どこテーブル内のノードの総数を示します。
  • ハッシュテーブルとは異なり、試行には操作にハッシュ関数は必要ありません。トライ内の異なるキーの衝突もありません。
  • トライ内のバケットは、キーの衝突を格納するハッシュテーブルバケットに類似しており、単一のキーが複数の値に関連付けられている場合にのみ必要です。
  • トライ内の文字列キーは、事前に定義されたアルファベット順を使用して並べ替えることができます。

ただし、メインメモリよりもランダムアクセス時間が長いハードディスクドライブなどのセカンダリストレージデバイスでデータに直接アクセスする場合、試行はハッシュテーブルよりも効率的ではありません[5]浮動小数点数のように、キー値を文字列として簡単に表現できない場合にも、試行は不利になります[11] :359  [疑わしい]

DFSA表現

トライは、ツリー型の決定性有限オートマトンと見なすことができます有限言語はトライオートマトンによって生成され、各トライは決定論的非巡回有限状態オートマトンに圧縮できます[12]

実装戦略

左子右兄弟二分木として実装されたトライ:垂直矢印はポインター、破線の水平矢印は次のポインターです。このトライに格納されている文字列のセットは、{baby、bad、bank、box、dad、dance }です。リストは、辞書式順序でトラバーサルできるようにソートされています。

試行は、メモリの使用と操作の速度の間のさまざまなトレードオフに対応して、いくつかの方法で表すことができます。[4] :341 トライを表すためにベクトルを使用すると、膨大なスペースが消費されます。ただし、各ノードベクトルに単一リンクリストを使用すると、実行時間を犠牲にしてメモリスペースを削減できます。これは、ベクトルのほとんどのエントリに含まれているためです。[2] :495 

アルファベットの削減などの手法では、元の文字列を小さいアルファベットよりも長い文字列として再解釈することで、スペースの複雑さを軽減できます。つまり、nバイトの文字列は、 2 n 4ビット単位の文字列と見なして、トライに格納できます。ノードごとに16個のポインター。ただし、最悪の場合、ルックアップは2倍のノードにアクセスする必要がありますが、スペース要件は8分の1に減少します。[4] :347–352 他の手法には、256個のASCIIポインターのベクトルを、ASCIIアルファベットを表す256ビットのビットマップとして格納することが含まれます。これにより、個々のノードのサイズが大幅に削減されます。[13]

ビット単位の試行

ビット単位の試行は、単純なポインターベクトルの実装におけるトライノードの膨大なスペース要件に対処するために使用されます。文字列キーセットの各文字は、文字列キー上でトライをトラバースするために使用される個々のビットを介して表されます。これらのタイプのトライの実装では、ベクトル化されたCPU命令を使用して、固定長のキー入力(GCC組み込み関数など)の最初のセットビットを検索しますしたがって、セットビットは、32または64エントリベースのビット単位ツリーの最初のアイテムまたは子ノードにインデックスを付けるために使用されます。次に、キーの後続の各ビットをテストして検索を続行します。[14]__builtin_clz()

この手順は、キャッシュローカルであり、レジスタの独立性により高度に並列化できるため、アウトオブオーダー実行CPUでパフォーマンスが向上します。

圧縮試行

基数木は、圧縮されたトライとも呼ばれ、スペースが最適化されたトライの変形であり、子が1つしかないノードがその親とマージされます。子が1つだけのノードのブランチを削除すると、スペースと時間の両方のメトリックが向上します。[15] :452 これは、トライが静的なままで、格納されているキーのセットが表現空間内で非常にまばらである次の条件下で最適に機能します。[16] :3-16 

もう1つのアプローチは、トライを「パック」することです。この場合、スパースパックされたトライのスペース効率の高い実装が自動ハイフネーションに適用され、各ノードの子孫がメモリにインターリーブされます。[7]

を試みます

接尾辞木を含むいくつかのトライバリアントは、外部メモリ内の文字列のセットを維持するのに適しています。このタスクでは、 Bトライと呼ばれるトライとBツリーの組み合わせも提案されています。接尾辞木と比較して、サポートされる操作には制限がありますが、更新操作をより高速に実行しながら、よりコンパクトになります。[17]

アプリケーション

Trieデータ構造は、予測テキストまたはオートコンプリート辞書、および近似一致アルゴリズムで一般的に使用されます。[18]試行により、検索が高速化され、占有するスペースが少なくなります。特に、セットに多数の短い文字列が含まれている場合は、スペルチェック、ハイフネーションアプリケーション、最長プレフィックス一致アルゴリズムで使用されます。[7] [11] :358 ただし、必要なのが辞書の単語の保存だけである場合(つまり、各単語に関連付けられたメタデータを保存する必要がない場合)、最小の決定論的非巡回有限状態オートマトン(DAFSA)または基数木はトライよりも少ないストレージスペースを使用します。これは、DAFSAと基数木が、格納されている異なる単語の同じ接尾辞(または部分)に対応するトライからの同一のブランチを圧縮できるためです。文字列辞書は、テキストコーパスの辞書の検索などの自然言語処理でも使用されます[19] :73 

並べ替え

文字列キーのセットの辞書式ソートは、指定されたキーのトライを作成し、事前注文方式でツリーをトラバースすることで実装できます。[20]これも基数ソートの形式です。[21]トライは、バーストソートの基本的なデータ構造でもあります。これは、2007年の時点で最速の文字列ソートアルゴリズムであることが注目されています[22]。これには、CPUキャッシュの効率的な使用が伴います。[23]

全文検索

接尾辞木と呼ばれる特別な種類のトライを使用して、テキスト内のすべての接尾辞にインデックスを付け、高速の全文検索を実行できます。[24]

Web検索エンジン

圧縮トライと呼ばれる特殊な種類のトライは、検索可能なすべての単語のコレクションであるインデックスを格納するためにWeb検索エンジンで使用されます。各ターミナルノードは、キーワードに一致するページへのURLのリスト(オカレンスリストと呼ばれる)に関連付けられています。トライはメインメモリに保存されますが、オカレンスは外部ストレージに保存され、多くの場合、大規模なクラスターに保存されます。[25] :368 

バイオインフォマティクス

トライは、バイオインフォマティクス、特にBLASTなどのシーケンスアラインメントソフトウェアアプリケーションで使用されます。BLASTは、圧縮されたトライシーケンスデータベースに出現位置を格納することにより、テキストの長さkk-mersと呼ばれる)のすべての異なるサブストリングにインデックスを付けます。[19] :75 

インターネットルーティング

転送情報ベース(FIB)を管理するためのデータベースなど、試行の圧縮されたバリアントは、 IPルーティングのマスクベースの操作を解決するためのプレフィックスベースのルックアップのためにルーターおよびブリッジ内にIPアドレスプレフィックスを格納する際に使用されます。[19] :75 

も参照してください

参照

  1. ^ トゥエ、アクセル(1912年)。"ÜberdiegegenseitigeLagegleicher TeilegewisserZeichenreihen"Skrifter udgivne af Videnskabs-SelskabetiChristiania1912(1):1–67。Knuthによって引用されました。
  2. ^ a b c d Knuth、ドナルド(1997)。「6.3:デジタル検索」。The Art of Computer Programming Volume 3:Sorting and Searching(2nd ed。)アディソン-ウェスリー。p。492. ISBN 0-201-89685-0
  3. ^ de la Briandais、René(1959)。可変長キーを使用したファイル検索(PDF)Proc。Western J.ComputerConf。pp。295–298。2020-02-11にオリジナル(PDF)からアーカイブされました。 真鍮とクヌースによって引用されました。
  4. ^ a b c d ブラス、ピーター(2008年9月8日)。高度なデータ構造英国ケンブリッジ大学出版局土井10.1017/CBO9780511800191ISBN 978-0521880374
  5. ^ a b エドワード・フレドキン(1960)。「トライメモリー」。ACMの通信3(9):490–499。土井10.1145/367390.367400
  6. ^ a b ブラック、ポールE.(2009-11-16)。「トライ」アルゴリズムとデータ構造の辞書米国国立標準技術研究所2011年4月29日にオリジナルからアーカイブされました。
  7. ^ a b c d フランクリン・マーク・リャン(1983)。Word Hy-phen-a-tion By Computer-er(PDF)(博士論文)。スタンフォード大学。2005年11月11日のオリジナルからアーカイブ(PDF)2010年3月28日取得
  8. ^ a b c d e f g Sedgewick、Robert ; ウェイン、ケビン(2011年4月3日)。アルゴリズム(4版)。アディソン-ウェスリープリンストン大学ISBN 978-0321573513
  9. ^ a b Gonnet、Gaston H .; Yates、GRicardo Baeza(1991年5月1日)。PascalおよびCのアルゴリズムとデータ構造のハンドブック(2版)。アメリカ合衆国ボストンAddison-WesleyETHチューリッヒISBN 978-0201416077
  10. ^ Patil、Virsha H.(2012年5月10日)。C++を使用したデータ構造オックスフォード大学出版局ISBN 9780198066231
  11. ^ a b c d Thareja、Reema(2018年10月13日)。「ハッシュと衝突」。Cを使用したデータ構造(2版)。オックスフォード大学出版局ISBN 9780198099307
  12. ^ Daciuk、1月(2003年6月24日)。文字列のセットからの最小、非周期的、決定論的、有限状態オートマトンの構築アルゴリズムの比較Automataの実装と適用に関する国際会議。シュプリンガーパブリッシングpp。255–261。土井10.1007/3-540-44977-9_26ISBN 978-3-540-40391-3
  13. ^ Bellekens、Xavier(2014)。「GPUで高速化された侵入検知システムのための高効率のメモリ圧縮スキーム」。情報とネットワークのセキュリティに関する第7回国際会議の議事録-SIN'14グラスゴー、スコットランド、英国:ACM。pp。302:302–302:309。arXiv1704.02272土井10.1145/2659651.2659723ISBN 978-1-4503-3033-6
  14. ^ Willar、Dan E.(1983年1月27日)。「対数対数の最悪の場合の範囲クエリは、スペースO(n)で可能です」17(2)。ScienceDirect:81–84。土井10.1016 / 0020-0190(83)90075-3 {{cite journal}}引用ジャーナルには|journal=ヘルプ)が必要です
  15. ^ Mehta、Dinesh P .; サルタージ・サーニ(2018年3月7日)。「トライ」。データ構造とアプリケーションのハンドブック(2版)。フロリダ大学チャップマン&ホールISBN 978-1498701853
  16. ^ Jan Daciuk; Stoyan Mihov; ブルース・W・ワトソン; リチャードE.ワトソン(2000年3月1日)。「最小の非巡回有限状態オートマトンのインクリメンタル構築」計算言語学MITプレス26(1)。土井10.1162/089120100561601
  17. ^ Askitis、ニコラス; ゾーベル、ジャスティン(2008)。「ディスクベースの文字列管理のB試行」(PDF)VLDBジャーナル:1–26。ISSN1066-8888_  
  18. ^ Aho、Alfred V .; コラシック、マーガレットJ.(1975年6月)。「効率的な文字列照合:書誌検索の支援」(PDF)ACMの通信18(6):333–340。土井10.1145/360825.360855
  19. ^ a b c Martinez-Prieto、Miguel A .; Brisaboa、Nieves; Canovas、Rodrigo; クロード、フランシスコ; ナバロ、ゴンザロ(2016年3月)。「実用的な圧縮文字列辞書」情報システムエルゼビア56土井10.1016/j.is.2015.08.008ISSN0306-4379_ 
  20. ^ Kärkkäinen、Juha。「レクチャー2」(PDF)ヘルシンキ大学トライ内のノードの事前順序は、ノードの子がエッジラベルによって順序付けられていると仮定して、それらが表す文字列の辞書式順序と同じです。
  21. ^ カリス、ラファエル(2018)。「適応基数木(レポート#14-708-887)」(PDF)チューリッヒ大学:情報学部、研究出版物
  22. ^ Ranjan Sinha、Justin Zobel、David Ring(2006年2月)。「コピーを使用したキャッシュ効率の高い文字列ソート」(PDF)ACM Journal ofExperimentalAlgorithmics11:1〜32。土井10.1145/1187436.1187439
  23. ^ J.KärkkäinenおよびT.Rantala(2008)。「文字列の基数ソートのエンジニアリング」。A.アミールとA.ターピンとA.モファット(編)。文字列処理と情報検索、Proc。SPIREコンピュータサイエンスの講義ノート。5280.スプリンガー。pp。3–14。土井10.1007/978-3-540-89097-3_3
  24. ^ 「アプリケーションを使用した正方行列への接尾辞木の一般化」SIAM JournalonComputing工業応用数学学会24(3):520–562。1992年5月28日。doi10.1137/S0097539792231982ISSN0097-5397_ 
  25. ^ Thenmozhi、M .; Srimathi、H.(2015年2月)。「さまざまなデータ使用モデルを使用したツリーおよびトライベースの辞書実装のパフォーマンスに関する分析」(PDF)Indian Journal of LawandTechnologySRMインスティテュートオブサイエンスアンドテクノロジー8(4)。土井10.17485 / ijst / 2015 / v8i4/598652022年1月22日のオリジナルからアーカイブ(PDF)2022年1月22日取得

外部リンク