nlib
nn::nlib::succinct 名前空間

ビットベクトルに関する簡潔データ構造クラスのライブラリが実装されています。 [詳解]

クラス

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オブジェクトを作成するクラスです。 [詳解]
 

詳解

ビットベクトルに関する簡潔データ構造クラスのライブラリが実装されています。

説明
簡潔データ構造(succinct data structure)とは、データサイズが小さいながらも各種操作を高速に(定数時間かそれに準ずる時間で)処理できるように設計されたデータ構造のことを言います。 大規模なデータをメモリに搭載する必要性から近年注目を浴びているデータ構造です。
ビットベクトルに関しては、先頭からi番目までのビット中の1の数を求めるrankと呼ばれる操作とi番目の1の位置を求めるselectという操作が基本になります。 これは例えば以下のような結果になります(基数を0としています)。
  • B=00110100...., rank1(5)=3, select1(1)=3
rank/select操作はビットベクトルにデータを追加することで高速に行うことが可能になります。 これを簡潔ビットベクトルと呼びます。 この簡潔ビットベクトルを用いて様々な簡潔データ構造を作ることができます。
このライブラリでは、以下のような機能が実装されています。