edit= Doar (ver 0.0.8) =
'''概要'''
Doarは、DoubleArrayの構築・検索を行うためのC++ライブラリです。
[[BR]]
現在(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は変更される可能性があります。'''
{{{ code cpp
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'''
'''※ まだ開発途中なので、メソッド等は変更される可能性があります。'''
{{{ code 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'''
・(このページを含めて)ドキュメント作成