template<class Trie>
class shogun::CTrie< Trie >
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.
Definition at line 156 of file Trie.h.
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) |
| CSGObject () |
| CSGObject (const CSGObject &orig) |
virtual | ~CSGObject () |
virtual bool | is_generic (EPrimitiveType *generic) const |
template<class T > |
void | set_generic () |
void | unset_generic () |
virtual void | print_serializable (const char *prefix="") |
virtual bool | save_serializable (CSerializableFile *file, const char *prefix="") |
virtual bool | load_serializable (CSerializableFile *file, const char *prefix="") |
void | set_global_io (SGIO *io) |
SGIO * | get_global_io () |
void | set_global_parallel (Parallel *parallel) |
Parallel * | get_global_parallel () |
void | set_global_version (Version *version) |
Version * | get_global_version () |
SGVector< char * > | get_modelsel_names () |
char * | get_modsel_param_descr (const char *param_name) |
index_t | get_modsel_param_index (const char *param_name) |