Template class Trie implements a suffix trie, i.e. a tree in which all suffixes up to a certain length are stored.
It is excessively used in the CWeightedDegreeStringKernel and CWeightedDegreePositionStringKernel to construct the whole features space and enormously helps here to speed up SVM training and evaluation.
Note that depending on the underlying structure used, a single symbol in the tree requires 20 bytes (DNATrie). It is also used to do the efficient recursion in computing positional oligomer importance matrices (POIMs) where the structure requires * 20+3*8 (POIMTrie) bytes.
Finally note that this try may use compact internal nodes (for strings that appear without modifications, thus not requiring further branches), which may save a lot of memory on higher degree tries.
Definition at line 153 of file Trie.h.
Public Member Functions | |
CTrie (int32_t d, bool p_use_compact_terminal_nodes=true) | |
CTrie (const CTrie &to_copy) | |
virtual | ~CTrie () |
const CTrie & | operator= (const CTrie &to_copy) |
bool | compare_traverse (int32_t node, const CTrie &other, int32_t other_node) |
bool | compare (const CTrie &other) |
bool | find_node (int32_t node, int32_t *trace, int32_t &trace_len) const |
int32_t | find_deepest_node (int32_t start_node, int32_t &deepest_node) const |
void | display_node (int32_t node) const |
void | destroy () |
void | set_degree (int32_t d) |
void | create (int32_t len, bool p_use_compact_terminal_nodes=true) |
void | delete_trees (bool p_use_compact_terminal_nodes=true) |
void | add_to_trie (int32_t i, int32_t seq_offset, int32_t *vec, float32_t alpha, float64_t *weights, bool degree_times_position_weights) |
float64_t | compute_abs_weights_tree (int32_t tree, int32_t depth) |
float64_t * | compute_abs_weights (int32_t &len) |
float64_t | compute_by_tree_helper (int32_t *vec, int32_t len, int32_t seq_pos, int32_t tree_pos, int32_t weight_pos, float64_t *weights, bool degree_times_position_weights) |
void | compute_by_tree_helper (int32_t *vec, int32_t len, int32_t seq_pos, int32_t tree_pos, int32_t weight_pos, float64_t *LevelContrib, float64_t factor, int32_t mkl_stepsize, float64_t *weights, bool degree_times_position_weights) |
void | compute_scoring_helper (int32_t tree, int32_t i, int32_t j, float64_t weight, int32_t d, int32_t max_degree, int32_t num_feat, int32_t num_sym, int32_t sym_offset, int32_t offs, float64_t *result) |
void | add_example_to_tree_mismatch_recursion (int32_t tree, int32_t i, float64_t alpha, int32_t *vec, int32_t len_rem, int32_t degree_rec, int32_t mismatch_rec, int32_t max_mismatch, float64_t *weights) |
void | traverse (int32_t tree, const int32_t p, struct TreeParseInfo info, const int32_t depth, int32_t *const x, const int32_t k) |
void | count (const float64_t w, const int32_t depth, const struct TreeParseInfo info, const int32_t p, int32_t *x, const int32_t k) |
int32_t | compact_nodes (int32_t start_node, int32_t depth, float64_t *weights) |
float64_t | get_cumulative_score (int32_t pos, uint64_t seq, int32_t deg, float64_t *weights) |
void | fill_backtracking_table_recursion (Trie *tree, int32_t depth, uint64_t seq, float64_t value, CDynamicArray< ConsensusEntry > *table, float64_t *weights) |
void | fill_backtracking_table (int32_t pos, CDynamicArray< ConsensusEntry > *prev, CDynamicArray< ConsensusEntry > *cur, bool cumulative, float64_t *weights) |
void | POIMs_extract_W (float64_t *const *const W, const int32_t K) |
void | POIMs_precalc_SLR (const float64_t *const distrib) |
void | POIMs_get_SLR (const int32_t parentIdx, const int32_t sym, const int32_t depth, float64_t *S, float64_t *L, float64_t *R) |
void | POIMs_add_SLR (float64_t *const *const poims, const int32_t K, const int32_t debug) |
bool | get_use_compact_terminal_nodes () |
void | set_use_compact_terminal_nodes (bool p_use_compact_terminal_nodes) |
int32_t | get_num_used_nodes () |
void | set_position_weights (const float64_t *p_position_weights) |
int32_t | get_node (bool last_node=false) |
void | check_treemem () |
void | set_weights_in_tree (bool weights_in_tree_) |
bool | get_weights_in_tree () |
void | POIMs_extract_W_helper (const int32_t nodeIdx, const int32_t depth, const int32_t offset, const int32_t y0, float64_t *const *const W, const int32_t K) |
void | POIMs_calc_SLR_helper1 (const float64_t *const distrib, const int32_t i, const int32_t nodeIdx, int32_t left_tries_idx[4], const int32_t depth, int32_t const lastSym, float64_t *S, float64_t *L, float64_t *R) |
void | POIMs_calc_SLR_helper2 (const float64_t *const distrib, const int32_t i, const int32_t nodeIdx, int32_t left_tries_idx[4], const int32_t depth, float64_t *S, float64_t *L, float64_t *R) |
void | POIMs_add_SLR_helper1 (const int32_t nodeIdx, const int32_t depth, const int32_t i, const int32_t y0, float64_t *const *const poims, const int32_t K, const int32_t debug) |
void | POIMs_add_SLR_helper2 (float64_t *const *const poims, const int32_t K, const int32_t k, const int32_t i, const int32_t y, const float64_t valW, const float64_t valS, const float64_t valL, const float64_t valR, const int32_t debug) |
virtual const char * | get_name () const |
Public Attributes | |
int32_t | NUM_SYMS |
Protected Attributes | |
int32_t | length |
int32_t * | trees |
int32_t | degree |
float64_t const * | position_weights |
Trie * | TreeMem |
int32_t | TreeMemPtr |
int32_t | TreeMemPtrMax |
bool | use_compact_terminal_nodes |
bool | weights_in_tree |
int32_t * | nofsKmers |
void CTrie< Trie >::check_treemem | ( | ) |
void CTrie< Trie >::compute_by_tree_helper | ( | int32_t * | vec, | |
int32_t | len, | |||
int32_t | seq_pos, | |||
int32_t | tree_pos, | |||
int32_t | weight_pos, | |||
float64_t * | LevelContrib, | |||
float64_t | factor, | |||
int32_t | mkl_stepsize, | |||
float64_t * | weights, | |||
bool | degree_times_position_weights | |||
) |
compute by tree helper
vec | vector | |
len | length | |
seq_pos | sequence position | |
tree_pos | tree position | |
weight_pos | weight position | |
LevelContrib | level contribution | |
factor | factor | |
mkl_stepsize | MKL stepsize | |
weights | ||
degree_times_position_weights | if degree times position weights shall be applied |
void CTrie< Trie >::create | ( | int32_t | len, | |
bool | p_use_compact_terminal_nodes = true | |||
) |
void CTrie< Trie >::delete_trees | ( | bool | p_use_compact_terminal_nodes = true |
) |
void CTrie< Trie >::destroy | ( | ) |
void CTrie< Trie >::display_node | ( | int32_t | node | ) | const |
void CTrie< Trie >::fill_backtracking_table | ( | int32_t | pos, | |
CDynamicArray< ConsensusEntry > * | prev, | |||
CDynamicArray< ConsensusEntry > * | cur, | |||
bool | cumulative, | |||
float64_t * | weights | |||
) |
void CTrie< Trie >::fill_backtracking_table_recursion | ( | Trie * | tree, | |
int32_t | depth, | |||
uint64_t | seq, | |||
float64_t | value, | |||
CDynamicArray< ConsensusEntry > * | table, | |||
float64_t * | weights | |||
) |
int32_t CTrie< Trie >::find_deepest_node | ( | int32_t | start_node, | |
int32_t & | deepest_node | |||
) | const |
bool CTrie< Trie >::find_node | ( | int32_t | node, | |
int32_t * | trace, | |||
int32_t & | trace_len | |||
) | const |
virtual const char* CTrie< Trie >::get_name | ( | ) | const [virtual] |
int32_t CTrie< Trie >::get_node | ( | bool | last_node = false |
) |
int32_t CTrie< Trie >::get_num_used_nodes | ( | ) |
bool CTrie< Trie >::get_use_compact_terminal_nodes | ( | ) |
bool CTrie< Trie >::get_weights_in_tree | ( | ) |
void CTrie< Trie >::POIMs_add_SLR | ( | float64_t *const *const | poims, | |
const int32_t | K, | |||
const int32_t | debug | |||
) |
POIMs add SLR
poims | POIMs | |
K | K | |
debug | debug level |
void CTrie< Trie >::POIMs_add_SLR_helper1 | ( | const int32_t | nodeIdx, | |
const int32_t | depth, | |||
const int32_t | i, | |||
const int32_t | y0, | |||
float64_t *const *const | poims, | |||
const int32_t | K, | |||
const int32_t | debug | |||
) |
POIMs add SLR helper 1
nodeIdx | node index | |
depth | depth | |
i | i | |
y0 | y0 | |
poims | POIMs | |
K | K | |
debug | debug level |
void CTrie< Trie >::POIMs_add_SLR_helper2 | ( | float64_t *const *const | poims, | |
const int32_t | K, | |||
const int32_t | k, | |||
const int32_t | i, | |||
const int32_t | y, | |||
const float64_t | valW, | |||
const float64_t | valS, | |||
const float64_t | valL, | |||
const float64_t | valR, | |||
const int32_t | debug | |||
) |
POIMs add SLR helper 2
poims | POIMs | |
K | K | |
k | k | |
i | i | |
y | y | |
valW | value W | |
valS | value S | |
valL | value L | |
valR | value R | |
debug | debug level |
void CTrie< Trie >::POIMs_calc_SLR_helper1 | ( | const float64_t *const | distrib, | |
const int32_t | i, | |||
const int32_t | nodeIdx, | |||
int32_t | left_tries_idx[4], | |||
const int32_t | depth, | |||
int32_t const | lastSym, | |||
float64_t * | S, | |||
float64_t * | L, | |||
float64_t * | R | |||
) |
POIMs calc SLR helper
distrib | distribution | |
i | i | |
nodeIdx | node index | |
left_tries_idx | left tries index | |
depth | depth | |
lastSym | last symbol | |
S | S | |
L | L | |
R | R |
void CTrie< Trie >::POIMs_calc_SLR_helper2 | ( | const float64_t *const | distrib, | |
const int32_t | i, | |||
const int32_t | nodeIdx, | |||
int32_t | left_tries_idx[4], | |||
const int32_t | depth, | |||
float64_t * | S, | |||
float64_t * | L, | |||
float64_t * | R | |||
) |
POIMs calc SLR helper 2
distrib | distribution | |
i | i | |
nodeIdx | node index | |
left_tries_idx | left tries index | |
depth | depth | |
S | S | |
L | L | |
R | R |
void CTrie< Trie >::POIMs_extract_W | ( | float64_t *const *const | W, | |
const int32_t | K | |||
) |
POIMs extract W
W | W | |
K | K |
void CTrie< Trie >::POIMs_extract_W_helper | ( | const int32_t | nodeIdx, | |
const int32_t | depth, | |||
const int32_t | offset, | |||
const int32_t | y0, | |||
float64_t *const *const | W, | |||
const int32_t | K | |||
) |
POIMs extract W helper
nodeIdx | node index | |
depth | depth | |
offset | offset | |
y0 | y0 | |
W | W | |
K | K |
void CTrie< Trie >::POIMs_get_SLR | ( | const int32_t | parentIdx, | |
const int32_t | sym, | |||
const int32_t | depth, | |||
float64_t * | S, | |||
float64_t * | L, | |||
float64_t * | R | |||
) |
POIMs get SLR
parentIdx | parent index | |
sym | symbol | |
depth | depth | |
S | will point to S | |
L | will point to L | |
R | will point to R |
POIMs precalc SLR
distrib | distribution |
void CTrie< Trie >::set_degree | ( | int32_t | d | ) |
void CTrie< Trie >::set_use_compact_terminal_nodes | ( | bool | p_use_compact_terminal_nodes | ) |
void CTrie< Trie >::set_weights_in_tree | ( | bool | weights_in_tree_ | ) |
void CTrie< Trie >::traverse | ( | int32_t | tree, | |
const int32_t | p, | |||
struct TreeParseInfo | info, | |||
const int32_t | depth, | |||
int32_t *const | x, | |||
const int32_t | k | |||
) |
float64_t const* CTrie< Trie >::position_weights [protected] |
int32_t CTrie< Trie >::TreeMemPtr [protected] |
int32_t CTrie< Trie >::TreeMemPtrMax [protected] |
bool CTrie< Trie >::use_compact_terminal_nodes [protected] |
bool CTrie< Trie >::weights_in_tree [protected] |