私がもっと読むことを試みることは、私が何らかの理由でより混乱することを試みます。
私を混乱させているのは、次のとおりです。
私は2種類の実装について読んだことがあります。
- 配列を使って文字を表現する（文字を格納しない） そして、各ノードに実際の単語へのインデックスも格納します（もし 私たちは言葉に達しました）。
- を使って
Collection文字を格納するノードの数 各ノードの単語がブーリアンを使って単語に到達したかを判断 この道を進む
最初のケースでは言及されていませんが、実際にはすべての辞書の単語を保持する必要があるようです（間接的に参照しているため）。だから我々は持っています array_size*numberOfNodes*lengthOfword + size of dictionary processed
後者の場合は、文字がツリーに直接格納されているので辞書は必要ありません。そのため、2番目の実装のほうがスペース効率が高いように思われます。
私の理解は実装上で正しいですか、そして、一方を他方に選ぶ特別な理由がありますか？また、2番目のケースのスペース所要量をどのように計算できますか？
回答：
回答№1の場合は3トライは元の単語をどこにも格納せず、代わりに暗黙的に格納します。トライの基本構造は次のとおりです。トライストアの各ノード
- ノードに到着するパスがワードを形成するかどうかを決定する単一ビット
- 文字でラベル付けされた子ノードへのポインタのコレクション。
単語がトライに含まれているかどうかを判断するには、あなたはルートから始めて、適切なラベルの付いたポインタを1つずつ順にたどります。単語としてマークされたノードに到着した場合、その単語はトライに存在します。印が付いていないノードにたどり着いたり、トライから外れた場合、その単語は存在しません。
2つの構造の違い上記のリストは子ポインタの格納方法です。最初のバージョンでは、子ポインタはアルファベットのシンボルごとに1つのポインタの配列として格納されています。これにより、後続の子ポインタは非常に高速になりますが、非常にスペース効率が悪くなります。 2番目のバージョンでは、必要なラベル付きポインターだけを保持しているある種のコレクションを明示的に保管します。これは遅くなりますが、まばらな試行にはよりスペース効率が良くなります。
トライのスペース使用量は数によって異なりますノードの数（nと呼びます）、アルファベットのサイズ（kと呼びます）、および子ポインタの表現方法。ポインタの固定サイズの配列を格納する場合、スペースの使用量はkn個のポインタ（それぞれk個のポインタを持つn個のノード）と、各ノードのマーカー用のnビットになります。たとえば、ポインタの動的な配列がソートされた順序で格納されている場合、オーバーヘッドは合計n個の子ポインタにnビットを加え、さらに1つのコレクションを格納するのに必要なスペースのn倍になります。
最初のアプローチの利点は、スピードとシンプルさであり、高密度の試行で非常に優れたパフォーマンスを発揮します。 2番目の方法は、低速ですがスパースな試行にはメモリ効率がよくなります。
これらが唯一のスペース最適化ではありません可能。 Patriciaは1人の子供だけでノードを圧縮しようとしており、とてもスペース効率が良いです。 DAWGはできるだけ多くのノードをマージしようとしますが、効率的な挿入をサポートしません。
お役に立てれば！