2

試行錯誤について読めば読むほど、何らかの理由で混乱します。
今私を混乱させているのは次のことです:
私は 2 種類の実装について読んだことがあります。

  1. 配列を使用して文字を表し (文字自体を格納するのではなく)、各ノードに実際の単語へのインデックスも格納します (単語に到達した場合)。
  2. 文字を格納するノードの を使用Collectionし、各ノードの最後でブール値を使用して、このパスをたどる単語に到達したかどうかを判断します

最初のケースでは言及されていませんが、実際にはすべての辞書の単語を保持する必要があるようです (間接的に参照しているため)。だから私たちは持っていますarray_size*numberOfNodes*lengthOfword + size of dictionary processed

後者の場合、文字はツリーに直接格納されるため、辞書は必要ありません。したがって、2 番目の実装の方がスペース効率が良いように思えます。しかし、どのくらいかはわかりません。
実装に関する私の理解は正しいですか? また、どちらかを選択する特定の理由はありますか? また、2 番目のケースのスペース要件をどのように計算できますか?

4

1 に答える 1

3

試行は元の単語をどこにも保存せず、代わりに暗黙的に保存します。トライの基本構造は次のとおりです: トライストア内の各ノード

  • ノードに到達するパスがワードを形成するかどうかを決定する単一のビット、および
  • 文字でラベル付けされた子ノードへのポインターのコレクション。

単語がトライに含まれているかどうかを判断するには、ルートから始めて、適切にラベル付けされたポインターを 1 つずつたどります。単語としてマークされたノードに到達した場合、その単語はトライに存在します。マークされていないノードに到達するか、トライから外れると、その単語は存在しません。

上記の 2 つの構造体の違いは、子ポインターの格納方法です。最初のバージョンでは、子ポインターはアルファベットのシンボルごとに 1 つのポインターの配列として格納されます。2 番目のバージョンでは、必要なラベル付きポインターだけを保持するある種のコレクションを明示的に格納します。これは遅くなりますが、まばらな試行ではスペース効率が高くなります。

トライのスペース使用量は、ノードの数 (n と呼ぶ)、アルファベットのサイズ (k と呼ぶ)、および子ポインターの表現方法によって異なります。ポインターの固定サイズの配列を格納する場合、スペースの使用量は、約 kn 個のポインター (それぞれ k 個のポインターを持つ n ノード) に、各ノードのマーカー用に n ビットを加えたものになります。たとえば、ポインタの動的配列がソートされた順序で格納されている場合、オーバーヘッドは、合計 n 個の子ポインタに n ビットを加え、さらに単一のコレクションを格納するために必要な容量の n 倍になります。

最初のアプローチの利点は、スピードとシンプルさであり、高密度の試行で非常に優れたパフォーマンスを発揮します。2 番目の方法は低速ですが、スパース試行ではメモリ効率が高くなります。

可能なスペースの最適化はこれだけではありません。Patricia は、ノードを 1 つの子だけでまとめて圧縮しようと試みており、スペース効率が非常に優れています。DAWG は、できるだけ多くのノードを一緒にマージしようとしますが、効率的な挿入をサポートしていません。

お役に立てれば！

于 2013-01-21T19:10:03.847 に答える