次期 marisa-trie のインタフェースに関するメモ

ほとんどの部分を作り直すという暴挙によって仕上がった代物を，近い内に marisa-0.2.0-beta として公開する予定です．

旧版（marisa-0.1.x）と比べると，最大の違いはインタフェースです．原形が残っていないので，旧版を利用するソースコードの流用は無理です．その代わり，とてもシンプルなインタフェースになります．例えば，検索関数の引数を統一したほか，Common prefix search と Predictive search については，検索結果を 1 つずつ返すようにしました．

大体の使い方については，以下のサンプルでほとんど説明できます．

// キー集合を作成します．
marisa::Keyset keyset;
keyset.push_back("a");
keyset.push_back("app");
keyset.push_back("apple");

// キー集合から辞書を構築します．
marisa::Trie trie;
trie.build(keyset);

// 検索（Common prefix search）します．
marisa::Agent agent;
agent.set_query("apple");
while (trie.common_prefix_search(agent)) {
  std::cout.write(agent.key().ptr(), agent.key().length())
      << ": " << agent.key().id() << std::endl;
}

一応，使いそうな部分をまとめて簡単なメモを付けた内容が以下になります．

namespace marisa {

// キーを格納するためのクラスです．
// 辞書を構築するとき，および検索結果を受け取るときに使いますが，
// 前者は Keyset のメンバとして，後者は Agent のメンバとしての利用になります．
class Key {
 public:
  Key();
  Key(const Key &key);

  Key &operator=(const Key &key);

  char operator[](std::size_t i) const;

  const char *ptr() const;
  std::size_t length() const;

  // id と weight は共用体のメンバになっています．
  // 辞書を構築するときは，weight を利用してノードの整列をおこない，
  // id を上書きして返すようになっています（入出力兼用）．
  // 検索結果を受け取るときは id が有効になります．
  std::size_t id() const;
  float weight() const;
};

// キーの集合を格納するためのクラスです．辞書を構築するときに使います．
// 検索結果の保存に使うこともできます．
// push_back() で渡した文字列については，複製を持つようになっています．
class Keyset {
 public:
  Keyset();

  void push_back(const Key &key);
  void push_back(const char *str);
  void push_back(const char *ptr, std::size_t length, float weight = 1.0);

  const Key &operator[](std::size_t i) const;
  Key &operator[](std::size_t i);

  std::size_t num_keys() const;

  bool empty() const;
  std::size_t size() const;
  std::size_t total_length() const;

  // メモリを解放せずに，格納されているキーの情報のみを破棄します．
  // 同じオブジェクトを使い回すことで無駄をなくしたいときに使います．
  void reset();

  void clear();
  void swap(Keyset &rhs);
};

// 検索要求を格納するためのクラスです．
// Agent のメンバとして，検索するときに使います．
class Query {
 public:
  Query();
  Query(const Query &query);

  Query &operator=(const Query &query);

  char operator[](std::size_t i) const;

  const char *ptr() const;
  std::size_t length() const;
  std::size_t key_id() const;
};

// 検索要求，検索結果，作業領域をまとめるためのクラスです．
// 検索するときに使います．
class Agent {
 public:
  Agent();
  ~Agent();

  const Query &query() const;
  const Key &key() const;

  // 検索要求の設定に使います．
  // set_query(str) は '\0' が出現するまでの長さを求めるようになっています．
  void set_query(const char *str);
  void set_query(const char *ptr, std::size_t length);
  void set_query(int key_id);  // 引数に 0 を渡されたときのためだけにあります．
  void set_query(std::size_t key_id);

  void clear();
  void swap(Agent &rhs);
};

class Trie {
 public:
  // 辞書を構築します．
  // config_flags の内容は旧版（0.1.x）とほとんど同じです．
  void build(Keyset &keyset, int config_flags = 0);

  void mmap(const char *filename);
  void map(const void *ptr, std::size_t size);

  void load(const char *filename);
  void read(int fd);

  void save(const char *filename) const;
  void write(int fd) const;

  // 検索のインタフェースはほとんど同じです．
  // 引数は Agent に統一したので，
  // 「引数は何だったっけ？」と悩むことはなくなります．

  // 該当するキーが存在すれば true を返します．
  bool lookup(Agent &agent) const;

  // ID からキーの文字列を復元します．
  // 不正な ID を受け取ると例外を投げます．
  void reverse_lookup(Agent &agent) const;

  // 検索結果を 1 つずつ返すようになっています．
  // false を返すまで呼び出しつづけることにより，
  // すべての検索結果を受け取ることができます．
  // agent.set_query() を呼び出すと途中経過は破棄されます．
  bool common_prefix_search(Agent &agent) const;
  bool predictive_search(Agent &agent) const;

  std::size_t num_tries() const;
  std::size_t num_keys() const;
  std::size_t num_nodes() const;

  TailMode tail_mode() const;
  NodeOrder node_order() const;

  bool empty() const;
  std::size_t size() const;
  std::size_t total_size() const;
  std::size_t io_size() const;

  void clear();
  void swap(Trie &rhs);
};

// std::FILE を用いた入出力関数は marisa/stdio.h にて宣言されています．
// #include <cstdio> を入れたくないときは，#include <marisa.h> の代わりに
// #include <marisa/trie.h> を使ってください．

void fread(std::FILE *file, Trie *trie);
void fwrite(std::FILE *file, const Trie &trie);

// std::iostream を用いた入出力関数は marisa/iostream.h にて宣言されています．
// #include <iostream> を入れたくないときは，#include <marisa.h> の代わりに
// #include <marisa/trie.h> を使ってください．

std::istream &read(std::istream &stream, Trie *trie);
std::ostream &write(std::ostream &stream, const Trie &trie);

std::istream &operator>>(std::istream &stream, Trie &trie);
std::ostream &operator<<(std::ostream &stream, const Trie &trie);

}  // namespace marisa