Doar (ver 0.0.8)

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

概要

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

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

環境

・現在(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を作ってしまったのでどうしよう?)

・その他 ...