スペース効率的なトライ

Question

私はこれが私の構造体である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]; 
}; 

、それのインデックスは、文字のunsigned char型キャストです。たとえば、「c」を追加する場合は、

children[(unsigned char)'c'] 

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

struct node** children; 

と、ノードのためだけのmallocスペース、ノードを追加し、新しいノードに

children[(unsigned char)'c'] 

ポイントを持っています。問題は、子供のための空間をmallocしないと、明らかにインデックスを参照できないか、それは大きな誤りです。

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

Answer 1

を使用すると、ノードごとに子ポインタが1つしかなく、すべてのノードにも「兄弟」へのポインタがあるため、すべての兄弟が効果的に直接ポインティングされるのではなくリンクリストとして格納されます親によって

Answer 2

あなたは本当にそれを両方の方法で持たせることはできませんし、スペース効率が良く、子ノードでO（1）ルックアップを持つことはできません。

にはあなたしか実際に追加されますエントリのためのスペースを割り当てない場合、およびNOT NULLポインタを、あなたは、もはやあなたは配列に直接もはやインデックスを得るよう

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つのレベルの非空のエントリの多くで終了した場合、あなたは可能性がありますになるために持っているどのように多くのエントリの追加の回数を保存します子をソート順に挿入し、バイナリ検索を行います。または、配列の代わりにリンクリストとして子を追加することもできます。

Answer 3

英語のキーワード検索をしたいのであれば、子供のサイズを256から26に最小限に抑えることができると思います。26文字のアルファベットをカバーできます。

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

私はまだライブラリを通過していませんが、私はtrie implementationが役立つと思います。

Answer 4

すべてのノードの子ノードをノードのハッシュテーブルにすることで、空間効率がよく、一定の検索時間を保つことができます。特にUnicode文字が含まれていて、辞書に含めることができる文字セットが52 +いくつかに制限されていない場合、これはよりきめ細かな要件になります。このようにして、トライを使用する利点を維持し、同時に時間と空間を効率的にすることができます。

あなたが使用している文字セットが無制限に近づいている場合は、ノードのリンクリストがうまくいく可能性があります。管理不能な悪夢が好きなら、最初のいくつかのレベルでハッシュテーブルに子供を残し、下位レベルにはリンクされたリストがあるハイブリッドアプローチを選択できます。真のバグファームでは、リンクされた各リストがしきい値を超えるたびにハッシュテーブルに変換します。あなたは簡単にコストを償却することができます。

可能性は無限です！