doar Wiki - doar

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は変更される可能性があります。

 namespace Doar {
   //=== ファイル: src/doar/builder.h ===
   class Builder {
     // 引数のファイル(ソート済み)から、DoubleArrayを構築する
     // [返り値]
     // 成功: 0
     // 失敗(ファイルオープン): -1
     // 失敗(未ソートファイル): -2  ※ キーがユニークでは無い場合もこのエラーを返す
     int build(const char* filepath);
 
     // 引数の文字列配列(ソート済み)から、DoubleArrayを構築する
     // [返り値]
     // 成功: 0
     // 失敗(未ソート文字列配列): -2  ※ キーがユニークでは無い場合もこのエラーを返す
     void build(const char** strs, unsigned str_count);
     
     // 引数のファイルにDoubleArrayを保存する
     bool save(const char* filepath);   
 
     // DoubleArrayに格納されているキー数を取得する
     unsigned size() const;
   };
 
   //=== ファイル: src/doar/node.h ===
   struct Node {
     // IDを取得する
     unsigned id() const;
 
     // ノードが有効化どうか(検索に成功したかどうか)を返す
     operator bool() const;
 
     // ノードが葉(終端)かどうかを返す
     bool is_leaf() const;
   }
 
   //=== ファイル: src/doar/searcher.h ===
   class Searcher {
     // DoubleArrayを引数のファイルから読み込む
     Searcher(cosnt char* filepath);
 
     // (コンストラクタで)無事に読み込めた場合はtrueを返す
     operator bool() const;
 
     // コンストラクタ呼び出し後のSearcherの状態
     // 0 : 検索可能
     // -1: ファイルオープンに失敗
     // -2: ファイルフォーマットが不正
     // -3: ファイルが壊れている
     const int status;
 
     // DoubleArrayに格納されているキー数を取得する
     unsigned size() const;
 
     // ルートノードを取得する
     Node root_node() const;
 
     // キーに対応するノードを探す
     // 検索に失敗した場合は、Node.valid()==falseとなる
     Node search(const char* key) const;
 
     // 初期ノード(root_node)を指定して、検索を行う
     // root_nodeには、最後に使われた親ノードが格納される ※ 終端ノードで一致した場合は、node.is_leaf()==trueとなる
     Node search(const char* key, Node &root_node) const;
 
     // common-prefix検索(走査)を行う
     // fnは、void fn(const char* key, unsigned key_offset, unsigned id)形式のファンクタ
     // fnは、keyに一致するノードが見つかった場合に、その都度呼び出される
     //  ※ 現在、fnはconst指定されているので、fnが関数オブジェクトで、かつ可変メンバを使いたい場合は、そのメンバにmutableを指定して下さい
     template<typename Callback>
     void common_prefix_search(const char* key, const Callback& fn) const;
 
     // common-prefix検索(走査)を行う
     // root_nodeを指定することで検索を開始するノードが指定できる
     // fnは、void fn(const char* key, unsigned key_offset, unsigned id, Node node)形式のファンクタ
     //   fnの引数のnodeは、一致したノードの親ノード  ※ 終端ノードで一致した場合は、node.is_leaf()==trueとなる
     // fnは、keyに一致するノードが見つかった場合に、その都度呼び出される
     template<typename Callback>
     void common_prefix_search(const char* key, Node root_node, const Callback& fn) const;
     
     // parentの子ノード(のindex)を、走査する
     // fnは、 void fn(char arc_char, Node child_node, const char* tail)形式のファンクタ
     //  child_node.is_leaf()の場合は、tailには遷移文字に続く文字列へのポインタが渡される (それ以外はNULL)
     template<typename Callback>
     void children(Node parent, const Callback& fn) const;
   };
 
 
   //=== ファイル: src/doar/double_array.h ===
   class DoubleArray {
     DoubleArray();
 
     // keyをDoubleArrayに追加する
     //  ※ keyはNULL終端で、途中に値が0xFFの文字を含むことはできない
     // 既にキーが挿入されている場合は、falseを返す
     bool insert(const char* key); 
 
 
     // Searcherクラスの同メソッドと同様に働く
     // ただし、検索系のメソッドは、Searcherクラスのそれの方が最適化されている可能性がある
     unsigned size() const;
     Node root_node() const;
     Node search(const char* key) const;
     Node search(const char* key, Node &root_node) const;
     template <typename Callback>
     void common_prefix_search(const char* key, Callback& fn) const;
     template <typename Callback>
     void common_prefix_search(const char* key, Node root_node, Callback& fn) const;
     template <typename Callback>
     void children(Node parent, const Callback& fn) const;
 
 
     // pathに構築したtrieデータを保存する
     bool save(const char* path);
     
     // データを初期化する
     void clear();
 
    // pathからtrieデータを読み込む
     // 読み込んだ後は、そのデータに対して、さらにinsertを行うことが可能
     //   ※ ただし、挿入効率は、ゼロから構築したtrieに比べて劣る
     //
     // [返り値]
     // 0 : 成功
     // -1: ファイルオープンに失敗
     // -2: ファイルフォーマットが不正
     // -3: ファイルが壊れている
     int load(const char* path);
   } 
 }

---

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

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

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

---

TODO

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

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

・その他 ...