LOUDS Trie ライブラリを書いた

C++ で LOUDS Trie を扱うライブラリhsds::Trieを書きました。

GitHub - hideo55/cpp-HSDS: Succinct Data Structure Library Collection.Includes bit-vector/wavelet-matrix/trie.

LOUDS Trieとは?

Level-Order Unary Degree Sequence という木構造を表現するデータ構造を利用したTrie木です。

Space-efficient Static Trees and Graphs

hsds::Trie の機能

現在は以下の機能をサポートしています。

  • 木のノードレベルでの探索(traverse)
  • 完全一致検索(exactMatchSearch)
  • 共通接頭辞検索(commonPrefixSearch)
  • クエリ文字列を接頭辞に含む全てのキーを列挙(predictiveSearch)
  • ノードIDからキー文字列の復元(decodeKey)
  • Trieのファイル書き出し、読み込み、mmap
  • TAIL配列の圧縮

特に、traverse は私のユースケースでは重要なのですが、tx-trie、ux-trie 等のLOUDS Trieの実装では提供されていませんでした。

なお、hsds::Trieでは内部で使用する簡潔ビットベクトルの実装として、以前作成した簡潔ビットベクトルライブラリを採用しています。

パフォーマンス

しっかりしたベンチマークはまだとっていませんが、ランダム文字列の共通接頭辞検索でux-trieの3倍以上の速さでした。
これは使用している簡潔ビットベクトルの速度の差によるものと考えています。