Compressed bit parallel nonlinear tree index. Stores a bit vector for each symbol of the alphabet. The bit vector of symbol a contains true on index i if symbol a is on i-th position in the indexed string. The class does not check whether the bit vectors actually represent valid index. The bit vectors are compressed with run length encoding packing runs of false values. Additionally the index contains a subtree jump table representing positions after a jump over a subtree. The index is supposed to be able to provide data to search for nonlinear tree patterns. Therefore it also contains representation of subtree repeats. More...
#include <NonlinearCompressedBitParallelTreeIndex.h>
Friends | |
| ext::ostream & | operator<< (ext::ostream &out, const NonlinearCompressedBitParallelTreeIndex &instance) |
Additional Inherited Members | |
 Static Public Member Functions inherited from core::Components< NonlinearCompressedBitParallelTreeIndex< DefaultSymbolType >, ext::set< common::ranked_symbol< DefaultSymbolType > >, component::Set, GeneralAlphabet > | |
| static void | registerComponent () |
| static void | unregisterComponent () |
Detailed Description
class indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >
Compressed bit parallel nonlinear tree index. Stores a bit vector for each symbol of the alphabet. The bit vector of symbol a contains true on index i if symbol a is on i-th position in the indexed string. The class does not check whether the bit vectors actually represent valid index. The bit vectors are compressed with run length encoding packing runs of false values. Additionally the index contains a subtree jump table representing positions after a jump over a subtree. The index is supposed to be able to provide data to search for nonlinear tree patterns. Therefore it also contains representation of subtree repeats.
The actual notation of used tree is irelevant. The index, as fas as the data structure is concerned, is not different. Of course tree in postfix notation must be queried with patterns in postfix notation, etc.
- Template Parameters
-
SymbolType used for the symbol part of the ranked symbol
Constructor & Destructor Documentation
◆ NonlinearCompressedBitParallelTreeIndex()
|
explicit |
Creates a new instance of the index with concrete alphabet, bit vectors, subtree jump table, and subtree repeats.
- Parameters
-
alphabet the alphabet of indexed string vectors the compressed bit vectors jumpTable the subtree jump table repeats the subtree repeats table
Member Function Documentation
◆ getAlphabet() [1/2]
|
inline |
Getter of the alphabet of the indexed tree.
- Returns
- the alphabet of the indexed tree
◆ getAlphabet() [2/2]
|
inline |
Getter of the alphabet of the indexed tree.
- Returns
- the alphabet of the indexed tree
◆ getData() [1/2]
| ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > && indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getData | ( | ) | && |
Getter of the compressed bit vectors.
- Returns
- compressed bit vectors
◆ getData() [2/2]
| const ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > & indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getData | ( | ) | const & |
Getter of the compressed bit vectors.
- Returns
- compressed bit vectors
◆ getJumps() [1/2]
| ext::vector< int > && indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getJumps | ( | ) | && |
Getter of the subtree jump table
- Returns
- the subtree jump table
◆ getJumps() [2/2]
| const ext::vector< int > & indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getJumps | ( | ) | const & |
Getter of the subtree jump table
- Returns
- the subtree jump table
◆ getRepeats() [1/2]
| ext::vector< unsigned > && indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getRepeats | ( | ) | && |
Getter of the subtree repeats table
- Returns
- the subtree repeats table
◆ getRepeats() [2/2]
| const ext::vector< unsigned > & indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getRepeats | ( | ) | const & |
Getter of the subtree repeats table
- Returns
- the subtree repeats table
◆ getString()
| ext::vector< common::ranked_symbol< SymbolType > > indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::getString |
Reconstructs the indexed string from bit vectors.
- Returns
- the original indexed string
◆ operator<=>()
|
inline |
The three way comparison implementation
- Parameters
-
other the other instance
- Returns
- the ordering between this object and the
other.
◆ operator==()
|
inline |
The equality comparison implementation.
- Parameters
-
other the other object to compare with.
- Returns
- true if this and other objects are equal, false othervise
◆ removeSymbolFromAlphabet()
|
inline |
Remover of a symbol from the alphabet. The symbol can be removed if it is not used in any of bit vector keys.
- Parameters
-
symbol a symbol to remove.
◆ setNonlinearCompressedBitVectorForSymbol()
| void indexes::arbology::NonlinearCompressedBitParallelTreeIndex< SymbolType >::setNonlinearCompressedBitVectorForSymbol | ( | common::ranked_symbol< SymbolType > | symbol, |
| common::SparseBoolVector | data | ||
| ) |
Changes the bit vector for concrete symbol.
- Parameters
-
symbol the changed symbol data the new bit vector
Friends And Related Function Documentation
◆ operator<<
|
friend |
Print this object as raw representation to ostream.
- Parameters
-
out ostream where to print instance object to print
- Returns
- modified output stream
The documentation for this class was generated from the following file:
- alib2data/src/indexes/arbology/NonlinearCompressedBitParallelTreeIndex.h
