doar

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

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

 ・Rubyバインディング  ※ 現在は、データ読込・検索のみ


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

[移植性に関する注意]
　・std::vector.data()
　・mmap_t	
　・バイトエンディアン

[コンパイル・動作確認]
・WindowsXP
　・VisualC++ 2005/2008
・unix系(g++ 4.x.x)  ※ 以下は、SourceForge.jpのコンパイラフォーム(http://sourceforge.jp/docs/コンパイルファームFAQ)での検証環境
　・x86	Linux Kernel 2.6（Debian GNU/Linux 4.0 etch)
　・x86	NetBSD 4.0
　・PowerPC G5	MacOS X 10.5
　・AMD64	Linux Kernel 2.6（Debian GNU/Linux 4.0 etch)

[使い方]
・ルートディレクトリでmakeを実行することで、サンプルコマンドがbin以下に作成されます 
　・mkdoar: DoubleArray構築コマンド 
　・doar:   簡易検索コマンド (通常検索, common-prefix検索)
　・ckdoar: 構築したDoubleArrayのテスト & ベンチマークコマンド
　・merge-douar: DoubleArrayマージコマンド
・具体的な使い方は、src/comman/以下のファイルを参照してください


[簡易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;

    // common-prefix検索(走査)を行う
    // fnは、void fn(const char* key, unsigned key_offset, unsigned id)形式のファンクタ
    // fnは、keyに一致するノードが見つかった場合に、その都度呼び出される
    //  ※ 現在、fnはconst指定されているので、fnが関数オブジェクトで、かつ可変メンバを使いたい場合は、そのメンバにmutableを指定して下さい
    template<typename Callback>
    void each_common_prefix(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 each_common_prefix(const char* key, Node root_node, const Callback& fn) const;

    // common-prefix検索(走査)を行う
    // inは、ストリーム形式の検索キー。以下のメソッドを備えている必要がある。
    //   - read: 呼び出されるごとに、一つのDoar::Codeを返す。ストリームの終端に達した場合は、Doar::TERMINAL_CODEを返す。
    //     ※  charからDoar::Codeへの変換には、Doar::char2codeを用いる
    // fnは、void fn(CustomKeyStream in, unsigned id)形式のファンクタ
    //  - read(): read one code from stream. If end of stream reached, must return TERMINAL_CODE.
    //  - including(const char* tail): a predicate method. If tail is included in the rest of this stream, return true.
    template<typename CustomKeyStream, typename Callback>
    void each_common_prefix(CustomKeyStream& in, 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);
  }  

  //=== ファイル: src/doar/merger.h ===
  class Merger {
    // path1とpath2のDoubleArrayインデックスをマージする
    // 返り値は、DoubleArray::loadメソッドのそれと同様
    // ※ 二つのDoubleArrayには、重複したキーが存在しないことが望ましい
    // 　重複キーが存在する場合、path2の方の該当キーが無視される(ただし、そのためのID値およびスペースは消費されるので無駄)
    //   なお、path2の方の全てのIDには、path1の最大IDが加算される
    int merge(const char* path1, const char* path2);

    // filepathに構築したtrieデータを保存する
    // do_shrink_tailがtrueの場合は、TAIL配列の圧縮を行ってから保存される
    bool save(const char* filepath, bool do_shrink_tail=true);
  }
}


[Ruby 簡易API & 使用例]
## インストール方法
# 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("形態素")
--> [[368117, 3], [368161, 6], [368162, 9]]  # [ID, 一致した文字列の位置]の配列

trie.each_common_prefix("形態素"){|id,pos|
  puts "#{id}: #{'形態素'[0,pos]}"
}
368117: 形
368161: 形態
368162: 形態素
--> nil

trie.each{|id, key|  # 格納されている全てのキーをiterate
  # ...
}

trie.each("日本"){|id, key| # "日本"で始める全てのキーをiterate
  # keyは、先頭に"日本"という文字列を必ず含む
  # 第二引数にfalseを渡した場合、共通(第一引数)部分が除去された文字列が渡される
}

[TODO]
・ポータビリティ向上
・削除機能 (検討)                           => おそらく実装しない(2010/03/01)
・キーに対応する任意の4byte値を格納可能にする  => おそらく実装しない(2010/03/01)

[メモ]
・Searcher::search(key, root)のAPIには欠陥(?)がある
　・元々、rootの意図は、keyを包含する文字列がtrieの中にある場合に、その一致部分までの情報を保持して、別のkeyでその部分から検索を行えるようにすることにある。
　・ただし、現在はkeyのユニークな末尾部分はまとめてtail配列に格納してしまっているので、その部分の一致情報を取り出すことはできない。
　・そのため、keyを包含する文字列がtrieにあったとしても、その部分までも一致情報がrootに格納されるかどうかは、その時のtrie内のキーセットに依存することになり、実際上は使えなくなるのではないかと思う。