25 #ifndef DOXYGEN_SHOULD_SKIP_THIS
28 #define NO_CHILD ((int32_t)-1073741824)
30 #define WEIGHTS_IN_TRIE
33 #ifdef TRIE_CHECK_EVERYTHING
34 #define TRIE_ASSERT_EVERYTHING(x) ASSERT(x)
36 #define TRIE_ASSERT_EVERYTHING(x)
40 #define TRIE_ASSERT(x)
42 #define TRIE_TERMINAL_CHARACTER 7
60 #ifdef TRIE_CHECK_EVERYTHING
89 #ifdef TRIE_CHECK_EVERYTHING
107 struct TreeParseInfo {
134 #endif // DOXYGEN_SHOULD_SKIP_THIS
138 #define IGNORE_IN_CLASSLIST
169 CTrie(int32_t d,
bool p_use_compact_terminal_nodes=
true);
186 int32_t
node,
const CTrie & other, int32_t other_node);
201 bool find_node(int32_t node, int32_t * trace, int32_t &trace_len)
const;
210 int32_t start_node, int32_t &deepest_node)
const;
233 void create(int32_t len,
bool p_use_compact_terminal_nodes=
true);
240 void delete_trees(
bool p_use_compact_terminal_nodes=
true);
253 int32_t i, int32_t seq_offset, int32_t* vec,
float32_t alpha,
254 float64_t *weights,
bool degree_times_position_weights);
284 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
286 bool degree_times_position_weights) ;
303 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
305 int32_t mkl_stepsize,
float64_t * weights,
306 bool degree_times_position_weights);
323 int32_t tree, int32_t i, int32_t j,
float64_t weight, int32_t d,
324 int32_t max_degree, int32_t num_feat, int32_t num_sym,
325 int32_t sym_offset, int32_t offs,
float64_t* result);
340 int32_t tree, int32_t i,
float64_t alpha, int32_t *vec,
341 int32_t len_rem, int32_t degree_rec, int32_t mismatch_rec,
342 int32_t max_mismatch,
float64_t * weights);
354 int32_t tree,
const int32_t p,
struct TreeParseInfo info,
355 const int32_t depth, int32_t*
const x,
const int32_t k);
368 const struct TreeParseInfo info,
const int32_t p, int32_t* x,
388 int32_t pos, uint64_t seq, int32_t deg,
float64_t* weights);
400 Trie* tree, int32_t depth, uint64_t seq,
float64_t value,
401 DynArray<ConsensusEntry>* table,
float64_t* weights);
412 int32_t pos, DynArray<ConsensusEntry>* prev,
413 DynArray<ConsensusEntry>* cur,
bool cumulative,
439 const int32_t parentIdx,
const int32_t sym,
const int32_t depth,
449 float64_t*
const*
const poims,
const int32_t K,
450 const int32_t debug);
467 bool p_use_compact_terminal_nodes)
501 for (int32_t q=0; q<4; q++)
502 TreeMem[ret].child_weights[q]=0.0;
506 for (int32_t q=0; q<4; q++)
507 TreeMem[ret].children[q]=NO_CHILD;
509 #ifdef TRIE_CHECK_EVERYTHING
511 TreeMem[ret].has_floats=false ;
522 SG_DEBUG(
"Extending TreeMem from %i to %i elements\n",
525 TreeMemPtrMax = (int32_t) ((
float64_t)TreeMemPtrMax*1.2);
557 const int32_t nodeIdx,
const int32_t depth,
const int32_t offset,
558 const int32_t y0,
float64_t*
const*
const W,
const int32_t K);
573 const float64_t*
const distrib,
const int32_t i,
574 const int32_t nodeIdx, int32_t left_tries_idx[4],
575 const int32_t depth, int32_t
const lastSym,
float64_t* S,
590 const float64_t*
const distrib,
const int32_t i,
591 const int32_t nodeIdx, int32_t left_tries_idx[4],
605 const int32_t nodeIdx,
const int32_t depth,
const int32_t i,
606 const int32_t y0,
float64_t*
const*
const poims,
const int32_t K,
607 const int32_t debug);
623 float64_t*
const*
const poims,
const int32_t K,
const int32_t k,
624 const int32_t i,
const int32_t y,
const float64_t valW,
626 const int32_t debug);
629 virtual const char*
get_name()
const {
return "Trie"; }
661 template <
class Trie>
663 :
CSGObject(), degree(0), position_weights(NULL),
664 use_compact_terminal_nodes(false),
665 weights_in_tree(true)
678 template <
class Trie>
680 :
CSGObject(), degree(d), position_weights(NULL),
681 use_compact_terminal_nodes(p_use_compact_terminal_nodes),
682 weights_in_tree(true)
694 template <
class Trie>
696 :
CSGObject(to_copy), degree(to_copy.degree), position_weights(NULL),
697 use_compact_terminal_nodes(to_copy.use_compact_terminal_nodes)
699 if (to_copy.position_weights!=NULL)
716 for (int32_t i=0; i<
length; i++)
717 trees[i]=to_copy.trees[i];
722 template <
class Trie>
725 degree=to_copy.degree ;
726 use_compact_terminal_nodes=to_copy.use_compact_terminal_nodes ;
728 SG_FREE(position_weights);
729 position_weights=NULL ;
730 if (to_copy.position_weights!=NULL)
732 position_weights=to_copy.position_weights ;
738 position_weights=NULL ;
740 TreeMemPtrMax=to_copy.TreeMemPtrMax ;
741 TreeMemPtr=to_copy.TreeMemPtr ;
743 TreeMem = SG_MALLOC(Trie, TreeMemPtrMax);
744 memcpy(TreeMem, to_copy.TreeMem, TreeMemPtrMax*
sizeof(Trie)) ;
746 length = to_copy.length ;
749 trees=SG_MALLOC(int32_t, length);
750 for (int32_t i=0; i<length; i++)
751 trees[i]=to_copy.trees[i] ;
756 template <
class Trie>
758 int32_t start_node, int32_t& deepest_node)
const
760 #ifdef TRIE_CHECK_EVERYTHING
762 SG_DEBUG(
"start_node=%i\n", start_node)
764 if (start_node==NO_CHILD)
766 for (int32_t i=0; i<length; i++)
768 int32_t my_deepest_node ;
769 int32_t depth=find_deepest_node(i, my_deepest_node) ;
770 SG_DEBUG(
"start_node %i depth=%i\n", i, depth)
773 deepest_node=my_deepest_node ;
780 if (TreeMem[start_node].has_seq)
782 for (int32_t q=0; q<16; q++)
783 if (TreeMem[start_node].seq[q]!=TRIE_TERMINAL_CHARACTER)
785 deepest_node=start_node ;
788 if (TreeMem[start_node].has_floats)
790 deepest_node=start_node ;
794 for (int32_t q=0; q<4; q++)
796 int32_t my_deepest_node ;
797 if (TreeMem[start_node].children[q]==NO_CHILD)
799 int32_t depth=find_deepest_node(abs(TreeMem[start_node].children[q]), my_deepest_node) ;
802 deepest_node=my_deepest_node ;
813 template <
class Trie>
815 int32_t start_node, int32_t depth,
float64_t * weights)
821 if (start_node==NO_CHILD)
823 for (int32_t i=0; i<length; i++)
824 compact_nodes(i,1, weights) ;
832 TRIE_ASSERT_EVERYTHING(TreeMem[start_node].has_floats)
834 for (int32_t q=0; q<4; q++)
835 if (TreeMem[start_node].child_weights[q]!=0.0)
841 TRIE_ASSERT_EVERYTHING(!TreeMem[start_node].has_floats)
843 int32_t num_used = 0 ;
846 for (int32_t q=0; q<4; q++)
848 if (TreeMem[start_node].children[q]==NO_CHILD)
857 for (int32_t q=0; q<4; q++)
859 if (TreeMem[start_node].children[q]==NO_CHILD)
861 int32_t num=compact_nodes(abs(TreeMem[start_node].children[q]), depth+1, weights) ;
864 int32_t
node=get_node() ;
866 int32_t last_node=TreeMem[start_node].children[q] ;
869 ASSERT(weights[depth]!=0.0)
870 TreeMem[node].weight=TreeMem[last_node].weight/weights[depth] ;
873 TreeMem[node].weight=TreeMem[last_node].weight ;
875 #ifdef TRIE_CHECK_EVERYTHING
876 TreeMem[node].has_seq=true ;
878 memset(TreeMem[node].seq, TRIE_TERMINAL_CHARACTER, 16) ;
879 for (int32_t n=0; n<num; n++)
881 ASSERT(depth+n+1<=degree-1)
882 ASSERT(last_node!=NO_CHILD)
883 if (depth+n+1==degree-1)
885 TRIE_ASSERT_EVERYTHING(TreeMem[last_node].has_floats)
888 if (TreeMem[last_node].child_weights[k]!=0.0)
892 TreeMem[node].seq[n]=k ;
897 TRIE_ASSERT_EVERYTHING(!TreeMem[last_node].has_floats)
900 if (TreeMem[last_node].children[k]!=NO_CHILD)
904 TreeMem[node].seq[n]=k ;
905 last_node=TreeMem[last_node].children[k] ;
908 TreeMem[start_node].children[q]=-node ;
915 ret=compact_nodes(abs(TreeMem[start_node].children[q_used]), depth+1, weights) ;
922 template <
class Trie>
926 SG_DEBUG(
"checking nodes %i and %i\n", node, other_node)
927 if (fabs(TreeMem[node].weight-other.TreeMem[other_node].weight)>=1e-5)
929 SG_DEBUG(
"CTrie::compare: TreeMem[%i].weight=%f!=other.TreeMem[%i].weight=%f\n", node, TreeMem[node].weight, other_node,other.TreeMem[other_node].weight)
930 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
932 SG_DEBUG(
"============================================================\n")
933 other.display_node(other_node) ;
934 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
938 #ifdef TRIE_CHECK_EVERYTHING
939 if (TreeMem[node].has_seq!=other.TreeMem[other_node].has_seq)
941 SG_DEBUG(
"CTrie::compare: TreeMem[%i].has_seq=%i!=other.TreeMem[%i].has_seq=%i\n", node, TreeMem[node].has_seq, other_node,other.TreeMem[other_node].has_seq)
942 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
944 SG_DEBUG(
"============================================================\n")
945 other.display_node(other_node) ;
946 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
949 if (TreeMem[node].has_floats!=other.TreeMem[other_node].has_floats)
951 SG_DEBUG(
"CTrie::compare: TreeMem[%i].has_floats=%i!=other.TreeMem[%i].has_floats=%i\n", node, TreeMem[node].has_floats, other_node, other.TreeMem[other_node].has_floats)
954 if (other.TreeMem[other_node].has_floats)
956 for (int32_t q=0; q<4; q++)
957 if (fabs(TreeMem[node].child_weights[q]-other.TreeMem[other_node].child_weights[q])>1e-5)
959 SG_DEBUG(
"CTrie::compare: TreeMem[%i].child_weights[%i]=%e!=other.TreeMem[%i].child_weights[%i]=%e\n", node, q,TreeMem[node].child_weights[q], other_node,q,other.TreeMem[other_node].child_weights[q])
960 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
962 SG_DEBUG(
"============================================================\n")
963 other.display_node(other_node) ;
964 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
968 if (other.TreeMem[other_node].has_seq)
970 for (int32_t q=0; q<16; q++)
971 if ((TreeMem[node].seq[q]!=other.TreeMem[other_node].seq[q]) && ((TreeMem[node].seq[q]<4)||(other.TreeMem[other_node].seq[q]<4)))
973 SG_DEBUG(
"CTrie::compare: TreeMem[%i].seq[%i]=%i!=other.TreeMem[%i].seq[%i]=%i\n", node,q,TreeMem[node].seq[q], other_node,q,other.TreeMem[other_node].seq[q])
974 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
976 SG_DEBUG(
"============================================================\n")
977 other.display_node(other_node) ;
978 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
982 if (!other.TreeMem[other_node].has_seq && !other.TreeMem[other_node].has_floats)
984 for (int32_t q=0; q<4; q++)
986 if ((TreeMem[node].children[q]==NO_CHILD) && (other.TreeMem[other_node].children[q]==NO_CHILD))
988 if ((TreeMem[node].children[q]==NO_CHILD)!=(other.TreeMem[other_node].children[q]==NO_CHILD))
990 SG_DEBUG(
"CTrie::compare: TreeMem[%i].children[%i]=%i!=other.TreeMem[%i].children[%i]=%i\n", node,q,TreeMem[node].children[q], other_node,q,other.TreeMem[other_node].children[q])
991 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
993 SG_DEBUG(
"============================================================\n")
994 other.display_node(other_node) ;
995 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
998 if (!compare_traverse(abs(TreeMem[node].children[q]), other, abs(other.TreeMem[other_node].children[q])))
1009 template <
class Trie>
1013 for (int32_t i=0; i<length; i++)
1014 if (!compare_traverse(trees[i], other, other.trees[i]))
1017 SG_DEBUG(
"two tries at %i identical\n", i)
1022 template <
class Trie>
1024 int32_t
node, int32_t * trace, int32_t& trace_len)
const
1026 #ifdef TRIE_CHECK_EVERYTHING
1028 ASSERT((trace[trace_len-1]>=0) && (trace[trace_len-1]<TreeMemPtrMax))
1029 if (TreeMem[trace[trace_len-1]].has_seq)
1031 if (TreeMem[trace[trace_len-1]].has_floats)
1034 for (int32_t q=0; q<4; q++)
1036 if (TreeMem[trace[trace_len-1]].children[q]==NO_CHILD)
1038 int32_t tl=trace_len+1 ;
1039 if (TreeMem[trace[trace_len-1]].children[q]>=0)
1040 trace[trace_len]=TreeMem[trace[trace_len-1]].children[q] ;
1042 trace[trace_len]=-TreeMem[trace[trace_len-1]].children[q] ;
1044 if (trace[trace_len]==node)
1049 if (find_node(node, trace, tl))
1063 template <
class Trie>
1066 #ifdef TRIE_CHECK_EVERYTHING
1067 int32_t * trace=SG_MALLOC(int32_t, 2*degree);
1068 int32_t trace_len=-1 ;
1069 bool found = false ;
1071 for (tree=0; tree<length; tree++)
1073 trace[0]=trees[tree] ;
1075 found=find_node(node, trace, trace_len) ;
1080 SG_PRINT(
"position %i trace: ", tree)
1082 for (int32_t i=0; i<trace_len-1; i++)
1085 for (int32_t q=0; q<4; q++)
1086 if (abs(TreeMem[trace[i]].children[q])==trace[i+1])
1092 char acgt[5]=
"ACGT" ;
1095 SG_PRINT(
"\nnode=%i\nweight=%f\nhas_seq=%i\nhas_floats=%i\n", node, TreeMem[node].weight, TreeMem[node].has_seq, TreeMem[node].has_floats)
1096 if (TreeMem[node].has_floats)
1098 for (int32_t q=0; q<4; q++)
1099 SG_PRINT(
"child_weighs[%i] = %f\n", q, TreeMem[node].child_weights[q])
1101 if (TreeMem[node].has_seq)
1103 for (int32_t q=0; q<16; q++)
1104 SG_PRINT(
"seq[%i] = %i\n", q, TreeMem[node].seq[q])
1106 if (!TreeMem[node].has_seq && !TreeMem[node].has_floats)
1108 for (int32_t q=0; q<4; q++)
1110 if (TreeMem[node].children[q]!=NO_CHILD)
1112 SG_PRINT(
"children[%i] = %i -> \n", q, TreeMem[node].children[q])
1113 display_node(abs(TreeMem[node].children[q])) ;
1116 SG_PRINT(
"children[%i] = NO_CHILD -| \n", q, TreeMem[node].children[q])
1140 for (int32_t i=0; i<length; i++)
1141 trees[i] = NO_CHILD;
1152 delete_trees(get_use_compact_terminal_nodes());
1157 int32_t len,
bool p_use_compact_terminal_nodes)
1161 trees=SG_MALLOC(int32_t, len);
1163 for (int32_t i=0; i<len; i++)
1164 trees[i]=get_node(degree==1);
1167 use_compact_terminal_nodes=p_use_compact_terminal_nodes ;
1172 bool p_use_compact_terminal_nodes)
1178 for (int32_t i=0; i<length; i++)
1179 trees[i]=get_node(degree==1);
1181 use_compact_terminal_nodes=p_use_compact_terminal_nodes ;
1184 template <
class Trie>
1191 TRIE_ASSERT(tree>=0)
1193 if (depth==degree-2)
1195 ret+=(TreeMem[tree].weight) ;
1197 for (int32_t k=0; k<4; k++)
1198 ret+=(TreeMem[tree].child_weights[k]) ;
1203 ret+=(TreeMem[tree].weight) ;
1205 for (int32_t i=0; i<4; i++)
1206 if (TreeMem[tree].children[i]!=NO_CHILD)
1207 ret += compute_abs_weights_tree(TreeMem[tree].children[i], depth+1) ;
1213 template <
class Trie>
1217 for (int32_t i=0; i<length*4; i++)
1221 for (int32_t i=0; i<length; i++)
1223 TRIE_ASSERT(trees[i]!=NO_CHILD)
1224 for (int32_t k=0; k<4; k++)
1226 sum[i*4+k]=compute_abs_weights_tree(TreeMem[trees[i]].children[k], 0) ;
1233 template <
class Trie>
1235 int32_t tree, int32_t i,
float64_t alpha,
1236 int32_t *vec, int32_t len_rem,
1237 int32_t degree_rec, int32_t mismatch_rec,
1238 int32_t max_mismatch,
float64_t * weights)
1242 TRIE_ASSERT(tree!=NO_CHILD)
1244 if ((len_rem<=0) || (mismatch_rec>max_mismatch) || (degree_rec>degree))
1246 const int32_t other[4][3] = { {1,2,3},{0,2,3},{0,1,3},{0,1,2} } ;
1248 int32_t subtree = NO_CHILD ;
1250 if (degree_rec==degree-1)
1252 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1253 if (weights_in_tree)
1254 TreeMem[tree].child_weights[vec[0]] += alpha*weights[degree_rec+degree*mismatch_rec];
1256 if (weights[degree_rec]!=0.0)
1257 TreeMem[tree].child_weights[vec[0]] += alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec];
1258 if (mismatch_rec+1<=max_mismatch)
1259 for (int32_t o=0; o<3; o++)
1261 if (weights_in_tree)
1262 TreeMem[tree].child_weights[other[vec[0]][o]] += alpha*weights[degree_rec+degree*(mismatch_rec+1)];
1264 if (weights[degree_rec]!=0.0)
1265 TreeMem[tree].child_weights[other[vec[0]][o]] += alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec];
1271 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1272 if (TreeMem[tree].children[vec[0]]!=NO_CHILD)
1274 subtree=TreeMem[tree].children[vec[0]] ;
1275 if (weights_in_tree)
1276 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*mismatch_rec];
1278 if (weights[degree_rec]!=0.0)
1279 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec];
1283 int32_t tmp = get_node(degree_rec==degree-2);
1285 TreeMem[tree].children[vec[0]]=tmp ;
1287 #ifdef TRIE_CHECK_EVERYTHING
1288 if (degree_rec==degree-2)
1289 TreeMem[subtree].has_floats=true ;
1291 if (weights_in_tree)
1292 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*mismatch_rec] ;
1294 if (weights[degree_rec]!=0.0)
1295 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec] ;
1297 TreeMem[subtree].weight = 0.0 ;
1299 add_example_to_tree_mismatch_recursion(subtree, i, alpha,
1301 degree_rec+1, mismatch_rec, max_mismatch, weights) ;
1303 if (mismatch_rec+1<=max_mismatch)
1305 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1306 for (int32_t o=0; o<3; o++)
1308 int32_t ot = other[vec[0]][o] ;
1309 if (TreeMem[tree].children[ot]!=NO_CHILD)
1311 subtree=TreeMem[tree].children[ot] ;
1312 if (weights_in_tree)
1313 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*(mismatch_rec+1)];
1315 if (weights[degree_rec]!=0.0)
1316 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec];
1320 int32_t tmp = get_node(degree_rec==degree-2);
1322 TreeMem[tree].children[ot]=tmp ;
1324 #ifdef TRIE_CHECK_EVERYTHING
1325 if (degree_rec==degree-2)
1326 TreeMem[subtree].has_floats=true ;
1329 if (weights_in_tree)
1330 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*(mismatch_rec+1)] ;
1332 if (weights[degree_rec]!=0.0)
1333 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec] ;
1335 TreeMem[subtree].weight = 0.0 ;
1338 add_example_to_tree_mismatch_recursion(subtree, i, alpha,
1340 degree_rec+1, mismatch_rec+1, max_mismatch, weights) ;
1346 template <
class Trie>
1348 int32_t tree, int32_t i, int32_t j,
float64_t weight, int32_t d,
1349 int32_t max_degree, int32_t num_feat, int32_t num_sym, int32_t sym_offset,
1360 for (int32_t k=0; k<num_sym; k++)
1362 if (TreeMem[tree].children[k]!=NO_CHILD)
1364 int32_t child=TreeMem[tree].children[k];
1367 compute_scoring_helper(child, i, j+1, weight+decay*TreeMem[child].weight, d+1, max_degree, num_feat, num_sym, sym_offset, num_sym*offs+k, result);
1369 result[sym_offset*(i+j-max_degree+1)+num_sym*offs+k] += weight+decay*TreeMem[child].weight;
1373 compute_scoring_helper(child, i, j+1, 0.0, 0, max_degree, num_feat, num_sym, sym_offset, offs, result);
1377 else if (j==degree-1)
1379 for (int32_t k=0; k<num_sym; k++)
1382 if (d<max_degree-1 && i<num_feat-1)
1383 compute_scoring_helper(trees[i+1], i+1, 0, weight+decay*TreeMem[tree].child_weights[k], d+1, max_degree, num_feat, num_sym, sym_offset, num_sym*offs+k, result);
1385 result[sym_offset*(i+j-max_degree+1)+num_sym*offs+k] += weight+decay*TreeMem[tree].child_weights[k];
1391 template <
class Trie>
1393 int32_t tree,
const int32_t p,
struct TreeParseInfo info,
1394 const int32_t depth, int32_t*
const x,
const int32_t k)
1396 const int32_t num_sym = info.num_sym;
1397 const int32_t y0 = info.y0;
1398 const int32_t y1 = (k==0) ? 0 : y0 - ( (depth<k) ? 0 : info.nofsKmers[k-1] * x[depth-k] );
1409 for( sym=0; sym<num_sym; ++sym ) {
1410 const int32_t childNum = TreeMem[tree].children[ sym ];
1411 if( childNum != NO_CHILD ) {
1412 int32_t child = childNum ;
1414 info.substrs[depth+1] = y0 + sym;
1415 info.y0 = (k==0) ? 0 : (y1+sym)*num_sym;
1417 count( TreeMem[child].weight, depth, info, p, x, k );
1418 traverse( child, p, info, depth+1, x, k );
1423 else if( depth == degree-1 )
1425 for( sym=0; sym<num_sym; ++sym ) {
1426 const float64_t w = TreeMem[tree].child_weights[ sym ];
1429 info.substrs[depth+1] = y0 + sym;
1430 info.y0 = (k==0) ? 0 : (y1+sym)*num_sym;
1432 count( w, depth, info, p, x, k );
1441 template <
class Trie>
1443 const float64_t w,
const int32_t depth,
const struct TreeParseInfo info,
1444 const int32_t p, int32_t* x,
const int32_t k)
1453 const int32_t nofKmers = info.nofsKmers[k];
1454 const float64_t margWeight = w * info.margFactors[ depth-k ];
1455 const int32_t m_a = depth - k + 1;
1456 const int32_t m_b = info.num_feat - p;
1457 const int32_t m = ( m_a < m_b ) ? m_a : m_b;
1459 const int32_t offset0 = nofKmers * p;
1463 for( i = 0; i < m; ++i ) {
1464 const int32_t y = info.substrs[i+k+1];
1465 info.C_k[ y + offset ] += margWeight;
1470 const int32_t offsR = info.substrs[k+1] + offset0;
1471 info.R_k[offsR] += margWeight;
1473 if( p+depth-k < info.num_feat ) {
1474 const int32_t offsL = info.substrs[depth+1] + nofKmers * (p+depth-k);
1475 info.L_k[offsL] += margWeight;
1495 template <
class Trie>
1497 int32_t i, int32_t seq_offset, int32_t * vec,
float32_t alpha,
1498 float64_t *weights,
bool degree_times_position_weights)
1500 int32_t tree = trees[i] ;
1503 int32_t max_depth = 0 ;
1505 if (degree_times_position_weights)
1506 weights_column = &weights[(i+seq_offset)*degree] ;
1508 weights_column = weights ;
1510 if (weights_in_tree)
1512 for (int32_t j=0; (j<degree) && (i+j<length); j++)
1520 for (int32_t j=0; (j<max_depth) && (i+j+seq_offset<length); j++)
1522 TRIE_ASSERT((vec[i+j+seq_offset]>=0) && (vec[i+j+seq_offset]<4))
1523 if ((j<degree-1) && (TreeMem[tree].children[vec[i+j+seq_offset]]!=NO_CHILD))
1525 if (TreeMem[tree].children[vec[i+j+seq_offset]]<0)
1528 TRIE_ASSERT(j >= degree-16)
1530 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1531 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1532 int32_t
node = - TreeMem[tree].
children[vec[i+j+seq_offset]] ;
1534 TRIE_ASSERT((node>=0) && (node<=TreeMemPtrMax))
1535 TRIE_ASSERT_EVERYTHING(TreeMem[node].has_seq)
1536 TRIE_ASSERT_EVERYTHING(!TreeMem[node].has_floats)
1539 int32_t mismatch_pos = -1 ;
1542 for (k=0; (j+k<max_depth) && (i+j+seq_offset+k<length); k++)
1544 TRIE_ASSERT((vec[i+j+seq_offset+k]>=0) && (vec[i+j+seq_offset+k]<4))
1546 if ((TreeMem[node].seq[k]>=4) && (TreeMem[node].seq[k]!=TRIE_TERMINAL_CHARACTER))
1547 fprintf(stderr,
"+++i=%i j=%i seq[%i]=%i\n", i, j, k, TreeMem[node].seq[k]) ;
1548 TRIE_ASSERT((TreeMem[node].seq[k]<4) || (TreeMem[node].seq[k]==TRIE_TERMINAL_CHARACTER))
1550 if (TreeMem[node].seq[k]!=vec[i+j+seq_offset+k])
1560 if (mismatch_pos==-1)
1562 TreeMem[node].weight+=alpha ;
1570 int32_t last_node=tree ;
1574 for (k=0; k<mismatch_pos; k++)
1576 TRIE_ASSERT((vec[i+j+seq_offset+k]>=0) && (vec[i+j+seq_offset+k]<4))
1577 TRIE_ASSERT(vec[i+j+seq_offset+k]==TreeMem[node].seq[k])
1579 int32_t tmp=get_node();
1580 TreeMem[last_node].children[vec[i+j+seq_offset+k]]=tmp ;
1582 if (weights_in_tree)
1583 TreeMem[last_node].weight = (TreeMem[node].weight+alpha)*weights_column[j+k] ;
1585 TreeMem[last_node].weight = (TreeMem[node].weight+alpha) ;
1586 TRIE_ASSERT(j+k!=degree-1)
1588 if ((TreeMem[node].seq[mismatch_pos]>=4) && (TreeMem[node].seq[mismatch_pos]!=TRIE_TERMINAL_CHARACTER))
1589 fprintf(stderr,
"**i=%i j=%i seq[%i]=%i\n", i, j, k, TreeMem[node].seq[mismatch_pos]) ;
1590 ASSERT((TreeMem[node].seq[mismatch_pos]<4) || (TreeMem[node].seq[mismatch_pos]==TRIE_TERMINAL_CHARACTER))
1591 TRIE_ASSERT(vec[i+j+seq_offset+mismatch_pos]!=TreeMem[node].seq[mismatch_pos])
1598 for (int32_t q=0; q<4; q++)
1599 TreeMem[last_node].child_weights[q]=0.0 ;
1600 if (weights_in_tree)
1602 if (TreeMem[node].seq[mismatch_pos]<4)
1603 TreeMem[last_node].child_weights[TreeMem[node].seq[mismatch_pos]]+=TreeMem[node].weight*weights_column[degree-1] ;
1604 TreeMem[last_node].child_weights[vec[i+j+seq_offset+k]] += alpha*weights_column[degree-1] ;
1608 if (TreeMem[node].seq[mismatch_pos]<4)
1609 TreeMem[last_node].child_weights[TreeMem[node].seq[mismatch_pos]]=TreeMem[node].weight ;
1610 TreeMem[last_node].child_weights[vec[i+j+seq_offset+k]] = alpha ;
1613 #ifdef TRIE_CHECK_EVERYTHING
1614 TreeMem[last_node].has_floats=true ;
1620 if (TreeMem[node].seq[mismatch_pos]<4)
1622 TreeMem[last_node].children[TreeMem[node].seq[mismatch_pos]] = -node ;
1625 for (int32_t q=0; q<16; q++)
1627 if ((j+q+mismatch_pos<degree) && (i+j+seq_offset+q+mismatch_pos<length))
1628 TreeMem[node].seq[q] = TreeMem[node].seq[q+mismatch_pos] ;
1630 TreeMem[node].seq[q] = TRIE_TERMINAL_CHARACTER ;
1632 #ifdef TRIE_CHECK_EVERYTHING
1633 TreeMem[node].has_seq=true ;
1638 TRIE_ASSERT((vec[i+j+seq_offset+mismatch_pos]>=0) && (vec[i+j+seq_offset+mismatch_pos]<4))
1639 int32_t tmp = get_node() ;
1640 TreeMem[last_node].children[vec[i+j+seq_offset+mismatch_pos]] = -tmp ;
1643 TreeMem[last_node].weight = alpha ;
1644 #ifdef TRIE_CHECK_EVERYTHING
1645 TreeMem[last_node].has_seq = true ;
1647 memset(TreeMem[last_node].seq, TRIE_TERMINAL_CHARACTER, 16) ;
1648 for (int32_t q=0; (j+q+mismatch_pos<degree) && (i+j+seq_offset+q+mismatch_pos<length); q++)
1649 TreeMem[last_node].seq[q] = vec[i+j+seq_offset+mismatch_pos+q] ;
1656 tree=TreeMem[tree].children[vec[i+j+seq_offset]] ;
1657 TRIE_ASSERT((tree>=0) && (tree<TreeMemPtrMax))
1658 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1659 if (weights_in_tree)
1660 TreeMem[tree].weight += alpha*weights_column[j];
1662 TreeMem[tree].weight += alpha ;
1665 else if (j==degree-1)
1668 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1669 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1670 if (weights_in_tree)
1671 TreeMem[tree].child_weights[vec[i+j+seq_offset]] += alpha*weights_column[j] ;
1673 TreeMem[tree].child_weights[vec[i+j+seq_offset]] += alpha;
1679 bool use_seq = use_compact_terminal_nodes && (j>degree-16) ;
1680 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1681 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1683 int32_t tmp = get_node((j==degree-2) && (!use_seq));
1685 TreeMem[tree].children[vec[i+j+seq_offset]] = -tmp ;
1687 TreeMem[tree].children[vec[i+j+seq_offset]] = tmp ;
1690 TRIE_ASSERT((tree>=0) && (tree<TreeMemPtrMax))
1691 #ifdef TRIE_CHECK_EVERYTHING
1692 TreeMem[tree].has_seq = use_seq ;
1696 TreeMem[tree].weight = alpha ;
1698 memset(TreeMem[tree].seq, TRIE_TERMINAL_CHARACTER, 16) ;
1699 for (int32_t q=0; (j+q<degree) && (i+j+seq_offset+q<length); q++)
1702 TreeMem[tree].seq[q]=vec[i+j+seq_offset+q] ;
1708 if (weights_in_tree)
1709 TreeMem[tree].weight = alpha*weights_column[j] ;
1711 TreeMem[tree].weight = alpha ;
1712 #ifdef TRIE_CHECK_EVERYTHING
1714 TreeMem[tree].has_floats = true ;
1721 template <
class Trie>
1723 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
1725 bool degree_times_position_weights)
1727 int32_t tree = trees[tree_pos] ;
1729 if ((position_weights!=NULL) && (position_weights[weight_pos]==0))
1733 if (degree_times_position_weights)
1734 weights_column=&weights[weight_pos*degree] ;
1736 weights_column=weights ;
1739 for (int32_t j=0; seq_pos+j < len; j++)
1741 TRIE_ASSERT((vec[seq_pos+j]<4) && (vec[seq_pos+j]>=0))
1743 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1745 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1746 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1748 tree = - TreeMem[tree].children[vec[seq_pos+j]];
1749 TRIE_ASSERT(tree>=0)
1750 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1752 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1754 TRIE_ASSERT((vec[seq_pos+j+k]<4) && (vec[seq_pos+j+k]>=0))
1755 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1757 this_weight += weights_column[j+k] ;
1759 sum += TreeMem[tree].weight * this_weight ;
1764 tree=TreeMem[tree].children[vec[seq_pos+j]];
1765 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1766 if (weights_in_tree)
1767 sum += TreeMem[tree].weight ;
1769 sum += TreeMem[tree].weight * weights_column[j] ;
1774 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1777 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1778 if (weights_in_tree)
1779 sum += TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1781 sum += TreeMem[tree].child_weights[vec[seq_pos+j]] * weights_column[j] ;
1784 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1790 if (position_weights!=NULL)
1791 return sum*position_weights[weight_pos] ;
1796 template <
class Trie>
1798 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
1800 int32_t mkl_stepsize,
float64_t * weights,
1801 bool degree_times_position_weights)
1803 int32_t tree = trees[tree_pos] ;
1807 if (position_weights!=NULL)
1809 factor *= position_weights[weight_pos] ;
1812 if (!degree_times_position_weights)
1814 for (int32_t j=0; seq_pos+j<len; j++)
1816 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1818 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1820 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1821 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1822 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1824 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1826 if (weights_in_tree)
1827 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1829 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k] ;
1835 tree=TreeMem[tree].children[vec[seq_pos+j]];
1836 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1837 if (weights_in_tree)
1838 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1840 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j] ;
1845 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1848 if (weights_in_tree)
1849 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1851 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j] ;
1858 for (int32_t j=0; seq_pos+j<len; j++)
1860 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1862 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1864 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1865 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1866 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1868 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1870 if (weights_in_tree)
1871 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1873 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k+weight_pos*degree] ;
1879 tree=TreeMem[tree].children[vec[seq_pos+j]];
1880 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1881 if (weights_in_tree)
1882 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1884 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+weight_pos*degree] ;
1889 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1892 if (weights_in_tree)
1893 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1895 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j+weight_pos*degree] ;
1902 else if (!degree_times_position_weights)
1904 for (int32_t j=0; seq_pos+j<len; j++)
1906 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1908 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1910 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1911 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1912 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1914 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1916 if (weights_in_tree)
1917 LevelContrib[(j+k)/mkl_stepsize] += factor*TreeMem[tree].weight ;
1919 LevelContrib[(j+k)/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k] ;
1925 tree=TreeMem[tree].children[vec[seq_pos+j]];
1926 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1927 if (weights_in_tree)
1928 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].weight ;
1930 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j] ;
1935 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1938 if (weights_in_tree)
1939 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1941 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j] ;
1967 for (int32_t j=0; seq_pos+j<len; j++)
1969 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1971 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1973 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1974 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1975 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1977 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1979 if (weights_in_tree)
1980 LevelContrib[(j+k+degree*weight_pos)/mkl_stepsize] += factor*TreeMem[tree].weight ;
1982 LevelContrib[(j+k+degree*weight_pos)/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k+weight_pos*degree] ;
1988 tree=TreeMem[tree].children[vec[seq_pos+j]];
1989 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1990 if (weights_in_tree)
1991 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].weight ;
1993 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].weight * weights[j+weight_pos*degree] ;
1998 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
2001 if (weights_in_tree)
2002 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].child_weights[vec[seq_pos+j]] ;
2004 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].child_weights[vec[seq_pos+j]] * weights[j+weight_pos*degree] ;
2012 template <
class Trie>
2014 Trie* tree, int32_t depth, uint64_t seq,
float64_t value,
2019 if (weights_in_tree || depth==0)
2020 value+=tree->weight;
2023 w=weights[degree-1];
2024 value+=weights[depth-1]*tree->weight;
2027 if (degree-1==depth)
2029 for (int32_t sym=0; sym<4; sym++)
2034 ConsensusEntry entry;
2036 entry.score=value+v;
2037 entry.string=seq | ((uint64_t) sym) << (2*(degree-depth-1));
2045 for (int32_t sym=0; sym<4; sym++)
2047 uint64_t str=seq | ((uint64_t) sym) << (2*(degree-depth-1));
2048 if (tree->children[sym] != NO_CHILD)
2049 fill_backtracking_table_recursion(&TreeMem[tree->children[sym]], depth+1, str, value, table, weights);
2054 template <
class Trie>
2056 int32_t pos, uint64_t seq, int32_t deg,
float64_t* weights)
2062 for (int32_t i=pos; i<pos+deg && i<length; i++)
2065 Trie* tree = &TreeMem[trees[i]];
2067 for (int32_t d=0; d<deg-i+pos; d++)
2071 int32_t sym = (int32_t) (seq >> (2*(deg-1-d-i+pos)) & 3);
2074 if (!weights_in_tree)
2077 ASSERT(tree->children[sym] != NO_CHILD)
2078 tree=&TreeMem[tree->children[sym]];
2079 result+=w*tree->weight;
2086 template <
class Trie>
2091 ASSERT(pos>=0 && pos<length)
2092 ASSERT(!use_compact_terminal_nodes)
2094 Trie* t = &TreeMem[trees[pos]];
2096 fill_backtracking_table_recursion(t, 0, (uint64_t) 0, 0.0, cur, weights);
2102 for (int32_t i=0; i<num_cur; i++)
2105 entry.score+=get_cumulative_score(pos+1, entry.string, degree-1, weights);
2118 for (int32_t i=0; i<num_cur; i++)
2121 uint64_t str_cur= cur->
get_element(i).string >> 2;
2127 for (int32_t j=0; j<num_prev; j++)
2131 ((((uint64_t)0)-1) ^ (((uint64_t) 3) << (2*(degree-1))));
2132 uint64_t str_prev= mask & prev->
get_element(j).string;
2135 if (str_cur == str_prev)
2138 if (bt==-1 || sc>max_score)
2149 ConsensusEntry entry;
2151 entry.score=max_score;
2159 #endif // _TRIE_H___
void delete_trees(bool p_use_compact_terminal_nodes=true)
T get_element(int32_t index) const
void POIMs_add_SLR(float64_t *const *const poims, const int32_t K, const int32_t debug)
float64_t * position_weights
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)
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)
int32_t compact_nodes(int32_t start_node, int32_t depth, float64_t *weights)
bool compare_traverse(int32_t node, const CTrie &other, int32_t other_node)
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)
bool append_element(T element)
Template class Trie implements a suffix trie, i.e. a tree in which all suffixes up to a certain lengt...
void POIMs_extract_W(float64_t *const *const W, const int32_t K)
void traverse(int32_t tree, const int32_t p, struct TreeParseInfo info, const int32_t depth, int32_t *const x, const int32_t k)
int32_t get_node(bool last_node=false)
const CTrie & operator=(const CTrie &to_copy)
float64_t get_cumulative_score(int32_t pos, uint64_t seq, int32_t deg, float64_t *weights)
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)
int32_t get_num_elements() const
bool find_node(int32_t node, int32_t *trace, int32_t &trace_len) const
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 POIMs_precalc_SLR(const float64_t *const distrib)
void fill_backtracking_table(int32_t pos, DynArray< ConsensusEntry > *prev, DynArray< ConsensusEntry > *cur, bool cumulative, float64_t *weights)
bool compare(const CTrie &other)
void set_position_weights(float64_t *p_position_weights)
Class SGObject is the base class of all shogun objects.
void set_use_compact_terminal_nodes(bool p_use_compact_terminal_nodes)
#define IGNORE_IN_CLASSLIST
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 Dynamic array class that creates an array that can be used like a list or an array...
void create(int32_t len, bool p_use_compact_terminal_nodes=true)
int32_t get_num_used_nodes()
bool set_element(T element, int32_t index)
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)
virtual const char * get_name() const
void display_node(int32_t node) const
bool get_weights_in_tree()
all of classes and functions are contained in the shogun namespace
float64_t * compute_abs_weights(int32_t &len)
void set_weights_in_tree(bool weights_in_tree_)
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)
bool use_compact_terminal_nodes
int32_t find_deepest_node(int32_t start_node, int32_t &deepest_node) const
bool get_use_compact_terminal_nodes()
void fill_backtracking_table_recursion(Trie *tree, int32_t depth, uint64_t seq, float64_t value, DynArray< ConsensusEntry > *table, float64_t *weights)
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 set_degree(int32_t d)
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 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)