3

私はCでスペース効率の良いトライを実装しようとしています。これは私の構造です：

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

ノードを追加すると、そのインデックスは文字のunsignedcharキャストになります。たとえば、「c」を追加したい場合は、

children[(unsigned char)'c']

新しく追加されたノードへのポインタです。ただし、この実装では、256要素のnode*配列を宣言する必要があります。私がやりたいことは：

struct node** children;

次に、ノードを追加するときは、ノードのスペースをmallocするだけで、

children[(unsigned char)'c']

新しいノードをポイントします。問題は、最初に子供用のスペースをmallocしないと、明らかにインデックスを参照できないか、それ以外の場合は大きなエラーになるということです。

だから私の質問は：それがその子への非nullポインタだけを格納するようにトライを実装するにはどうすればよいですか？

4

4 に答える 4

5

各ノードに子ポインターが 1 つしかなく、すべてのノードにも「兄弟」へのポインターがあるde la Briandais trieを使用してみてください。これにより、すべての兄弟が直接ポイントされるのではなく、リンクされたリストとして効果的に格納されます。親によって。

于 2011-06-22T15:21:56.163 に答える
2

実際には、両方の方法を使用して、スペース効率を高め、子ノードで O(1) ルックアップを行うことはできません。

ヌルポインタではなく、実際に追加されたエントリにのみスペースを割り当てると、できなくなります

children[(unsigned char)'c']

配列に直接インデックスを付けることができなくなったためです。

1 つの代替方法は、単純に子を線形検索することです。children配列に含まれるエントリ数の追加カウントを保存します。

children[(unsigned char)'c'] = ...;

ならないといけない

for(i = 0; i < len; i++) {
  if(children[i] == 'c')
     break;
} 
if(i == len) {
  //...reallocate and add space for one item in children
}
children[i] = ...;

ツリーの 1 つのレベルに空でないエントリが多数ある場合は、子を並べ替えた順序で挿入し、バイナリ検索を実行できます。または、子を配列ではなく連結リストとして追加することもできます。

于 2011-06-22T15:25:22.403 に答える
1

すべてのノードの子ノードをノードのハッシュテーブルにすることで、スペース効率を高め、ルックアップ時間を一定に保つことができます。特にUnicode文字が含まれていて、辞書に含めることができる文字のセットが52以上に制限されていない場合、これは優れたものというよりも要件になります。このようにして、トライを使用する利点を維持し、同時に時間とスペースの効率を高めることができます。

また、使用している文字セットが無制限に近づいている場合は、ノードのリンクリストが適切に機能する可能性があることも付け加えておきます。管理不能な悪夢が好きな場合は、最初の数レベルで子をハッシュテーブルに保持し、下位レベルでそれらのリンクリストを保持するハイブリッドアプローチを選択できます。真のバグファームの場合は、リンクされた各リストがしきい値を超えると、その場でハッシュテーブルに変換する動的なものを選択します。費用は簡単に償却できます。

可能性は無限大です！

于 2013-01-15T22:58:58.617 に答える
1

英語のキーワード検索だけを行いたい場合は、子供のサイズを 256 からちょうど 26 に最小化できると思います。26 文字の az をカバーするのに十分です。

さらに、リンクされたリストを使用して子の数をさらに少なくして、より効率的な反復を行うことができます。

私はまだライブラリを調べていませんが、試してみると役立つと思います。

于 2012-05-28T11:56:39.367 に答える