MARISA: Matching Algorithm with Recursively Implemented StorAge

概要

Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie に対するコンパクトなデータ構造であり，動的な更新には対応していないものの，高い空間効率とそれなりの時間効率を実現できます．また，Trie の特徴を引き継いでいるため，MARISA による辞書は，単純な辞書引きだけでなく，逆引き，Common Prefix Search や Predictive Search を効率良く実現できます．

ほとんどの場合，MARISA による辞書は，登録文字列の集合を連結してできるテキストと比べて，ずっとコンパクトになります．そのため，登録文字列をそのまま保持する標準的な二分探索木やハッシュ表と比べると，ずーっとコンパクトです．一方で，確率的なデータ構造である Bloom Filter と比べてみると，空間効率の面では劣りますが，False Positive がなく，逆引きに加えて Common Prefix Search や Predictive Search を効率良く実現できることが特徴になります．

libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます．

できること

libmarisa による辞書の構築では，登録文字列に 0 から順に固有の ID を割り当てるようになっています．ID は自動的に割り当てられるので，登録文字列に任意の ID を割り当てることはできません．検索においては，文字列あるいは ID をクエリとして受け取り，適合する登録文字列と ID の組を検索結果として返すようになっています．

• 辞書引き（Lookup）
  • 入力文字列が登録されているかどうかを確認します．
• 逆引き（Reverse Lookup）
  • 入力された ID から登録文字列を復元します．
• Common Prefix Search
  • 入力文字列の前半部分に一致する登録文字列を検索します．
• Predictive Search
  • 入力文字列で始まる登録文字列を検索します．

ライセンス

libmarisa および付属のコマンドラインツールはフリーソフトウェアです．使用・再配布については，二条項 BSD ライセンスと LGPL のデュアルライセンスを採用しています．

ダウンロード

プロジェクトの管理やソースコードの配布には GitHub を利用しています．

• プロジェクト
  • https://github.com/s-yata/marisa-trie
• ソースコード
  • marisa-0.2.6.tar.gz

GCC & Clang

$ tar zxf marisa-0.2.6.tar.gz
$ cd marisa-0.2.6
$ ./configure
$ make
$ make check
$ make install

configure と make によりインストールできるようになっています．make install については，必要に応じて sudo を付けてご利用ください．また，特に指定がなければ libmarisa は共有ライブラリとしてインストールされるので，ldconfig が必要になるかもしれません．

POPCNT 命令が使える環境では，configure に --enable-popcnt を渡すことで，少し高速化することができます．同様に，--enable-sse2, --enable-sse3, --enable-ssse3, --enable-sse4.1, --enable-sse4.2, --enable-sse4, --enable-sse4a, --enable-bmi, --enable-bmi2 というオプションがあります．--enable-native-code を渡せば，コンパイル環境で使える命令がすべて有効になります．また，スタティックライブラリが必要なときは，configure に --enable-static を渡すようにしてください．その他，configure のオプションについては ./configure --help をご覧ください．

Visual C++ 2008

Visual C++ 2008 にて作成したファイルを vs2008/ 以下に配置しています．Visual C++ 2008 以降であれば，vs2008/vs2008.sln を開くだけでスタティックライブラリ libmarisa.lib とコマンドラインツールをビルドできます．

Visual C++ 2008 より古い環境では，新しくプロジェクトを作る必要があります．プロジェクトを作成すれば問題なくビルドできると思いますが，試していないので断言はできません．

Perl バインディング

$ cd bindings/perl
$ perl Makefile.PL
$ make
$ make install

SWIG による Perl バインディングが bindings/perl/ にあります．perl Makefile.PL により Makefile を作成し，make install を実行することでインストールできます．使い方については，bindings/perl/sample.pl を参考にしてください．

Python バインディング

$ cd bindings/python
$ python setup.py build
$ python setup.py install

SWIG による Python バインディングが bindings/python/ にあります．python setup.py install により インストールできます．使い方については，bindings/python/sample.py を参考にしてください．

Ruby バインディング

$ cd bindings/ruby
$ ruby extconf.rb
$ make
$ make install

SWIG による Ruby バインディングが bindings/ruby/ にあります．ruby extconf.rb により Makefile を作成し，make install を実行することでインストールできます．使い方については，bindings/ruby/sample.rb を参考にしてください．

その他

上記のバインディング以外にも，いくつかのバインディングがあります．

• Python
  • "https://github.com/kmike/marisa-trie/高速・高機能な Python バインディング
• Node.js
  • https://github.com/komiya-atsushi/node-marisa-trieNode.js から使うためのモジュール

marisa-build

$ marisa-build < keyset.txt > keyset.dic
#keys: 1342099
#nodes: 1832373
size: 7841664

marisa-build は辞書を構築するツールです．改行を区切りとして文字列を受け取り，構築した辞書を標準出力に書き出すようになっています．

構築する辞書のパラメータについては，オプションを使って指定できます．オプションの一覧は marisa-build -h により確認できます．

入力は改行区切りとなっていますが，水平タブが存在する行については，最後の水平タブ以降を文字列の重みとして扱うようになっています．文字列の出現頻度や出現確率を与えることにより，検索時間を短縮できる可能性があります．

marisa-lookup

$ marisa-lookup keyset.dic
東方
174385	東方
とうほう
-1	とうほう

marisa-lookup は単純な辞書引きをおこなうツールです．入力された文字列が登録されていれば ID とともに出力し，登録されていなければ -1 とともに出力します．

オプションの一覧は marisa-lookup -h により確認できます．

marisa-reverse-lookup

$ marisa-reverse-lookup keyset.dic
800000
800000	紀元前475年

marisa-reverse-lookup は辞書に登録されている文字列を ID から復元するツールです．登録文字列には 0 から順に固有の ID が割り当てられるので，指定できる値は 0 以上で登録文字列数より小さい整数となります．範囲外の値を入力するとエラーになるので注意してください．

オプションの一覧は marisa-reverse-lookup -h により確認できます．

marisa-common-prefix-search

$ marisa-common-prefix-search keyset.dic
東方
2 found
3542	東	東方
174385	東方	東方

marisa-common-prefix-search は Common Prefix Search をおこなうツールです．入力された文字列の前半部分に一致する登録文字列を ID とともに出力します．

オプションの一覧は marisa-common-prefix-search -h により確認できます．

marisa-predictive-search

$ marisa-predictive-search keyset.dic -n 2
東方
200 found
174385	東方	東方
639679	東方文花帖	東方

marisa-predictive-search は Predictive Search をおこなうツールです．入力された文字列で始まる登録文字列を ID とともに出力します．

オプションの一覧は marisa-predictive-search -h により確認できます．

marisa-benchmark

$ marisa-benchmark keyset.txt
Number of tries: 1 - 5
TAIL mode: Text mode
Node order: Descending weight order
Cache level: Normal cache
Number of keys: 1342099
Total length: 28308027
------+----------+--------+--------+--------+--------+--------
#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]
------+----------+--------+--------+--------+--------+--------
     1   11588904   506.45  1187.70  1109.17  1040.39   596.49
     2    8467920   424.71   699.01   677.83   636.07   300.25
     3    7841664   405.47   615.64   601.84   563.91   254.67
     4    7633584   399.43   593.85   583.52   545.57   242.69
     5    7548584   395.90   526.31   563.91   504.55   236.70
------+----------+--------+--------+--------+--------+--------

marisa-benchmark は，marisa-build と同様の入力を受け取り，辞書のサイズや構築・検索にかかる時間を調べるツールです．辞書を構成する Trie の数を選択するのに有用です．

検索時間については，入力された文字列を一通り検索するのに要した時間を std::clock() で計測した結果を出力します．文字列を整列してから入力とした場合はキャッシュが効きやすい状況での検索時間になり，文字列をランダムに並べ替えてから入力とした場合はキャッシュが効きにくい状況での検索時間になります．

オプションの一覧は marisa-benchmark -h により確認できます．

marisa-dump

$ marisa-dump keyset.dic | head -3
input: keyset.dic
フ
ファ
ファン

marisa-dump は辞書に登録されている文字列をすべて出力するツールです．デフォルトの区切り文字は改行（LF）ですが，オプションにより変更することができます．

オプションの一覧は marisa-dump -h により確認できます．

使い方

// sample.cc
#include <iostream>
#include <marisa.h>

int main() {
  marisa::Keyset keyset;
  keyset.push_back("a");
  keyset.push_back("app");
  keyset.push_back("apple");

  marisa::Trie trie;
  trie.build(keyset);

  marisa::Agent agent;
  agent.set_query("apple");
  while (trie.common_prefix_search(agent)) {
    std::cout.write(agent.key().ptr(), agent.key().length());
    std::cout << ": " << agent.key().id() << std::endl;
  }
  return 0;
}

$ g++ sample.cc -lmarisa
$ ./a.out
a: 0
app: 1
apple: 2

libmarisa のヘッダは marisa.h です．名前空間には marisa を使っています．危険なので，using namespace marisa とするのは避けてください．最後に，gcc や clang によるリンクでは -lmarisa が必要となることに注意してください．

libmarisa の主要なクラスは Keyset, Agent, Trie の 3 つです．サンプルコードでは明示的に使っていませんが，例外のクラスとして Exception があるほか，Keyset, Agent のメンバとして Key や Query が存在します．

• Keyset: 文字列の集合を格納するクラスです．辞書を構築するときの入力として使うほか，検索結果の保存にも利用できます．
• Agent: 検索の入出力と途中経過を格納するクラスです．検索用の関数はすべて Agent への参照を引数とします．
• Trie: 辞書のクラスです．

コマンドラインツールのソースコードが tools/ にあり，例外処理やファイル入出力，Predictive Search などのサンプルとして利用できます．

定数

typedef enum marisa_error_code_ {
  MARISA_OK           = 0,
  MARISA_STATE_ERROR  = 1,
  MARISA_NULL_ERROR   = 2,
  MARISA_BOUND_ERROR  = 3,
  MARISA_RANGE_ERROR  = 4,
  MARISA_CODE_ERROR   = 5,
  MARISA_RESET_ERROR  = 6,
  MARISA_SIZE_ERROR   = 7,
  MARISA_MEMORY_ERROR = 8,
  MARISA_IO_ERROR     = 9,
  MARISA_FORMAT_ERROR = 10,
} marisa_error_code;

typedef enum marisa_num_tries_ {
  MARISA_MIN_NUM_TRIES     = 0x00001,
  MARISA_MAX_NUM_TRIES     = 0x0007F,
  MARISA_DEFAULT_NUM_TRIES = 0x00003,
} marisa_num_tries;

typedef enum marisa_cache_level_ {
  MARISA_HUGE_CACHE    = 0x00080,
  MARISA_LARGE_CACHE   = 0x00100,
  MARISA_NORMAL_CACHE  = 0x00200,
  MARISA_SMALL_CACHE   = 0x00400,
  MARISA_TINY_CACHE    = 0x00800,
  MARISA_DEFAULT_CACHE = MARISA_NORMAL_CACHE
} marisa_cache_level;

typedef enum marisa_tail_mode_ {
  MARISA_TEXT_TAIL    = 0x01000,
  MARISA_BINARY_TAIL  = 0x02000,
  MARISA_DEFAULT_TAIL = MARISA_TEXT_TAIL,
} marisa_tail_mode;

typedef enum marisa_node_order_ {
  MARISA_LABEL_ORDER   = 0x10000,
  MARISA_WEIGHT_ORDER  = 0x20000,
  MARISA_DEFAULT_ORDER = MARISA_WEIGHT_ORDER,
} marisa_node_order;

namespace marisa {
  typedef ::marisa_error_code ErrorCode;
  typedef ::marisa_cache_level CacheLevel;
  typedef ::marisa_tail_mode TailMode;
  typedef ::marisa_node_order NodeOrder;
}  // namespace marisa

class Exception

class Exception {
 public:
  const char *filename() const;
  int line() const;
  ErrorCode error_code() const;
  const char *error_message() const;

  const char *what() const;
};

Exception は libmarisa が例外として送出するクラスです．エラーが検出されたファイルの名前（__FILE__）と行番号（__LINE__），さらにエラーコードを取り出せるようになっています．what() は使いやすさのために用意した関数であり，error_message() と同じく，__FILE__:__LINE__: error_code: error_message という書式の文字列を返します．

class Key

class Key {
 public:
  char operator[](std::size_t i) const;
  std::string_view str() const;  // C++17
  const char *ptr() const;
  std::size_t length() const;
  std::size_t id() const;
};

Key は後述する Keyset および Agent のメンバになっているクラスです．登録しようとしている文字列や，検索で見つけた登録文字列の情報を格納するために使われています．基本的な使い方では，既に情報が格納されたインスタンスのみを目にすることになります．

class Query

class Query {
 public:
  char operator[](std::size_t i) const;
  std::string_view str() const;  // C++17
  const char *ptr() const;
  std::size_t length() const;
  std::size_t id() const;
};

Query は後述する Agent のメンバになっているクラスです．検索しようとしている文字列や参照したい登録文字列の ID を格納するようになっています．Query に対する文字列や ID の設定は Agent を介しておこなうため，基本的な使い方では，意識する必要はありません．内容を確認したいときに参照する程度です．

class Keyset

class Keyset {
 public:
  Keyset();

  void push_back(const Key &key);
  void push_back(const Key &key, char end_marker);

  void push_back(std::string_view str,
                 float weight = 1.0);  // C++17
  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();

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

  void reset();

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

class Agent

class Agent {
 public:
  Agent();

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

  void set_query(std::string_view str);  // C++17
  void set_query(const char *str);
  void set_query(const char *ptr,
                 std::size_t length);
  void set_query(std::size_t key_id);
};

Agent は Query と Key をメンバとして持つクラスです．検索における入出力の受け渡し，および途中経過の保存に使います．後述する Trie の検索関数は，例外なく Agent への参照を引数として受け取るようになっています．

検索の手順は，set_query() を使って検索したい文字列もしくは参照したい登録文字列の ID を設定し，Trie の関数に渡した後，key() により検索結果を取り出すという流れになります．

class Trie

class Trie {
 public:
  Trie();

  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;

  bool lookup(Agent &agent) const;
  void reverse_lookup(Agent &agent) const;
  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 io_size() const;

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

stdio

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

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

iostream

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);

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