最近の更新 (Recent Changes)

2010-04-12

Dernières dossier de presse

doar (0.0.13)2010-08-30 00:43

Wikiガイド(Guide)

サイドバー (Side Bar)

Doar (ver 0.0.8)

※ ver 0.0.9以降は、READMEファイルを参照して下さい


概要

Doarは、DoubleArrayの構築・検索を行うためのC++ライブラリです。


現在(2009/11/1)で実装されている機能は以下の通りです。

DoubleArrayの構築・保存
  ・ソート済みのキーセットから、DoubleArrayを構築 ※ 構築時の使用メモリ容量が少ない
  ・任意の順番のキーセットから、DoubleArrayを構築
  ・構築したDoubleArrayをファイルに保存
  ・一度保存したデータを読み込んで、更新(要素追加)、再保存
・上で作成したDoubleArrayデータから、キーを検索する
・各キーを、0から始まるユニークなIDにマッピング (IDは挿入順で割り振られる)
・Rubyバインディング ※ 現在は、データ読込・検索のみ

環境

・現在(2009/11/1)は、sizeof(int)==4、となる環境を前提としています


使い方

・ルートディレクトリでmakeを実行することで、サンプルコマンドがbin以下に作成されます

 ・mkdoar: DoubleArray構築コマンド

 ・doar: 簡易検索コマンド

 ・ckdoar: 構築したDoubleArrayのテスト & ベンチマークコマンド

・具体的な使い方は、src/comman/以下の各ファイルを参照して下さい


簡易API C++

※ まだ開発途中なので、APIは変更される可能性があります。

  1. namespace Doar {
  2. //=== ファイル: src/doar/builder.h ===
  3. class Builder {
  4. // 引数のファイル(ソート済み)から、DoubleArrayを構築する
  5. // [返り値]
  6. // 成功: 0
  7. // 失敗(ファイルオープン): -1
  8. // 失敗(未ソートファイル): -2 ※ キーがユニークでは無い場合もこのエラーを返す
  9. int build(const char* filepath);
  10. // 引数の文字列配列(ソート済み)から、DoubleArrayを構築する
  11. // [返り値]
  12. // 成功: 0
  13. // 失敗(未ソート文字列配列): -2 ※ キーがユニークでは無い場合もこのエラーを返す
  14. void build(const char** strs, unsigned str_count);
  15. // 引数のファイルにDoubleArrayを保存する
  16. bool save(const char* filepath);
  17. // DoubleArrayに格納されているキー数を取得する
  18. unsigned size() const;
  19. };
  20. //=== ファイル: src/doar/node.h ===
  21. struct Node {
  22. // IDを取得する
  23. unsigned id() const;
  24. // ノードが有効化どうか(検索に成功したかどうか)を返す
  25. operator bool() const;
  26. // ノードが葉(終端)かどうかを返す
  27. bool is_leaf() const;
  28. }
  29. //=== ファイル: src/doar/searcher.h ===
  30. class Searcher {
  31. // DoubleArrayを引数のファイルから読み込む
  32. Searcher(cosnt char* filepath);
  33. // (コンストラクタで)無事に読み込めた場合はtrueを返す
  34. operator bool() const;
  35. // コンストラクタ呼び出し後のSearcherの状態
  36. // 0 : 検索可能
  37. // -1: ファイルオープンに失敗
  38. // -2: ファイルフォーマットが不正
  39. // -3: ファイルが壊れている
  40. const int status;
  41. // DoubleArrayに格納されているキー数を取得する
  42. unsigned size() const;
  43. // ルートノードを取得する
  44. Node root_node() const;
  45. // キーに対応するノードを探す
  46. // 検索に失敗した場合は、Node.valid()==falseとなる
  47. Node search(const char* key) const;
  48. // 初期ノード(root_node)を指定して、検索を行う
  49. // root_nodeには、最後に使われた親ノードが格納される ※ 終端ノードで一致した場合は、node.is_leaf()==trueとなる
  50. Node search(const char* key, Node &root_node) const;
  51. // common-prefix検索(走査)を行う
  52. // fnは、void fn(const char* key, unsigned key_offset, unsigned id)形式のファンクタ
  53. // fnは、keyに一致するノードが見つかった場合に、その都度呼び出される
  54. // ※ 現在、fnはconst指定されているので、fnが関数オブジェクトで、かつ可変メンバを使いたい場合は、そのメンバにmutableを指定して下さい
  55. template<typename Callback>
  56. void common_prefix_search(const char* key, const Callback& fn) const;
  57. // common-prefix検索(走査)を行う
  58. // root_nodeを指定することで検索を開始するノードが指定できる
  59. // fnは、void fn(const char* key, unsigned key_offset, unsigned id, Node node)形式のファンクタ
  60. // fnの引数のnodeは、一致したノードの親ノード ※ 終端ノードで一致した場合は、node.is_leaf()==trueとなる
  61. // fnは、keyに一致するノードが見つかった場合に、その都度呼び出される
  62. template<typename Callback>
  63. void common_prefix_search(const char* key, Node root_node, const Callback& fn) const;
  64. // parentの子ノード(のindex)を、走査する
  65. // fnは、 void fn(char arc_char, Node child_node, const char* tail)形式のファンクタ
  66. // child_node.is_leaf()の場合は、tailには遷移文字に続く文字列へのポインタが渡される (それ以外はNULL)
  67. template<typename Callback>
  68. void children(Node parent, const Callback& fn) const;
  69. };
  70. //=== ファイル: src/doar/double_array.h ===
  71. class DoubleArray {
  72. DoubleArray();
  73. // keyをDoubleArrayに追加する
  74. // ※ keyはNULL終端で、途中に値が0xFFの文字を含むことはできない
  75. // 既にキーが挿入されている場合は、falseを返す
  76. bool insert(const char* key);
  77. // Searcherクラスの同メソッドと同様に働く
  78. // ただし、検索系のメソッドは、Searcherクラスのそれの方が最適化されている可能性がある
  79. unsigned size() const;
  80. Node root_node() const;
  81. Node search(const char* key) const;
  82. Node search(const char* key, Node &root_node) const;
  83. template <typename Callback>
  84. void common_prefix_search(const char* key, Callback& fn) const;
  85. template <typename Callback>
  86. void common_prefix_search(const char* key, Node root_node, Callback& fn) const;
  87. template <typename Callback>
  88. void children(Node parent, const Callback& fn) const;
  89. // pathに構築したtrieデータを保存する
  90. bool save(const char* path);
  91. // データを初期化する
  92. void clear();
  93. // pathからtrieデータを読み込む
  94. // 読み込んだ後は、そのデータに対して、さらにinsertを行うことが可能
  95. // ※ ただし、挿入効率は、ゼロから構築したtrieに比べて劣る
  96. //
  97. // [返り値]
  98. // 0 : 成功
  99. // -1: ファイルオープンに失敗
  100. // -2: ファイルフォーマットが不正
  101. // -3: ファイルが壊れている
  102. int load(const char* path);
  103. }
  104. }

インストール + 使用方法: Ruby

※ まだ開発途中なので、メソッド等は変更される可能性があります。

  1. ## インストール方法
  2. # cd $DOAR_ROOT/ruby
  3. # ruby extconf.rb
  4. # make
  5. # sudo make install
  6. require "doar"
  7. trie = Doar::Searcher.new("doar.dat")
  8. trie.size
  9. --> 1000000 # キー数
  10. trie.key?("形態素")
  11. --> true
  12. trie["形態素"]
  13. --> 10 # ID
  14. trie["morpheme"]
  15. --> nil # trie.key?("...")==falseの場合
  16. trie.common_prefix_search("形態素")
  17. --> [[3, 368117], [6, 368161], [9, 368162]] # [一致した文字列の位置,ID]の配列
  18. trie.each_common_prefix("形態素"){|pos,id|
  19. puts "#{id}: #{'形態素'[0,pos]}"
  20. }
  21. 368117:
  22. 368161: 形態
  23. 368162: 形態素
  24. --> nil
  25. trie.each{|key,id| # 格納されている全てのキーをiterate
  26. # ...
  27. }
  28. trie.each("日本"){|key,id| # "日本"で始める全てのキーをiterate
  29. # keyは、先頭に"日本"という文字列を必ず含む
  30. # 第二引数にfalseを渡した場合、共通(第一引数)部分が除去された文字列が渡される
  31. }


TODO

・このページを含めて、ちゃんとしたドキュメントを作成する。

・実例として、Doarを使用した形態素解析器を実装する。(Igoを作ってしまったのでどうしよう?)

・その他 ...