SHOGUN
v1.1.0
|
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 tree 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.
Public Member Functions | |
CTrie () | |
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, DynArray< ConsensusEntry > *table, float64_t *weights) |
void | fill_backtracking_table (int32_t pos, DynArray< ConsensusEntry > *prev, DynArray< 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 (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 |
template<> | |
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) |
template<> | |
void | POIMs_extract_W (float64_t *const *const W, const int32_t K) |
template<> | |
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) |
template<> | |
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) |
template<> | |
void | POIMs_precalc_SLR (const float64_t *const distrib) |
template<> | |
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) |
template<> | |
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) |
template<> | |
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) |
template<> | |
void | POIMs_add_SLR (float64_t *const *const poims, const int32_t K, const int32_t debug) |
Public Attributes | |
int32_t | NUM_SYMS |
Protected Attributes | |
int32_t | length |
int32_t * | trees |
int32_t | degree |
float64_t * | position_weights |
Trie * | TreeMem |
int32_t | TreeMemPtr |
int32_t | TreeMemPtrMax |
bool | use_compact_terminal_nodes |
bool | weights_in_tree |
int32_t * | nofsKmers |
CTrie | ( | int32_t | d, |
bool | p_use_compact_terminal_nodes = true |
||
) |
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 add_to_trie | ( | int32_t | i, |
int32_t | seq_offset, | ||
int32_t * | vec, | ||
float32_t | alpha, | ||
float64_t * | weights, | ||
bool | degree_times_position_weights | ||
) |
void check_treemem | ( | ) |
int32_t compact_nodes | ( | int32_t | start_node, |
int32_t | depth, | ||
float64_t * | weights | ||
) |
bool compare_traverse | ( | int32_t | node, |
const CTrie< Trie > & | other, | ||
int32_t | other_node | ||
) |
float64_t * compute_abs_weights | ( | int32_t & | len | ) |
float64_t compute_abs_weights_tree | ( | int32_t | tree, |
int32_t | depth | ||
) |
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 | ||
) |
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 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 create | ( | int32_t | len, |
bool | p_use_compact_terminal_nodes = true |
||
) |
void delete_trees | ( | bool | p_use_compact_terminal_nodes = true | ) |
void display_node | ( | int32_t | node | ) | const |
void fill_backtracking_table | ( | int32_t | pos, |
DynArray< ConsensusEntry > * | prev, | ||
DynArray< ConsensusEntry > * | cur, | ||
bool | cumulative, | ||
float64_t * | weights | ||
) |
void fill_backtracking_table_recursion | ( | Trie * | tree, |
int32_t | depth, | ||
uint64_t | seq, | ||
float64_t | value, | ||
DynArray< ConsensusEntry > * | table, | ||
float64_t * | weights | ||
) |
int32_t find_deepest_node | ( | int32_t | start_node, |
int32_t & | deepest_node | ||
) | const |
bool find_node | ( | int32_t | node, |
int32_t * | trace, | ||
int32_t & | trace_len | ||
) | const |
float64_t get_cumulative_score | ( | int32_t | pos, |
uint64_t | seq, | ||
int32_t | deg, | ||
float64_t * | weights | ||
) |
virtual const char* get_name | ( | ) | const [virtual] |
int32_t get_node | ( | bool | last_node = false | ) |
int32_t get_num_used_nodes | ( | ) |
bool get_use_compact_terminal_nodes | ( | ) |
bool get_weights_in_tree | ( | ) |
void POIMs_add_SLR | ( | float64_t *const *const | poims, |
const int32_t | K, | ||
const int32_t | debug | ||
) |
void 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 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_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 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 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_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 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_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 POIMs_extract_W | ( | float64_t *const *const | W, |
const int32_t | K | ||
) |
void POIMs_extract_W | ( | float64_t *const *const | W, |
const int32_t | K | ||
) |
POIMs extract W
W | W |
K | K |
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_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 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_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 |
void POIMs_precalc_SLR | ( | const float64_t *const | distrib | ) |
void POIMs_precalc_SLR | ( | const float64_t *const | distrib | ) |
POIMs precalc SLR
distrib | distribution |
void set_degree | ( | int32_t | d | ) |
void set_position_weights | ( | float64_t * | p_position_weights | ) |
void set_use_compact_terminal_nodes | ( | bool | p_use_compact_terminal_nodes | ) |
void set_weights_in_tree | ( | bool | weights_in_tree_ | ) |
void 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* position_weights [protected] |
int32_t TreeMemPtr [protected] |
int32_t TreeMemPtrMax [protected] |
bool use_compact_terminal_nodes [protected] |
bool weights_in_tree [protected] |