c - C の文字ツリー

Question

単純なアスキー文字 (aZ) で構成される単語に関連付けられたデータを保存したいと考えています。目標は、将来の解析で単語に関連付けられたデータを非常に迅速に取得することです。

私は次の構造について考えました：

struct Foo {
  Foo *letter[26];
  void *data;
};

したがって、文字列内の単語を解析しながら「文字ツリー」をたどり、関連するデータを取得することができます。

"foo" => ['f' node] -> ['o' node] -> ['o' node]

問題は単語数が多い場合のツリー全体の大きさです。

パフォーマンスを落とさずにツリーのサイズを小さくする方法はありますか?

Answer 1

あなたが説明しているのは と呼ばれるものですtrie。コンパクトな基数ツリーはよりコンパクトです。

Answer 2

単語をハッシュ テーブルに格納する代わりにツリーを使用している理由はありますか? これらは少し多くのメモリを使用する傾向がありますが、テーブル ルックアップのほぼ一定時間のパフォーマンスが得られます。