nlib
|
ビットベクトルに関する簡潔データ構造クラスのライブラリが実装されています。 [詳解]
クラス | |
class | AhoCorasick |
AC法を用いて語やパターンの検出を行います。 [詳解] | |
class | AhoCorasickBuilder |
AC法で用いるインデックス(オートマトン)を作成します。 [詳解] | |
class | Bp |
各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。 [詳解] | |
class | CompressedArray |
追記可能な圧縮された整数配列です。 [詳解] | |
class | Louds |
各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。 [詳解] | |
class | Map |
整数から整数へのコンパクトなリードオンリーの連想配列です。 [詳解] | |
class | Sbv |
Rank/Select 操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。 [詳解] | |
class | Set |
Rank/Select 操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。 [詳解] | |
class | SparseSet |
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。 [詳解] | |
class | Trie |
LOUDSを利用したTrieの実装です。 [詳解] | |
class | TrieBuilder |
Trie オブジェクトを作成するためのクラスです。 [詳解] | |
class | WordFilter |
文章内に事前に指定した語の集合が含まれていないかどうかチェックするためのクラスです。 [詳解] | |
class | WordFilterBuilder |
語と除外語に対応するWordFilter オブジェクトを作成するクラスです。 [詳解] | |
ビットベクトルに関する簡潔データ構造クラスのライブラリが実装されています。
rank
と呼ばれる操作とi番目の1の位置を求めるselect
という操作が基本になります。 これは例えば以下のような結果になります(基数を0としています)。 B=00110100...., rank1(5)=3, select1(1)=3
rank
/select
操作はビットベクトルにデータを追加することで高速に行うことが可能になります。 これを簡潔ビットベクトルと呼びます。 この簡潔ビットベクトルを用いて様々な簡潔データ構造を作ることができます。 Sbv
, SmartBitmap
(misc
ライブラリ) Sbv
, SmartBitmap
Map
Louds
, Bp
Trie
, TrieBuilder
AhoCorasick
, AhoCorasickBuilder
WordFilter
, WordFilterBuilder
© 2012-2017 Nintendo Co., Ltd. All rights reserved.