Try を表現する方法はいくつかあり、メモリ使用量と演算速度のトレードオフが異なることに対応している。 基本的な形式はノードのリンクセットで、各ノードはアルファベットの各シンボルに対して1つの子ポインタの配列を含む (したがって英語のアルファベットに対しては、26の子ポインタ、バイトのアルファベットに対しては256のポインタを格納することになる)。 バイトのアルファベット（サイズ256）と4バイトのポインタを使用すると、各ノードは1キロバイトのストレージを必要とし、文字列の接頭辞にほとんど重複がない場合、必要なノード数は格納されている文字列の長さを合わせたものとほぼ同じになります。341 別の言い方をすると、ツリーの底に近いノードは子ノードが少ない傾向があり、その数は多いので、構造体はヌルポインターを格納するスペースを浪費します。
ストレージの問題は、アルファベット縮小と呼ばれる実装技術によって軽減することができ、それによって元の文字列はより小さいアルファベット上の長い文字列に再解釈されます。 例えば、nバイトの文字列は、代わりに2n個の4ビット単位の文字列とみなすことができ、ノードあたり16個のポインタを持つトライに格納される。 最悪の場合、検索は 2 倍のノードを訪問する必要がありますが、ストレージ要件は 8 分の 1 に減少します。 子の集合は二項探索木として表現することもできる。このアイデアの一例として、BentleyとSedgewickが開発した三項探索木がある。353
前に提案したような 256 のポインターの配列（ASCII）の使用を避けるためのもう一つの代替案は、アルファベット配列を ASCII アルファベットを表す 256 ビットのビットマップとして格納し、ノードのサイズを劇的に減らすことである。 信頼できるソースの引用を追加することによって、このセクションを改善するために貢献してください。 ソースのないものは、異議を唱えられ、削除されることがあります。 (2015 年 2 月) (このテンプレート メッセージを削除する方法とタイミングを学ぶ)
Bitwise トライは、個々のビットが事実上バイナリ ツリーの形式になるものを横断するために使用されることを除いて、通常の文字ベースのトライとほとんど同じです。 一般に、実装では特別な CPU 命令を使用して、固定長のキー (例えば、GCC の __builtin_clz() 組込み) の最初のセットビットを非常に迅速に見つけます。 この値は、32 または 64 エントリーのテーブルのインデックスとして使用され、ビットワイズトライでその数の先頭のゼロビットを持つ最初のアイテムを指します。 この処理は遅く聞こえるかもしれませんが、非常にキャッシュローカルで、レジスタ依存がないため高度に並列化でき、実際、最新のアウトオブオーダー実行 CPU で優れた性能を発揮します。 例えば、赤黒木は紙面上ではもっと良い性能を発揮しますが、キャッシュに非常に疎く、最近のCPUでは複数のパイプラインやTLBのストールを引き起こすため、このアルゴリズムはCPU速度ではなくメモリのレイテンシに拘束されることになります。 それに比べ、ビットワイズトライはメモリにほとんどアクセスせず、アクセスしても読み込むだけなので、SMPキャッシュコヒーレンシのオーバーヘッドを回避することができます。 したがって、メモリアロケータ（例えば、有名なDoug Leaのアロケータ（dlmalloc）とその子孫の最近のバージョン）のような、多くの高速な挿入と削除を実行するコードに選ばれるアルゴリズムになりつつあるのです。 ルックアップのためのステップの最悪のケースは、ツリーのビンのインデックスに使用されるビットと同じです。
あるいは、「ビットワイズトライ」という用語は、より一般的には、整数値を保持しバイナリプレフィックスでソートしたバイナリツリー構造を指すことがあります。 1125>
Compressing triesEdit
トライを圧縮して共通のブランチをマージすると、大きなパフォーマンス向上が得られることがあります。 これは以下の条件で最も効果的です:
- トライは（ほとんど）静的で、キーの挿入や削除は必要ありません（例：トライの一括作成後）
- 検索のみが必要です
- トライのノードがノード固有のデータによりキーイングされていないか、ノードのデータが共通である。
- 保存されたキーの総セットは、その表現空間内で非常にまばらです (したがって圧縮は有益です)。
たとえば、まばらなビットセット、つまりはるかに大きな固定列挙可能セットのサブセットを表すために使用することができます。 このような場合、トライはフルセット内のビットエレメントの位置でキーが設定される。 キーは、各要素の積分位置を符号化するのに必要なビット列から作成される。 このようなトライは、多くの欠落した枝を持つ非常に退化した形式である。 共通パターンの繰り返しを検出するか、未使用のギャップを埋めた後、固有のリーフ ノード (ビット文字列) を保存して簡単に圧縮し、トライの全体サイズを縮小できます。
このような圧縮は、Unicode 文字プロパティを取得するためのさまざまな高速ルックアップ テーブルの実装でも使用されます。 これには、大文字と小文字のマッピング テーブル (たとえば、ギリシャ文字の π から π へ) や、基本文字と結合文字の組み合わせを正規化する検索テーブル (ドイツ語の a-umlaut の ä や、聖書ヘブライ語の dalet-patah-dagesh-ole の דַּ֫ など) が含まれます。 このような用途では、非常に大きな一次元の疎な表（例えば、ユニコードのコードポイント）をそれらの組み合わせの多次元行列に変換し、その超行列の座標を非圧縮トライの文字列キーとして使用して、結果の文字を表すのと同様の表現となる。 圧縮は、ハイパーマトリックス内の共通の列を検出してマージし、キーの最後の次元を圧縮することで行われます。 たとえば、行列の列を形成する各要素の完全なマルチバイト Unicode コードポイントを保存しないように、類似のコードポイントのグループ化を利用することができます。 ハイパーマトリックスの各次元は、次の次元の開始位置を格納するので、オフセット（通常は 1 バイト）だけを格納すればよい。 結果として得られるベクトルもスパースであればそれ自体が圧縮可能であるため、各次元 (トライのレイヤー レベルに関連) を個別に圧縮することができます。 しかし、圧縮されたセグメントを分割またはマージする必要がある場合、これには通常大きなコストがかかります。 データ圧縮と更新速度の間で何らかのトレードオフを行う必要があります。 典型的な戦略は、疎なトライの共通ブランチを比較するためのグローバル検索の範囲を制限することである。
このような圧縮の結果は、トライを有向無サイクルグラフ (DAG) に変換しようとすることに似ているかもしれないが、これは DAG からトライへの逆の変換が明らかであり、常に可能であるためである。 しかし、DAG の形状は、ノードのインデックスを付けるために選択されたキーの形式によって決定され、その結果、可能な圧縮が制限されます。 これにより、メモリマッピングと仮想メモリの使用が可能になり、ディスクから効率的にデータをロードできるようになる。 Liangは自動ハイフネーションに適用される疎なパックトライの空間効率の良い実装について述べており、そこでは各ノードの子孫はメモリ内でインターリーブされるかもしれない。
外部メモリのトライ編
いくつかのトライ亜種が外部メモリ内の文字列集合の維持に適しており、サフィックスツリーがある。 接尾辞木と比較すると、サポートされる操作に制限があるが、よりコンパクトであり、更新操作をより速く行うことができる。