nlib
|
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... | |
Implements a library of succinct data structure classes related to bit vectors.
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. rank1(5)=3, select1(1)=3
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. Sbv
, SmartBitmap
(misc
library) as a class for succinct bit vectors Sbv
, SmartBitmap
as a class for integer sets Map
as a class that maps integers to integers Louds
, Bp
as a class for succinct trees Trie
, TrieBuilder
as a class of Tries AhoCorasick
, AhoCorasickBuilder
as a class for the dictionary of an Aho-Corasick algorithm WordFilter
, WordFilterBuilder
as a class for word detection © 2012-2017 Nintendo Co., Ltd. All rights reserved.