LOUDS Trie ライブラリを書いた
C++ で LOUDS Trie を扱うライブラリhsds::Trieを書きました。
hsds::Trie の機能
現在は以下の機能をサポートしています。
- 木のノードレベルでの探索(traverse)
- 完全一致検索(exactMatchSearch)
- 共通接頭辞検索(commonPrefixSearch)
- クエリ文字列を接頭辞に含む全てのキーを列挙(predictiveSearch)
- ノードIDからキー文字列の復元(decodeKey)
- Trieのファイル書き出し、読み込み、mmap
- TAIL配列の圧縮
特に、traverse は私のユースケースでは重要なのですが、tx-trie、ux-trie 等のLOUDS Trieの実装では提供されていませんでした。
なお、hsds::Trieでは内部で使用する簡潔ビットベクトルの実装として、以前作成した簡潔ビットベクトルライブラリを採用しています。
パフォーマンス
しっかりしたベンチマークはまだとっていませんが、ランダム文字列の共通接頭辞検索でux-trieの3倍以上の速さでした。
これは使用している簡潔ビットベクトルの速度の差によるものと考えています。