トライ

トライ
トライ
タイプ	木
発明された	1960
発明者	エドワード・フレドキン、アクセル・テュー、ルネ・ド・ラ・ブリアンデ
手術
ビッグ O 記法による時間計算量
手術	平均
検索	の上）
入れる	の上）
消去	の上）
空間の複雑さ
空間	の上）

コンピュータサイエンスにおいて、トライ（/ ˈ t r aɪ /、/ ˈ t r iː / ）は、デジタルツリーまたはプレフィックスツリーとも呼ばれ、^[1]辞書またはセットから文字列を格納および取得するために使用される特殊な検索ツリーデータ構造です。バイナリ検索ツリーとは異なり、トライのノードは関連するキーを格納しません。代わりに、トライ内の各ノードの位置によって関連するキーが決定され、ノード間の接続はキー全体ではなく個々の文字によって定義されます。

トライは、プレフィックスベースの編成とハッシュ衝突がないことによるハッシュテーブルよりも優れた利点があり、オートコンプリート、スペルチェック、IP ルーティングなどのタスクに特に効果的です。すべての子ノードは親ノードと共通のプレフィックスを共有し、ルートノードは空の文字列を表します。基本的なトライの実装はメモリを大量に消費する可能性がありますが、効率を向上させるために、圧縮やビット単位の表現などのさまざまな最適化手法が開発されています。注目すべき最適化は、より効率的なプレフィックスベースのストレージを提供する基数木です。

トライは一般的に文字列を格納しますが、数字や形状の順列など、任意の順序付けられた要素のシーケンスを扱うように適応させることができます。注目すべきバリエーションは、固定長のバイナリデータ (整数やメモリアドレスなど) の個々のビットをキーとして使用するビット単位のトライです。

歴史、語源、発音

文字列の集合を表すトライの概念は、1912年にアクセル・トゥーによって初めて抽象的に記述された。 ^[2]^[3]トライは、1959年にルネ・デ・ラ・ブリアンデイによって初めてコンピュータのコンテキストで記述された。^[4]^[3]^[5]^{: 336}

このアイデアは1960年にエドワード・フレドキンによって独立に説明され、^[6]彼はtrieという用語を造り出し、retrievalの中間音節にちなんで/ ˈ t r iː / (「tree」の意) と発音した。^[7]^{[8]しかし、他の著者はそれを}/ ˈ t r aɪ / (「try」の意)と発音し、口頭で tree と区別しようとした。^[7]^[8]^[3]

概要

トライは文字列インデックス付きの検索データ構造の一種で、補完リストを効率的に生成できるような方法で検索できる単語の辞書リストを格納するのに使われます。^[9]^[10]^{: 1}プレフィックストライは有限のアルファベットセット上の文字列セットを表現するのに使われる順序付きツリーデータ構造で、共通のプレフィックスを持つ単語を効率的に格納できます。^[1]

トライは、予測テキスト、近似文字列マッチング、スペルチェックなどの文字列検索アルゴリズムにおいて、二分探索木に比べて効果的である。 ^[11]^[8]^[12]^{: 358}トライは、木の形をした決定論的有限オートマトンと見なすことができる。^[13]

オペレーション

トライは、挿入、削除、文字列キーの検索など、さまざまな操作をサポートしています。トライは、他のサフィックスの子ノードまたはnullを指すリンクを含むノードで構成されています。すべてのツリーと同様に、ルート以外の各ノードは、その親と呼ばれる他の 1 つのノードによってのみポイントされます。各ノードには、適用可能なアルファベットの文字数と同じ数のリンクが含まれます(ただし、トライにはかなりの数の null リンクが含まれる傾向があります)。場合によっては、使用されるアルファベットは単に文字エンコーディングのアルファベットであり、たとえば (符号なし) ASCIIの場合はサイズが 256 になります。^[14]^{: 732}

ノードの子ノード内のヌルリンクは、以下の特性を強調します。^[14]^{: 734}^[5]^{: 336}

文字と文字列キーは暗黙的にトライに格納され、文字列の終了を示す文字センチネル値が含まれます。
各ノードには、セットの強力なキーのプレフィックスへの 1 つの可能なリンクが含まれます。

トライ内のノードの基本的な構造型は次のとおりです。オプションのが含まれる場合があります。これは、文字列の最後の文字、つまり終端ノードに格納されている各キーに関連付けられています。 ${\text{ノード}}$ ${\text{値}}$

検索中

トライ内の値の検索は、検索文字列キーの文字によってガイドされます。トライ内の各ノードには、指定された文字列の各文字に対応するリンクが含まれています。したがって、トライ内の文字列をたどると、指定された文字列キーに関連付けられた値が得られます。検索中にヌルリンクが表示された場合は、キーが存在しないことを示します。^[14]^{: 732-733}

次の擬似コードは、ルート付きトライ木x内の指定された文字列キーの検索手順を実装している。^[15]^{: 135}

上記の擬似コードでは、xとkey はそれぞれトライのルートノードのポインタと文字列キーに対応します。標準トライでの検索操作には時間がかかり、ここでは文字列パラメータのサイズで、アルファベットのサイズに対応します。^[16]^{: 754}一方、二分探索木では、最悪の場合がかかります。これは、検索が BST の木の高さ ( ) に依存するためです(バランスの取れた木の場合)。ここでとはキーの数とキーの長さです。^[12]^{: 358} $O({\text{dm}})$ ${\text{m}}$ ${\text{キー}}$ ${\text{d}}$ $O(m\log n)$ $\log n$ ${\text{n}}$ ${\text{m}}$

トライは、ノードが共通の初期文字列サブシーケンスを共有し、キーを暗黙的に格納するため、短い文字列が多数ある場合、BSTと比較して占有するスペースが少なくなります。^[12]^{: 358}ツリーの終端ノードにはnull以外の値が含まれており、関連する値がトライで見つかった場合は検索ヒット、見つからない場合は検索ミスとなります。 ^[14]^{: 733}

挿入

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

文字列キーの最後の文字に到達する前にヌルリンクに遭遇した場合、新しいノードが作成される（3行目）。^[14]^：745終端ノードの値は入力値に割り当てられるため、挿入時に前者がヌルでなかった場合は新しい値に置き換えられます。

削除

トライからキーと値のペアを削除するには、対応する文字列キーを持つ終端ノードを見つけ、終端インジケータと値をそれぞれfalseとnullにマークする必要があります。^[14]^{: 740}

以下は、ルート付きトライ（ x ）から文字列キーを削除するための再帰的な手順です。

この手順は、キーを調べることから始まります。null は、終端ノードまたは文字列キーの終了の到着を示します。ノードが終端で子を持たない場合、そのノードはトライから削除されます (行 14)。ただし、ノードが終端でない文字列キーの終了は、キーが存在しないことを示すため、この手順はトライを変更しません。再帰は、キーのインデックスを増分しながら続行されます。

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

ハッシュテーブルの代替

トライはハッシュテーブルの代わりに使用することができ、ハッシュテーブルに比べて次のような利点がある: ^[12]^{: 358}

サイズの関連キーを持つノードの検索にはの複雑度がありますが、不完全なハッシュ関数には多数の衝突するキーがある可能性があり、そのようなテーブルの最悪ケースの検索速度はになります。ここで、はテーブル内のノードの総数を表します。 $m$ $O(m)$ $O(N)$ $N$
トライはハッシュテーブルとは異なり、操作にハッシュ関数を必要としません。また、トライでは異なるキーの衝突もありません。
トライ内のバケットは、キーの衝突を格納するハッシュテーブルバケットに類似しており、単一のキーが複数の値に関連付けられている場合にのみ必要です。
トライ内の文字列キーは、事前に決められたアルファベット順で並べ替えることができます。

しかし、ハードディスクドライブなどの二次記憶装置上のデータが、メインメモリよりもランダムアクセス時間が長い場合、トライはハッシュテーブルよりも効率が悪い。 ^[6]また、浮動小数点数など、複数の表現が可能なキー値（たとえば、1は1.0、+1.0、1.00など）を文字列として簡単に表現できない場合にも、トライは不利である。 ^[12]^{: 359}ただし、 2の補数形式と比較すると、IEEE 754では2進数として明確に表現できる。^[17]

実装戦略

トライは、メモリ使用量と操作速度のトレードオフに応じて、いくつかの方法で表現できます。^[5]^{: 341}トライを表現するためにポインタのベクトルを使用すると、膨大なスペースを消費します。ただし、各ノードベクトルに単方向リンクリストを使用すると、ベクトルのほとんどのエントリにが含まれるため、実行時間を犠牲にしてメモリスペースを削減できます。^[3]^{: 495} ${\text{nil}}$

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

ビット単位の試行

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

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

圧縮トライ

圧縮トライとも呼ばれる基数木は、トライの空間最適化版であり、子が1つしかないノードは親とマージされます。子が1つのノードの枝を削除すると、空間と時間の両方でメトリックが向上します。^[20]^[21]^{: 452}これは、トライが静的であり、格納されているキーのセットが表現空間内で非常にまばらである場合に最も効果的です。^[22]^{: 3–16}

もう一つのアプローチはトライを「パック」することであり、これはスパースパックトライのスペース効率の高い実装を自動ハイフネーションに適用し、各ノードの子孫をメモリ内でインターリーブすることができる。^[8]

パトリシアの木

文字列セット{in、integer、interval、string、structure}のパトリシア木表現。

パトリシア木は、圧縮バイナリトライの特定の実装であり、その表現に文字列キーのバイナリエンコードを使用します。 ^[23]^[15]^{: 140}パトリシア木のすべてのノードには、「スキップ番号」と呼ばれるインデックスが含まれており、トラバース中に空のサブツリーを回避するためにノードの分岐インデックスが格納されます。^[15]^{: 140-141}トライの単純な実装では、キーの疎な分布によって多数のリーフノードが発生するため、膨大なストレージを消費します。パトリシア木は、このような場合に効率的です。^[15]^{: 142}^[24]^{: 3}

右にパトリシアツリーの表現を示します。ノードに隣接する各インデックス値は「スキップ番号」、つまり分岐を決定するビットのインデックスを表します。^[24]^{: 3}ノード 0 のスキップ番号 1 は、キーセットの左端のビットが異なるバイナリエンコードされた ASCII の位置 1 に対応します。^[24]^{: 3-4}スキップ番号は、パトリシアツリーのノードの検索、挿入、削除に非常に重要であり、反復ごとにビットマスク操作が実行されます。^[15]^{: 143} $X$

アプリケーション

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

ソート

文字列キーの集合の辞書式ソートは、与えられたキーに対してトライを構築し、そのツリーを事前順序方式で走査することによって実装することができる。^[26]これも基数ソートの一種である。^{[27]トライは}バーストソートの基本的なデータ構造でもあり、バーストソートは2007年時点で最も高速な文字列ソートアルゴリズムとして注目されている。 ^{[28]これはCPU}キャッシュを効率的に使用することで実現されている。^[29]

全文検索

サフィックスツリーと呼ばれる特殊な種類のトライ木は、テキスト内のすべてのサフィックスをインデックス化し、高速な全文検索を実行するために使用できます。 ^[30]

ウェブ検索エンジン

圧縮トライと呼ばれる特殊な種類のトライは、ウェブ検索エンジンでインデックス（検索可能なすべての単語のコレクション）を格納するために使用されます。 ^{[31]各ターミナルノードは、キーワードに一致するページの}URLのリスト（オカレンスリストと呼ばれる）に関連付けられています。トライはメインメモリに格納されますが、オカレンスは外部ストレージ（多くの場合、大きなクラスター）に保持されます。または、メモリ内インデックスは外部の場所に格納されたドキュメントを指します。^[32]

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

トライはバイオインフォマティクス、特にBLASTなどの配列アライメントソフトウェアアプリケーションで使用され、テキスト中の長さkの異なる部分文字列（k-merと呼ばれる）の出現位置を圧縮されたトライ配列データベースに格納することでインデックスを作成します。^[25]^：75

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

転送情報ベース（FIB）を管理するためのデータベースなどの圧縮されたトライの変種は、 IPルーティングにおけるマスクベースの操作を解決するためのプレフィックスベースのルックアップのために、ルータやブリッジ内にIPアドレスプレフィックスを格納するために使用されます。^[25]^：75

参照

参考文献

^ ab Maabar, Maha (2014年11月17日). 「Trie Data Structure」. CVR,グラスゴー大学. 2021年1月27日時点のオリジナルよりアーカイブ。 2022年4月17日閲覧。
^ 木曜日、アクセル (1912). 「Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen」。Skrifter Udgivne Af Videnskabs-Selskabet I Christiania。1912 (1): 1–67。Knuth による引用。
^ abcd Knuth, Donald (1997). 「6.3: デジタル検索」.コンピュータプログラミングの技法第3巻: ソートと検索(第2版). Addison-Wesley. p. 492. ISBN 0-201-89685-0。
^ de la Briandais, René (1959). 可変長キーを使用したファイル検索(PDF) . Proc. Western J. Computer Conf. pp. 295–298. doi :10.1145/1457838.1457895. S2CID 10963780. 2020-02-11にオリジナル(PDF)からアーカイブ。Brass と Knuth によって引用されています。
^ abcd Brass, Peter (2008年9月8日). Advanced Data Structures.イギリス: Cambridge University Press . doi :10.1017/CBO9780511800191. ISBN 978-0521880374。
^ ab Edward Fredkin (1960). 「トライメモリ」Communications of the ACM . 3 (9): 490–499. doi : 10.1145/367390.367400 . S2CID 15384533.
^ ab Black, Paul E. (2009-11-16). 「trie」.アルゴリズムとデータ構造の辞書。国立標準技術研究所。2011-04-29時点のオリジナルよりアーカイブ。
^ abcde Franklin Mark Liang (1983). Word Hy-phen-a-tion By Comp-comp-er (PDF) (哲学博士論文). スタンフォード大学. 2005-11-11 のオリジナルからアーカイブ(PDF) 。2010-03-28に取得。
^ “Trie”. ラトガース大学芸術科学部. 2022年. 2022年4月17日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。
^ Connelly, Richard H.; Morris, F. Lockwood (1993). 「トライデータ構造の一般化」.コンピュータサイエンスにおける数学的構造. 5 (3).シラキュース大学: 381–418. doi :10.1017/S0960129500000803. S2CID 18747244.
^ ab Aho, Alfred V.; Corasick, Margaret J. (1975 年 6 月). 「効率的な文字列マッチング: 書誌検索の補助」. Communications of the ACM . 18 (6): 333–340. doi : 10.1145/360825.360855 . S2CID 207735784.
^ abcdef Thareja, Reema (2018年10月13日). 「ハッシュと衝突」. Cを使用したデータ構造（第2版）. Oxford University Press . ISBN 9780198099307。
^ Daciuk, Jan (2003 年 6 月 24 日)。文字列セットからの最小、非巡回、決定論的、有限状態オートマトンの構築アルゴリズムの比較。オートマトン実装および応用に関する国際会議。Springer Publishing。pp . 255–261。doi : 10.1007 /3-540-44977-9_26。ISBN 978-3-540-40391-3。
^ abcdefg セジウィック、ロバート、ウェイン、ケビン（ 2011年4月3日）。アルゴリズム（第4版）。アディソン・ウェズリー、プリンストン大学。ISBN 978-0321573513。
^ abcdef Gonnet, GH; Yates, R. Baeza (1991年1月). アルゴリズムとデータ構造のハンドブック: PascalとC (第2版).ボストン、アメリカ合衆国: Addison-Wesley . ISBN 978-0-201-41607-7。
^ Patil, Varsha H. (2012 年 5 月 10 日). C++ を使用したデータ構造. Oxford University Press . ISBN 9780198066231。
^ S. Orley; J. Mathews. 「IEEE 754フォーマット」。 エモリー大学数学・コンピュータサイエンス学部。2022年3月28日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。
^ Bellekens, Xavier (2014)。「GPU アクセラレーション侵入検知システム向けの高効率メモリ圧縮方式」。情報とネットワークのセキュリティに関する第 7 回国際会議 SIN '14 の議事録。グラスゴー、スコットランド、英国: ACM。pp. 302:302–302:309。arXiv : 1704.02272。doi : 10.1145 / 2659651.2659723。ISBN 978-1-4503-3033-6. S2CID 12943246。
^ ab Willar, Dan E. (1983年1月27日). 「対数対数最悪ケース範囲クエリはスペースO(n)で可能」. Information Processing Letters . 17 (2): 81–84. doi :10.1016/0020-0190(83)90075-3.
^ Sartaj Sahni (2004). 「C++ のデータ構造、アルゴリズム、アプリケーション: トライ」.フロリダ大学. 2016年7月3日時点のオリジナルよりアーカイブ。 2022年4月17日閲覧。
^ Mehta, Dinesh P.; Sahni, Sartaj ( 2018年 3 月 7 日)。「Tries」。データ構造とアプリケーションのハンドブック (第 2 版)。Chapman & Hall、フロリダ大学。ISBN 978-1498701853。
^ Jan Daciuk、Stoyan Mihov、Bruce W. Watson、Richard E. Watson (2000 年 3 月 1 日)。「Incremental Construction of Minimal Acyclic Finite-State Automata」。Computational Linguistics 26 ( 1 )。MIT Press : 3–16。arXiv : cs/0007009。Bibcode : 2000cs......7009D。doi : 10.1162/ 089120100561601。
^ “Patricia tree”. National Institute of Standards and Technology . 2022年2月14日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。
^ abc Crochemore, Maxime; Lecroq, Thierry (2009). 「Trie」. Encyclopedia of Database Systems.ボストン、アメリカ合衆国: Springer Publishing . Bibcode :2009eds..book.....L. doi :10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0– HAL (オープンアーカイブ)経由。
^ abc Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (2016 年 3 月). 「実用的な圧縮文字列辞書」.情報システム. 56. Elsevier : 73–108. doi :10.1016/j.is.2015.08.008. ISSN 0306-4379.
^ Kärkkäinen, Juha. 「講義 2」(PDF)。ヘルシンキ大学。トライ内のノードの事前順序は、ノードの子がエッジラベルによって順序付けられていると仮定すると、それらが表す文字列の辞書式順序と同じです。
^ Kallis, Rafael (2018). 「適応型基数木 (レポート #14-708-887)」(PDF)。チューリッヒ大学: 情報学部、研究出版物。
^ Ranjan Sinha、Justin Zobel、David Ring (2006 年 2 月)。「コピーを使用し たキャッシュ効率の良い文字列ソート」(PDF)。ACM Journal of Experimental Algorithmics。11 : 1–32。doi : 10.1145 /1187436.1187439。S2CID 3184411。
^ J. Kärkkäinen および T. Rantala (2008)。「文字列の基数ソートのエンジニアリング」。A. Amir、A. Turpin、A. Moffat (編)。文字列処理と情報検索、Proc. SPIRE。コンピュータサイエンスの講義ノート。Vol. 5280。Springer。pp. 3–14。doi :10.1007 / 978-3-540-89097-3_3。ISBN 978-3-540-89096-6。
^ Giancarlo, Raffaele (1992 年 5 月 28 日). 「Suffix Tree の正方行列への一般化とその応用」. SIAM Journal on Computing . 24 (3). Society for Industrial and Applied Mathematics : 520–562. doi :10.1137/S0097539792231982. ISSN 0097-5397.
^ Yang, Lai; Xu, Lida; Shi, Zhongzhi (2012 年 3 月 23 日). 「語彙検索のための強化された動的ハッシュ TRIE アルゴリズム」.エンタープライズ情報システム. 6 (4): 419–432. Bibcode :2012EntIS...6..419Y. doi :10.1080/17517575.2012.665483. S2CID 37884057.
^ Transier, Frederik; Sanders, Peter (2010 年 12 月). 「インメモリテキスト検索エンジンの基本アルゴリズムのエンジニアリング」. ACM Transactions on Information Systems . 29 (1). Association for Computing Machinery : 1–37. doi :10.1145/1877766.1877768. S2CID 932749.

外部リンク

NIST のアルゴリズムとデータ構造の辞書: トライ

[cvr14-1] Maabar, Maha (2014年11月17日). 「Trie Data Structure」. CVR,グラスゴー大学. 2021年1月27日時点のオリジナルよりアーカイブ。 2022年4月17日閲覧。

[thue-2] 木曜日、アクセル (1912). 「Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen」。Skrifter Udgivne Af Videnskabs-Selskabet I Christiania。1912 (1): 1–67。Knuth による引用。

[KnuthVol3-3] Knuth, Donald (1997). 「6.3: デジタル検索」.コンピュータプログラミングの技法第3巻: ソートと検索(第2版). Addison-Wesley. p. 492. ISBN 0-201-89685-0。

[4] Briandais, René (1959). 可変長キーを使用したファイル検索(PDF) . Proc. Western J. Computer Conf. pp. 295–298. doi :10.1145/1457838.1457895. S2CID 10963780. 2020-02-11にオリジナル(PDF)からアーカイブ。Brass と Knuth によって引用されています。

[brass-5] Brass, Peter (2008年9月8日). Advanced Data Structures.イギリス: Cambridge University Press . doi :10.1017/CBO9780511800191. ISBN 978-0521880374。

[triememory-6] Edward Fredkin (1960). 「トライメモリ」Communications of the ACM . 3 (9): 490–499. doi : 10.1145/367390.367400 . S2CID 15384533.

[DADS-7] Black, Paul E. (2009-11-16). 「trie」.アルゴリズムとデータ構造の辞書。国立標準技術研究所。2011-04-29時点のオリジナルよりアーカイブ。

[Liang1983-8] Franklin Mark Liang (1983). Word Hy-phen-a-tion By Comp-comp-er (PDF) (哲学博士論文). スタンフォード大学. 2005-11-11 のオリジナルからアーカイブ(PDF) 。2010-03-28に取得。

[9] ^ “Trie”. ラトガース大学芸術科学部. 2022年. 2022年4月17日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。

[10] Connelly, Richard H.; Morris, F. Lockwood (1993). 「トライデータ構造の一般化」.コンピュータサイエンスにおける数学的構造. 5 (3).シラキュース大学: 381–418. doi :10.1017/S0960129500000803. S2CID 18747244.

[aho75-11] Aho, Alfred V.; Corasick, Margaret J. (1975 年 6 月). 「効率的な文字列マッチング: 書誌検索の補助」. Communications of the ACM . 18 (6): 333–340. doi : 10.1145/360825.360855 . S2CID 207735784.

[reema18-12] Thareja, Reema (2018年10月13日). 「ハッシュと衝突」. Cを使用したデータ構造（第2版）. Oxford University Press . ISBN 9780198099307。

[13] Daciuk, Jan (2003 年 6 月 24 日)。文字列セットからの最小、非巡回、決定論的、有限状態オートマトンの構築アルゴリズムの比較。オートマトン実装および応用に関する国際会議。Springer Publishing。pp . 255–261。doi : 10.1007 /3-540-44977-9_26。ISBN 978-3-540-40391-3。

[robert11-14] セジウィック、ロバート、ウェイン、ケビン（ 2011年4月3日）。アルゴリズム（第4版）。アディソン・ウェズリー、プリンストン大学。ISBN 978-0321573513。

[gonnet91-15] Gonnet, GH; Yates, R. Baeza (1991年1月). アルゴリズムとデータ構造のハンドブック: PascalとC (第2版).ボストン、アメリカ合衆国: Addison-Wesley . ISBN 978-0-201-41607-7。

[patil_12-16] Patil, Varsha H. (2012 年 5 月 10 日). C++ を使用したデータ構造. Oxford University Press . ISBN 9780198066231。

[17] ^ S. Orley; J. Mathews. 「IEEE 754フォーマット」。 エモリー大学数学・コンピュータサイエンス学部。2022年3月28日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。

[18] Bellekens, Xavier (2014)。「GPU アクセラレーション侵入検知システム向けの高効率メモリ圧縮方式」。情報とネットワークのセキュリティに関する第 7 回国際会議 SIN '14 の議事録。グラスゴー、スコットランド、英国: ACM。pp. 302:302–302:309。arXiv : 1704.02272。doi : 10.1145 / 2659651.2659723。ISBN 978-1-4503-3033-6. S2CID 12943246。

[willar83-19] Willar, Dan E. (1983年1月27日). 「対数対数最悪ケース範囲クエリはスペースO(n)で可能」. Information Processing Letters . 17 (2): 81–84. doi :10.1016/0020-0190(83)90075-3.

[20] Sartaj Sahni (2004). 「C++ のデータ構造、アルゴリズム、アプリケーション: トライ」.フロリダ大学. 2016年7月3日時点のオリジナルよりアーカイブ。 2022年4月17日閲覧。

[21] ^ Mehta, Dinesh P.; Sahni, Sartaj ( 2018年 3 月 7 日)。「Tries」。データ構造とアプリケーションのハンドブック (第 2 版)。Chapman & Hall、フロリダ大学。ISBN 978-1498701853。

[22] Jan Daciuk、Stoyan Mihov、Bruce W. Watson、Richard E. Watson (2000 年 3 月 1 日)。「Incremental Construction of Minimal Acyclic Finite-State Automata」。Computational Linguistics 26 ( 1 )。MIT Press : 3–16。arXiv : cs/0007009。Bibcode : 2000cs......7009D。doi : 10.1162/ 089120100561601。

[23] “Patricia tree”. National Institute of Standards and Technology . 2022年2月14日時点のオリジナルよりアーカイブ。2022年4月17日閲覧。

[maxime09-24] Crochemore, Maxime; Lecroq, Thierry (2009). 「Trie」. Encyclopedia of Database Systems.ボストン、アメリカ合衆国: Springer Publishing . Bibcode :2009eds..book.....L. doi :10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0– HAL (オープンアーカイブ)経由。

[prieto16-25] Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (2016 年 3 月). 「実用的な圧縮文字列辞書」.情報システム. 56. Elsevier : 73–108. doi :10.1016/j.is.2015.08.008. ISSN 0306-4379.

[26] Kärkkäinen, Juha. 「講義 2」(PDF)。ヘルシンキ大学。トライ内のノードの事前順序は、ノードの子がエッジラベルによって順序付けられていると仮定すると、それらが表す文字列の辞書式順序と同じです。

[27] Kallis, Rafael (2018). 「適応型基数木 (レポート #14-708-887)」(PDF)。チューリッヒ大学: 情報学部、研究出版物。

[cachestringsort-28] ^ Ranjan Sinha、Justin Zobel、David Ring (2006 年 2 月)。「コピーを使用し たキャッシュ効率の良い文字列ソート」(PDF)。ACM Journal of Experimental Algorithmics。11 : 1–32。doi : 10.1145 /1187436.1187439。S2CID 3184411。

[stringradix-29] J. Kärkkäinen および T. Rantala (2008)。「文字列の基数ソートのエンジニアリング」。A. Amir、A. Turpin、A. Moffat (編)。文字列処理と情報検索、Proc. SPIRE。コンピュータサイエンスの講義ノート。Vol. 5280。Springer。pp. 3–14。doi :10.1007 / 978-3-540-89097-3_3。ISBN 978-3-540-89096-6。

[30] Giancarlo, Raffaele (1992 年 5 月 28 日). 「Suffix Tree の正方行列への一般化とその応用」. SIAM Journal on Computing . 24 (3). Society for Industrial and Applied Mathematics : 520–562. doi :10.1137/S0097539792231982. ISSN 0097-5397.

[Xu12-31] Yang, Lai; Xu, Lida; Shi, Zhongzhi (2012 年 3 月 23 日). 「語彙検索のための強化された動的ハッシュ TRIE アルゴリズム」.エンタープライズ情報システム. 6 (4): 419–432. Bibcode :2012EntIS...6..419Y. doi :10.1080/17517575.2012.665483. S2CID 37884057.

[32] Transier, Frederik; Sanders, Peter (2010 年 12 月). 「インメモリテキスト検索エンジンの基本アルゴリズムのエンジニアリング」. ACM Transactions on Information Systems . 29 (1). Association for Computing Machinery : 1–37. doi :10.1145/1877766.1877768. S2CID 932749.

トライ