文字列をキーに検索を行なうためのデータ構造として、 Double Arrayが代表的で、有名な実装としては次のものがあります。 Darts http://www.chasen.org/~taku/software/darts/ Datrie http://linux.thai.net/~thep/datrie/datrie.html
他に、最近、Level-Order Unary Tree(LOUD)という構造を使った Tx http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/tx-j.htm というライブラリが公開されています。 これらを使うのも面白くて良いのですが、頭を使わなくても 理解できる仕組みが欲しいこともあるかと思うので、anthyの 個人辞書アクセスで使っているやり方を切り抜いて添付します。 #gang lookupと呼んでいるので、gxという名前にしています。 各行が「キー文字列 検索対象」という形式でソートされたファイルを 入力として次のようなコードで検索することができ、call back関数が 呼び出されます。 // コード struct gx *g = gx_new(); gx_add_item(g, "a", NULL); gx_add_item(g, "hello", NULL); gx_add_item(g, "\xff", NULL); gx_add_item(g, "abc", NULL); gx_scan(g, find_cb, "input");// call backとファイル名を指定 gx_free(g); // call backの例 int find_cb(struct gx *g, int ln, const char *key, const char *line, void *ptr) { printf("line=(%d) key=(%s) found\n", ln, key); return 0; } 当然ながら色々と改善の余地があるので、使う時は検討してください。 -- -- CHAOS AND CHANCE! Yusuke TABATA
gx.c.gz
Description: GNU Zip compressed data
_______________________________________________ Anthy-dev mailing list Anthy-dev@lists.sourceforge.jp http://lists.sourceforge.jp/mailman/listinfo/anthy-dev
