Succinct なトライの実験に用いたソースコード

いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…．

ドキュメントは準備中ですが，基本的な使い方は後述します．

右のメニューにある Featured downloads からアーカイブをダウンロードして，よくある手順を踏めば動作確認できます．

./configure
make
make check

ヘッダのみで構成されているため，make install でインストールしなくても，ヘッダを格納しているディレクトリ（include/）をコピーすれば使えます．

トライを構築する手順は，以下のようになっています．

  1. 基礎となるトライの構築
    • ヘッダ：sumire/trie-builder.h
    • クラス：sumire::TrieBuilder
    • 手順：sumire::TrieBuilder のメソッド insert() によりキーを一つずつ昇順に追加していき，最後に finish() を呼び出す．
  2. 各種トライへの変換
    • ヘッダ：sumire/xxx-trie.h（xxx の部分で実装を切り替え）
    • クラス：sumire::XxxTrie
      • Succinct なトライについては，sumire::XxxTrie （引数を省略すると sumire::BasicSuccinctBitVector を利用）
    • 手順：sumire::TrieBuilder の virtual_trie() が返す一時的なトライを，各種トライの build() に渡すことにより，各種トライを構築できる．
// ビルドするとき，マクロ NDEBUG を与えることにより，assert() を無効にできる．

// ヘッダと各種トライの組み合わせは以下のとおりである．
//
// sumire/basic-trie.h: sumire::BasicTrie
// sumire/ternary-trie.h: sumire::TernaryTrie
// sumire/da-trie.h: sumire::DaTrie
// sumire/succinct-trie.h: sumire::SuccinctTrie
// sumire/louds-trie.h: sumire::LoudsTrie
// sumire/louds-plus-trie.h: sumire::LoudsPlusTrie
//
// トライのインタフェースは，sumire/trie-base.h で定義されている．

#include <sumire/trie-builder.h>
#include <sumire/basic-trie.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
  // 標準入力からキーのリスト（改行区切り）を読み込む．
  std::vector<std::string> keys;
  std::string line;
  while (std::getline(std::cin, line))
  {
    if (!line.empty())
      keys.push_back(line);
  }

  // キーのリストを整列し，重複しているものを取り除く．
  std::sort(keys.begin(), keys.end());
  keys.erase(std::unique(keys.begin(), keys.end()), keys.end());

  // TrieBuilder に対して，キーを昇順に登録する．
  sumire::TrieBuilder trie_builder;
  for (std::size_t key_id = 0; key_id < keys.size(); ++key_id)
  {
    // 第一引数がキー，第二引数が関連付ける値になる．
    // ただし，引数が三つのときは，第二引数が長さ，第三引数が値となる．
    if (!trie_builder.insert(keys[key_id].c_str(), key_id))
    {
      std::cerr << "error: failed to insert key: "
                << keys[key_id] << std::endl;
      return 1;
    }
  }

  // トライの構築を完了する．
  if (!trie_builder.finish())
  {
    std::cerr << "error: failed to finish building trie" << std::endl;
    return 2;
  }

  // TrieBuilder により得られた一時的なトライを元に，
  // 他の実装によるトライを構築する．
  sumire::BasicTrie trie;
  if (!trie.build(trie_builder.virtual_trie()))
  {
    std::cerr << "error: failed to convert trie" << std::endl;
    return 3;
  }

  // BasicTrie については，build() に第二引数を渡すことができる．
  // 引数なし : 深さ優先にノードを配置する．
  // sumire::BasicTrie::LEVEL_ORDER : 浅い順（幅優先）にノードを配置する．
  // sumire::BasicTrie::BREADTH_ORDER :
  //  子孫に関連付けられている値の数が降順になるように子ノードを整列する．
  // sumire::BasicTrie::MAX_VALUE_ORDER :
  //  子孫に関連付けられている値の最大値が降順になるように子ノードを整列する．
  //  sumire::ValueOrderCompleter を用いた重み付きキー補完において必要になる．
  // sumire::BasicTrie::TOTAL_VALUE_ORDER :
  //  子孫に関連付けられている値の合計が降順になるように子ノードを整列する．

  // BasicTrie 以外にも，次のような選択肢がある．
  // TernaryTrie, DaTrie, SuccinctTrie<>, LoudsTrie<>, LoudsPlusTrie<>
  // テンプレート引数には，Succinct Bit Vector のクラスを指定できる．
  // SimplifiedSuccinctBitVector, HybridSuccinctBitVector

  // キーが正しく登録されているかどうかを確かめる．
  for (std::size_t key_id = 0; key_id < keys.size(); ++key_id)
  {
    sumire::UInt32 value;
    if (!trie.find(keys[key_id].c_str(), &value))
    {
      std::cerr << "error: failed to find key: "
                << keys[key_id] << std::endl;
      return 4;
    }
    else if (value != key_id)
    {
      std::cerr << "error: wrong key value pair: "
                << keys[key_id] << ", " << value << std::endl;
      return 5;
    }
  }

  return 0;
}