nlib
nn::nlib::succinct Namespace Reference

Implements a library of succinct data structure classes related to bit vectors. More...

Classes

class  AhoCorasick
 Uses the Aho-Corasick algorithm to detect language and patterns. More...
 
class  AhoCorasickBuilder
 Creates the index (automaton) used in the Aho-Corasick algorithm. More...
 
class  Bp
 Provides a compact tree structure that can provide various operations in \(O(1)\) constant time. More...
 
class  CompressedArray
 A compressed array of integers that allows appending additional data. More...
 
class  Louds
 Provides a compact tree structure that can provide various operations in \(O(1)\) constant time. More...
 
class  Map
 A compact integer to integer read-only associative array. More...
 
class  Sbv
 Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation. More...
 
class  Set
 Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation. More...
 
class  SparseSet
 Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers. More...
 
class  Trie
 Implements Trie using LOUDS. More...
 
class  TrieBuilder
 Class to create a Trie object. More...
 
class  WordFilter
 Class that checks whether text contains the predefined set of words. More...
 
class  WordFilterBuilder
 Class to create a WordFilter object that corresponds to a term and excluded terms. More...
 

Detailed Description

Implements a library of succinct data structure classes related to bit vectors.

Description
A succinct data structure is designed to be small and able to be processed quickly (in constant time or some similar rate). Succinct data structures are noted for the ability to load large data into memory.
rank and select are basic bit vector operations. rank finds the number of 1s from the top to the ith bit. select finds the position of the ith 1. For example, using these operations finds the following results. Both operations take 0 as their cardinal number.
  • B=00110100...., rank1(5)=3, select1(1)=3
Both rank/select operations are executed at high speed by adding data to the bit vector. This is called a succinct bit vector. A range of succinct data structures can be built using these succinct bit vectors.
The library implements the following.