26 #ifndef DOXYGEN_SHOULD_SKIP_THIS
29 #define NO_CHILD ((int32_t)-1073741824)
31 #define WEIGHTS_IN_TRIE
34 #ifdef TRIE_CHECK_EVERYTHING
35 #define TRIE_ASSERT_EVERYTHING(x) ASSERT(x)
37 #define TRIE_ASSERT_EVERYTHING(x)
41 #define TRIE_ASSERT(x)
43 #define TRIE_TERMINAL_CHARACTER 7
61 #ifdef TRIE_CHECK_EVERYTHING
90 #ifdef TRIE_CHECK_EVERYTHING
108 struct TreeParseInfo {
135 #endif // DOXYGEN_SHOULD_SKIP_THIS
139 #define IGNORE_IN_CLASSLIST
170 CTrie(int32_t d,
bool p_use_compact_terminal_nodes=
true);
187 int32_t
node,
const CTrie & other, int32_t other_node);
202 bool find_node(int32_t node, int32_t * trace, int32_t &trace_len)
const;
211 int32_t start_node, int32_t &deepest_node)
const;
234 void create(int32_t len,
bool p_use_compact_terminal_nodes=
true);
241 void delete_trees(
bool p_use_compact_terminal_nodes=
true);
254 int32_t i, int32_t seq_offset, int32_t* vec,
float32_t alpha,
255 float64_t *weights,
bool degree_times_position_weights);
285 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
287 bool degree_times_position_weights) ;
304 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
306 int32_t mkl_stepsize,
float64_t * weights,
307 bool degree_times_position_weights);
324 int32_t tree, int32_t i, int32_t j,
float64_t weight, int32_t d,
325 int32_t max_degree, int32_t num_feat, int32_t num_sym,
326 int32_t sym_offset, int32_t offs,
float64_t* result);
341 int32_t tree, int32_t i,
float64_t alpha, int32_t *vec,
342 int32_t len_rem, int32_t degree_rec, int32_t mismatch_rec,
343 int32_t max_mismatch,
float64_t * weights);
355 int32_t tree,
const int32_t p,
struct TreeParseInfo info,
356 const int32_t depth, int32_t*
const x,
const int32_t k);
369 const struct TreeParseInfo info,
const int32_t p, int32_t* x,
389 int32_t pos, uint64_t seq, int32_t deg,
float64_t* weights);
401 Trie* tree, int32_t depth, uint64_t seq,
float64_t value,
402 DynArray<ConsensusEntry>* table,
float64_t* weights);
413 int32_t pos, DynArray<ConsensusEntry>* prev,
414 DynArray<ConsensusEntry>* cur,
bool cumulative,
440 const int32_t parentIdx,
const int32_t sym,
const int32_t depth,
450 float64_t*
const*
const poims,
const int32_t K,
451 const int32_t debug);
468 bool p_use_compact_terminal_nodes)
502 for (int32_t q=0; q<4; q++)
503 TreeMem[ret].child_weights[q]=0.0;
507 for (int32_t q=0; q<4; q++)
508 TreeMem[ret].children[q]=NO_CHILD;
510 #ifdef TRIE_CHECK_EVERYTHING
512 TreeMem[ret].has_floats=false ;
523 SG_DEBUG(
"Extending TreeMem from %i to %i elements\n",
526 TreeMemPtrMax = (int32_t) ((
float64_t)TreeMemPtrMax*1.2);
558 const int32_t nodeIdx,
const int32_t depth,
const int32_t offset,
559 const int32_t y0,
float64_t*
const*
const W,
const int32_t K);
574 const float64_t*
const distrib,
const int32_t i,
575 const int32_t nodeIdx, int32_t left_tries_idx[4],
576 const int32_t depth, int32_t
const lastSym,
float64_t* S,
591 const float64_t*
const distrib,
const int32_t i,
592 const int32_t nodeIdx, int32_t left_tries_idx[4],
606 const int32_t nodeIdx,
const int32_t depth,
const int32_t i,
607 const int32_t y0,
float64_t*
const*
const poims,
const int32_t K,
608 const int32_t debug);
624 float64_t*
const*
const poims,
const int32_t K,
const int32_t k,
625 const int32_t i,
const int32_t y,
const float64_t valW,
627 const int32_t debug);
630 virtual const char*
get_name()
const {
return "Trie"; }
662 template <
class Trie>
664 :
CSGObject(), degree(0), position_weights(NULL),
665 use_compact_terminal_nodes(false),
666 weights_in_tree(true)
679 template <
class Trie>
681 :
CSGObject(), degree(d), position_weights(NULL),
682 use_compact_terminal_nodes(p_use_compact_terminal_nodes),
683 weights_in_tree(true)
695 template <
class Trie>
697 :
CSGObject(to_copy), degree(to_copy.degree), position_weights(NULL),
698 use_compact_terminal_nodes(to_copy.use_compact_terminal_nodes)
700 if (to_copy.position_weights!=NULL)
717 for (int32_t i=0; i<
length; i++)
718 trees[i]=to_copy.trees[i];
723 template <
class Trie>
726 degree=to_copy.degree ;
727 use_compact_terminal_nodes=to_copy.use_compact_terminal_nodes ;
729 SG_FREE(position_weights);
730 position_weights=NULL ;
731 if (to_copy.position_weights!=NULL)
733 position_weights=to_copy.position_weights ;
739 position_weights=NULL ;
741 TreeMemPtrMax=to_copy.TreeMemPtrMax ;
742 TreeMemPtr=to_copy.TreeMemPtr ;
744 TreeMem = SG_MALLOC(Trie, TreeMemPtrMax);
745 memcpy(TreeMem, to_copy.TreeMem, TreeMemPtrMax*
sizeof(Trie)) ;
747 length = to_copy.length ;
750 trees=SG_MALLOC(int32_t, length);
751 for (int32_t i=0; i<length; i++)
752 trees[i]=to_copy.trees[i] ;
757 template <
class Trie>
759 int32_t start_node, int32_t& deepest_node)
const
761 #ifdef TRIE_CHECK_EVERYTHING
763 SG_DEBUG(
"start_node=%i\n", start_node)
765 if (start_node==NO_CHILD)
767 for (int32_t i=0; i<length; i++)
769 int32_t my_deepest_node ;
770 int32_t depth=find_deepest_node(i, my_deepest_node) ;
771 SG_DEBUG(
"start_node %i depth=%i\n", i, depth)
774 deepest_node=my_deepest_node ;
781 if (TreeMem[start_node].has_seq)
783 for (int32_t q=0; q<16; q++)
784 if (TreeMem[start_node].seq[q]!=TRIE_TERMINAL_CHARACTER)
786 deepest_node=start_node ;
789 if (TreeMem[start_node].has_floats)
791 deepest_node=start_node ;
795 for (int32_t q=0; q<4; q++)
797 int32_t my_deepest_node ;
798 if (TreeMem[start_node].children[q]==NO_CHILD)
800 int32_t depth=find_deepest_node(abs(TreeMem[start_node].children[q]), my_deepest_node) ;
803 deepest_node=my_deepest_node ;
814 template <
class Trie>
816 int32_t start_node, int32_t depth,
float64_t * weights)
822 if (start_node==NO_CHILD)
824 for (int32_t i=0; i<length; i++)
825 compact_nodes(i,1, weights) ;
833 TRIE_ASSERT_EVERYTHING(TreeMem[start_node].has_floats)
835 for (int32_t q=0; q<4; q++)
836 if (TreeMem[start_node].child_weights[q]!=0.0)
842 TRIE_ASSERT_EVERYTHING(!TreeMem[start_node].has_floats)
844 int32_t num_used = 0 ;
847 for (int32_t q=0; q<4; q++)
849 if (TreeMem[start_node].children[q]==NO_CHILD)
858 for (int32_t q=0; q<4; q++)
860 if (TreeMem[start_node].children[q]==NO_CHILD)
862 int32_t num=compact_nodes(abs(TreeMem[start_node].children[q]), depth+1, weights) ;
865 int32_t
node=get_node() ;
867 int32_t last_node=TreeMem[start_node].children[q] ;
870 ASSERT(weights[depth]!=0.0)
871 TreeMem[node].weight=TreeMem[last_node].weight/weights[depth] ;
874 TreeMem[node].weight=TreeMem[last_node].weight ;
876 #ifdef TRIE_CHECK_EVERYTHING
877 TreeMem[node].has_seq=true ;
879 memset(TreeMem[node].seq, TRIE_TERMINAL_CHARACTER, 16) ;
880 for (int32_t n=0; n<num; n++)
882 ASSERT(depth+n+1<=degree-1)
883 ASSERT(last_node!=NO_CHILD)
884 if (depth+n+1==degree-1)
886 TRIE_ASSERT_EVERYTHING(TreeMem[last_node].has_floats)
889 if (TreeMem[last_node].child_weights[k]!=0.0)
893 TreeMem[node].seq[n]=k ;
898 TRIE_ASSERT_EVERYTHING(!TreeMem[last_node].has_floats)
901 if (TreeMem[last_node].children[k]!=NO_CHILD)
905 TreeMem[node].seq[n]=k ;
906 last_node=TreeMem[last_node].children[k] ;
909 TreeMem[start_node].children[q]=-node ;
916 ret=compact_nodes(abs(TreeMem[start_node].children[q_used]), depth+1, weights) ;
923 template <
class Trie>
927 SG_DEBUG(
"checking nodes %i and %i\n", node, other_node)
928 if (fabs(TreeMem[node].weight-other.TreeMem[other_node].weight)>=1e-5)
930 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)
931 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
933 SG_DEBUG(
"============================================================\n")
934 other.display_node(other_node) ;
935 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
939 #ifdef TRIE_CHECK_EVERYTHING
940 if (TreeMem[node].has_seq!=other.TreeMem[other_node].has_seq)
942 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)
943 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
945 SG_DEBUG(
"============================================================\n")
946 other.display_node(other_node) ;
947 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
950 if (TreeMem[node].has_floats!=other.TreeMem[other_node].has_floats)
952 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)
955 if (other.TreeMem[other_node].has_floats)
957 for (int32_t q=0; q<4; q++)
958 if (fabs(TreeMem[node].child_weights[q]-other.TreeMem[other_node].child_weights[q])>1e-5)
960 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])
961 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
963 SG_DEBUG(
"============================================================\n")
964 other.display_node(other_node) ;
965 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
969 if (other.TreeMem[other_node].has_seq)
971 for (int32_t q=0; q<16; q++)
972 if ((TreeMem[node].seq[q]!=other.TreeMem[other_node].seq[q]) && ((TreeMem[node].seq[q]<4)||(other.TreeMem[other_node].seq[q]<4)))
974 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])
975 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
977 SG_DEBUG(
"============================================================\n")
978 other.display_node(other_node) ;
979 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
983 if (!other.TreeMem[other_node].has_seq && !other.TreeMem[other_node].has_floats)
985 for (int32_t q=0; q<4; q++)
987 if ((TreeMem[node].children[q]==NO_CHILD) && (other.TreeMem[other_node].children[q]==NO_CHILD))
989 if ((TreeMem[node].children[q]==NO_CHILD)!=(other.TreeMem[other_node].children[q]==NO_CHILD))
991 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])
992 SG_DEBUG(
">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
994 SG_DEBUG(
"============================================================\n")
995 other.display_node(other_node) ;
996 SG_DEBUG(
"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n")
999 if (!compare_traverse(abs(TreeMem[node].children[q]), other, abs(other.TreeMem[other_node].children[q])))
1010 template <
class Trie>
1014 for (int32_t i=0; i<length; i++)
1015 if (!compare_traverse(trees[i], other, other.trees[i]))
1018 SG_DEBUG(
"two tries at %i identical\n", i)
1023 template <
class Trie>
1025 int32_t
node, int32_t * trace, int32_t& trace_len)
const
1027 #ifdef TRIE_CHECK_EVERYTHING
1029 ASSERT((trace[trace_len-1]>=0) && (trace[trace_len-1]<TreeMemPtrMax))
1030 if (TreeMem[trace[trace_len-1]].has_seq)
1032 if (TreeMem[trace[trace_len-1]].has_floats)
1035 for (int32_t q=0; q<4; q++)
1037 if (TreeMem[trace[trace_len-1]].children[q]==NO_CHILD)
1039 int32_t tl=trace_len+1 ;
1040 if (TreeMem[trace[trace_len-1]].children[q]>=0)
1041 trace[trace_len]=TreeMem[trace[trace_len-1]].children[q] ;
1043 trace[trace_len]=-TreeMem[trace[trace_len-1]].children[q] ;
1045 if (trace[trace_len]==node)
1050 if (find_node(node, trace, tl))
1064 template <
class Trie>
1067 #ifdef TRIE_CHECK_EVERYTHING
1068 int32_t * trace=SG_MALLOC(int32_t, 2*degree);
1069 int32_t trace_len=-1 ;
1070 bool found = false ;
1072 for (tree=0; tree<length; tree++)
1074 trace[0]=trees[tree] ;
1076 found=find_node(node, trace, trace_len) ;
1081 SG_PRINT(
"position %i trace: ", tree)
1083 for (int32_t i=0; i<trace_len-1; i++)
1086 for (int32_t q=0; q<4; q++)
1087 if (abs(TreeMem[trace[i]].children[q])==trace[i+1])
1093 char acgt[5]=
"ACGT" ;
1096 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)
1097 if (TreeMem[node].has_floats)
1099 for (int32_t q=0; q<4; q++)
1100 SG_PRINT(
"child_weighs[%i] = %f\n", q, TreeMem[node].child_weights[q])
1102 if (TreeMem[node].has_seq)
1104 for (int32_t q=0; q<16; q++)
1105 SG_PRINT(
"seq[%i] = %i\n", q, TreeMem[node].seq[q])
1107 if (!TreeMem[node].has_seq && !TreeMem[node].has_floats)
1109 for (int32_t q=0; q<4; q++)
1111 if (TreeMem[node].children[q]!=NO_CHILD)
1113 SG_PRINT(
"children[%i] = %i -> \n", q, TreeMem[node].children[q])
1114 display_node(abs(TreeMem[node].children[q])) ;
1117 SG_PRINT(
"children[%i] = NO_CHILD -| \n", q, TreeMem[node].children[q])
1141 for (int32_t i=0; i<length; i++)
1142 trees[i] = NO_CHILD;
1153 delete_trees(get_use_compact_terminal_nodes());
1158 int32_t len,
bool p_use_compact_terminal_nodes)
1162 trees=SG_MALLOC(int32_t, len);
1164 for (int32_t i=0; i<len; i++)
1165 trees[i]=get_node(degree==1);
1168 use_compact_terminal_nodes=p_use_compact_terminal_nodes ;
1173 bool p_use_compact_terminal_nodes)
1179 for (int32_t i=0; i<length; i++)
1180 trees[i]=get_node(degree==1);
1182 use_compact_terminal_nodes=p_use_compact_terminal_nodes ;
1185 template <
class Trie>
1192 TRIE_ASSERT(tree>=0)
1194 if (depth==degree-2)
1196 ret+=(TreeMem[tree].weight) ;
1198 for (int32_t k=0; k<4; k++)
1199 ret+=(TreeMem[tree].child_weights[k]) ;
1204 ret+=(TreeMem[tree].weight) ;
1206 for (int32_t i=0; i<4; i++)
1207 if (TreeMem[tree].children[i]!=NO_CHILD)
1208 ret += compute_abs_weights_tree(TreeMem[tree].children[i], depth+1) ;
1214 template <
class Trie>
1218 for (int32_t i=0; i<length*4; i++)
1222 for (int32_t i=0; i<length; i++)
1224 TRIE_ASSERT(trees[i]!=NO_CHILD)
1225 for (int32_t k=0; k<4; k++)
1227 sum[i*4+k]=compute_abs_weights_tree(TreeMem[trees[i]].children[k], 0) ;
1234 template <
class Trie>
1236 int32_t tree, int32_t i,
float64_t alpha,
1237 int32_t *vec, int32_t len_rem,
1238 int32_t degree_rec, int32_t mismatch_rec,
1239 int32_t max_mismatch,
float64_t * weights)
1243 TRIE_ASSERT(tree!=NO_CHILD)
1245 if ((len_rem<=0) || (mismatch_rec>max_mismatch) || (degree_rec>degree))
1247 const int32_t other[4][3] = { {1,2,3},{0,2,3},{0,1,3},{0,1,2} } ;
1249 int32_t subtree = NO_CHILD ;
1251 if (degree_rec==degree-1)
1253 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1254 if (weights_in_tree)
1255 TreeMem[tree].child_weights[vec[0]] += alpha*weights[degree_rec+degree*mismatch_rec];
1257 if (weights[degree_rec]!=0.0)
1258 TreeMem[tree].child_weights[vec[0]] += alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec];
1259 if (mismatch_rec+1<=max_mismatch)
1260 for (int32_t o=0; o<3; o++)
1262 if (weights_in_tree)
1263 TreeMem[tree].child_weights[other[vec[0]][o]] += alpha*weights[degree_rec+degree*(mismatch_rec+1)];
1265 if (weights[degree_rec]!=0.0)
1266 TreeMem[tree].child_weights[other[vec[0]][o]] += alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec];
1272 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1273 if (TreeMem[tree].children[vec[0]]!=NO_CHILD)
1275 subtree=TreeMem[tree].children[vec[0]] ;
1276 if (weights_in_tree)
1277 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*mismatch_rec];
1279 if (weights[degree_rec]!=0.0)
1280 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec];
1284 int32_t tmp = get_node(degree_rec==degree-2);
1286 TreeMem[tree].children[vec[0]]=tmp ;
1288 #ifdef TRIE_CHECK_EVERYTHING
1289 if (degree_rec==degree-2)
1290 TreeMem[subtree].has_floats=true ;
1292 if (weights_in_tree)
1293 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*mismatch_rec] ;
1295 if (weights[degree_rec]!=0.0)
1296 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*mismatch_rec]/weights[degree_rec] ;
1298 TreeMem[subtree].weight = 0.0 ;
1300 add_example_to_tree_mismatch_recursion(subtree, i, alpha,
1302 degree_rec+1, mismatch_rec, max_mismatch, weights) ;
1304 if (mismatch_rec+1<=max_mismatch)
1306 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1307 for (int32_t o=0; o<3; o++)
1309 int32_t ot = other[vec[0]][o] ;
1310 if (TreeMem[tree].children[ot]!=NO_CHILD)
1312 subtree=TreeMem[tree].children[ot] ;
1313 if (weights_in_tree)
1314 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*(mismatch_rec+1)];
1316 if (weights[degree_rec]!=0.0)
1317 TreeMem[subtree].weight += alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec];
1321 int32_t tmp = get_node(degree_rec==degree-2);
1323 TreeMem[tree].children[ot]=tmp ;
1325 #ifdef TRIE_CHECK_EVERYTHING
1326 if (degree_rec==degree-2)
1327 TreeMem[subtree].has_floats=true ;
1330 if (weights_in_tree)
1331 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*(mismatch_rec+1)] ;
1333 if (weights[degree_rec]!=0.0)
1334 TreeMem[subtree].weight = alpha*weights[degree_rec+degree*(mismatch_rec+1)]/weights[degree_rec] ;
1336 TreeMem[subtree].weight = 0.0 ;
1339 add_example_to_tree_mismatch_recursion(subtree, i, alpha,
1341 degree_rec+1, mismatch_rec+1, max_mismatch, weights) ;
1347 template <
class Trie>
1349 int32_t tree, int32_t i, int32_t j,
float64_t weight, int32_t d,
1350 int32_t max_degree, int32_t num_feat, int32_t num_sym, int32_t sym_offset,
1361 for (int32_t k=0; k<num_sym; k++)
1363 if (TreeMem[tree].children[k]!=NO_CHILD)
1365 int32_t child=TreeMem[tree].children[k];
1368 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);
1370 result[sym_offset*(i+j-max_degree+1)+num_sym*offs+k] += weight+decay*TreeMem[child].weight;
1374 compute_scoring_helper(child, i, j+1, 0.0, 0, max_degree, num_feat, num_sym, sym_offset, offs, result);
1378 else if (j==degree-1)
1380 for (int32_t k=0; k<num_sym; k++)
1383 if (d<max_degree-1 && i<num_feat-1)
1384 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);
1386 result[sym_offset*(i+j-max_degree+1)+num_sym*offs+k] += weight+decay*TreeMem[tree].child_weights[k];
1392 template <
class Trie>
1394 int32_t tree,
const int32_t p,
struct TreeParseInfo info,
1395 const int32_t depth, int32_t*
const x,
const int32_t k)
1397 const int32_t num_sym = info.num_sym;
1398 const int32_t y0 = info.y0;
1399 const int32_t y1 = (k==0) ? 0 : y0 - ( (depth<k) ? 0 : info.nofsKmers[k-1] * x[depth-k] );
1410 for( sym=0; sym<num_sym; ++sym ) {
1411 const int32_t childNum = TreeMem[tree].children[ sym ];
1412 if( childNum != NO_CHILD ) {
1413 int32_t child = childNum ;
1415 info.substrs[depth+1] = y0 + sym;
1416 info.y0 = (k==0) ? 0 : (y1+sym)*num_sym;
1418 count( TreeMem[child].weight, depth, info, p, x, k );
1419 traverse( child, p, info, depth+1, x, k );
1424 else if( depth == degree-1 )
1426 for( sym=0; sym<num_sym; ++sym ) {
1427 const float64_t w = TreeMem[tree].child_weights[ sym ];
1430 info.substrs[depth+1] = y0 + sym;
1431 info.y0 = (k==0) ? 0 : (y1+sym)*num_sym;
1433 count( w, depth, info, p, x, k );
1442 template <
class Trie>
1444 const float64_t w,
const int32_t depth,
const struct TreeParseInfo info,
1445 const int32_t p, int32_t* x,
const int32_t k)
1454 const int32_t nofKmers = info.nofsKmers[k];
1455 const float64_t margWeight = w * info.margFactors[ depth-k ];
1456 const int32_t m_a = depth - k + 1;
1457 const int32_t m_b = info.num_feat - p;
1458 const int32_t m = ( m_a < m_b ) ? m_a : m_b;
1460 const int32_t offset0 = nofKmers * p;
1464 for( i = 0; i < m; ++i ) {
1465 const int32_t y = info.substrs[i+k+1];
1466 info.C_k[ y + offset ] += margWeight;
1471 const int32_t offsR = info.substrs[k+1] + offset0;
1472 info.R_k[offsR] += margWeight;
1474 if( p+depth-k < info.num_feat ) {
1475 const int32_t offsL = info.substrs[depth+1] + nofKmers * (p+depth-k);
1476 info.L_k[offsL] += margWeight;
1496 template <
class Trie>
1498 int32_t i, int32_t seq_offset, int32_t * vec,
float32_t alpha,
1499 float64_t *weights,
bool degree_times_position_weights)
1501 int32_t tree = trees[i] ;
1504 int32_t max_depth = 0 ;
1506 if (degree_times_position_weights)
1507 weights_column = &weights[(i+seq_offset)*degree] ;
1509 weights_column = weights ;
1511 if (weights_in_tree)
1513 for (int32_t j=0; (j<degree) && (i+j<length); j++)
1521 for (int32_t j=0; (j<max_depth) && (i+j+seq_offset<length); j++)
1523 TRIE_ASSERT((vec[i+j+seq_offset]>=0) && (vec[i+j+seq_offset]<4))
1524 if ((j<degree-1) && (TreeMem[tree].children[vec[i+j+seq_offset]]!=NO_CHILD))
1526 if (TreeMem[tree].children[vec[i+j+seq_offset]]<0)
1529 TRIE_ASSERT(j >= degree-16)
1531 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1532 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1533 int32_t
node = - TreeMem[tree].
children[vec[i+j+seq_offset]] ;
1535 TRIE_ASSERT((node>=0) && (node<=TreeMemPtrMax))
1536 TRIE_ASSERT_EVERYTHING(TreeMem[node].has_seq)
1537 TRIE_ASSERT_EVERYTHING(!TreeMem[node].has_floats)
1540 int32_t mismatch_pos = -1 ;
1543 for (k=0; (j+k<max_depth) && (i+j+seq_offset+k<length); k++)
1545 TRIE_ASSERT((vec[i+j+seq_offset+k]>=0) && (vec[i+j+seq_offset+k]<4))
1547 if ((TreeMem[node].seq[k]>=4) && (TreeMem[node].seq[k]!=TRIE_TERMINAL_CHARACTER))
1548 fprintf(stderr,
"+++i=%i j=%i seq[%i]=%i\n", i, j, k, TreeMem[node].seq[k]) ;
1549 TRIE_ASSERT((TreeMem[node].seq[k]<4) || (TreeMem[node].seq[k]==TRIE_TERMINAL_CHARACTER))
1551 if (TreeMem[node].seq[k]!=vec[i+j+seq_offset+k])
1561 if (mismatch_pos==-1)
1563 TreeMem[node].weight+=alpha ;
1571 int32_t last_node=tree ;
1575 for (k=0; k<mismatch_pos; k++)
1577 TRIE_ASSERT((vec[i+j+seq_offset+k]>=0) && (vec[i+j+seq_offset+k]<4))
1578 TRIE_ASSERT(vec[i+j+seq_offset+k]==TreeMem[node].seq[k])
1580 int32_t tmp=get_node();
1581 TreeMem[last_node].children[vec[i+j+seq_offset+k]]=tmp ;
1583 if (weights_in_tree)
1584 TreeMem[last_node].weight = (TreeMem[node].weight+alpha)*weights_column[j+k] ;
1586 TreeMem[last_node].weight = (TreeMem[node].weight+alpha) ;
1587 TRIE_ASSERT(j+k!=degree-1)
1589 if ((TreeMem[node].seq[mismatch_pos]>=4) && (TreeMem[node].seq[mismatch_pos]!=TRIE_TERMINAL_CHARACTER))
1590 fprintf(stderr,
"**i=%i j=%i seq[%i]=%i\n", i, j, k, TreeMem[node].seq[mismatch_pos]) ;
1591 ASSERT((TreeMem[node].seq[mismatch_pos]<4) || (TreeMem[node].seq[mismatch_pos]==TRIE_TERMINAL_CHARACTER))
1592 TRIE_ASSERT(vec[i+j+seq_offset+mismatch_pos]!=TreeMem[node].seq[mismatch_pos])
1599 for (int32_t q=0; q<4; q++)
1600 TreeMem[last_node].child_weights[q]=0.0 ;
1601 if (weights_in_tree)
1603 if (TreeMem[node].seq[mismatch_pos]<4)
1604 TreeMem[last_node].child_weights[TreeMem[node].seq[mismatch_pos]]+=TreeMem[node].weight*weights_column[degree-1] ;
1605 TreeMem[last_node].child_weights[vec[i+j+seq_offset+k]] += alpha*weights_column[degree-1] ;
1609 if (TreeMem[node].seq[mismatch_pos]<4)
1610 TreeMem[last_node].child_weights[TreeMem[node].seq[mismatch_pos]]=TreeMem[node].weight ;
1611 TreeMem[last_node].child_weights[vec[i+j+seq_offset+k]] = alpha ;
1614 #ifdef TRIE_CHECK_EVERYTHING
1615 TreeMem[last_node].has_floats=true ;
1621 if (TreeMem[node].seq[mismatch_pos]<4)
1623 TreeMem[last_node].children[TreeMem[node].seq[mismatch_pos]] = -node ;
1626 for (int32_t q=0; q<16; q++)
1628 if ((j+q+mismatch_pos<degree) && (i+j+seq_offset+q+mismatch_pos<length))
1629 TreeMem[node].seq[q] = TreeMem[node].seq[q+mismatch_pos] ;
1631 TreeMem[node].seq[q] = TRIE_TERMINAL_CHARACTER ;
1633 #ifdef TRIE_CHECK_EVERYTHING
1634 TreeMem[node].has_seq=true ;
1639 TRIE_ASSERT((vec[i+j+seq_offset+mismatch_pos]>=0) && (vec[i+j+seq_offset+mismatch_pos]<4))
1640 int32_t tmp = get_node() ;
1641 TreeMem[last_node].children[vec[i+j+seq_offset+mismatch_pos]] = -tmp ;
1644 TreeMem[last_node].weight = alpha ;
1645 #ifdef TRIE_CHECK_EVERYTHING
1646 TreeMem[last_node].has_seq = true ;
1648 memset(TreeMem[last_node].seq, TRIE_TERMINAL_CHARACTER, 16) ;
1649 for (int32_t q=0; (j+q+mismatch_pos<degree) && (i+j+seq_offset+q+mismatch_pos<length); q++)
1650 TreeMem[last_node].seq[q] = vec[i+j+seq_offset+mismatch_pos+q] ;
1657 tree=TreeMem[tree].children[vec[i+j+seq_offset]] ;
1658 TRIE_ASSERT((tree>=0) && (tree<TreeMemPtrMax))
1659 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1660 if (weights_in_tree)
1661 TreeMem[tree].weight += alpha*weights_column[j];
1663 TreeMem[tree].weight += alpha ;
1666 else if (j==degree-1)
1669 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1670 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1671 if (weights_in_tree)
1672 TreeMem[tree].child_weights[vec[i+j+seq_offset]] += alpha*weights_column[j] ;
1674 TreeMem[tree].child_weights[vec[i+j+seq_offset]] += alpha;
1680 bool use_seq = use_compact_terminal_nodes && (j>degree-16) ;
1681 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1682 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1684 int32_t tmp = get_node((j==degree-2) && (!use_seq));
1686 TreeMem[tree].children[vec[i+j+seq_offset]] = -tmp ;
1688 TreeMem[tree].children[vec[i+j+seq_offset]] = tmp ;
1691 TRIE_ASSERT((tree>=0) && (tree<TreeMemPtrMax))
1692 #ifdef TRIE_CHECK_EVERYTHING
1693 TreeMem[tree].has_seq = use_seq ;
1697 TreeMem[tree].weight = alpha ;
1699 memset(TreeMem[tree].seq, TRIE_TERMINAL_CHARACTER, 16) ;
1700 for (int32_t q=0; (j+q<degree) && (i+j+seq_offset+q<length); q++)
1703 TreeMem[tree].seq[q]=vec[i+j+seq_offset+q] ;
1709 if (weights_in_tree)
1710 TreeMem[tree].weight = alpha*weights_column[j] ;
1712 TreeMem[tree].weight = alpha ;
1713 #ifdef TRIE_CHECK_EVERYTHING
1715 TreeMem[tree].has_floats = true ;
1722 template <
class Trie>
1724 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
1726 bool degree_times_position_weights)
1728 int32_t tree = trees[tree_pos] ;
1730 if ((position_weights!=NULL) && (position_weights[weight_pos]==0))
1734 if (degree_times_position_weights)
1735 weights_column=&weights[weight_pos*degree] ;
1737 weights_column=weights ;
1740 for (int32_t j=0; seq_pos+j < len; j++)
1742 TRIE_ASSERT((vec[seq_pos+j]<4) && (vec[seq_pos+j]>=0))
1744 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1746 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1747 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1749 tree = - TreeMem[tree].children[vec[seq_pos+j]];
1750 TRIE_ASSERT(tree>=0)
1751 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1753 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1755 TRIE_ASSERT((vec[seq_pos+j+k]<4) && (vec[seq_pos+j+k]>=0))
1756 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1758 this_weight += weights_column[j+k] ;
1760 sum += TreeMem[tree].weight * this_weight ;
1765 tree=TreeMem[tree].children[vec[seq_pos+j]];
1766 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1767 if (weights_in_tree)
1768 sum += TreeMem[tree].weight ;
1770 sum += TreeMem[tree].weight * weights_column[j] ;
1775 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1778 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_floats)
1779 if (weights_in_tree)
1780 sum += TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1782 sum += TreeMem[tree].child_weights[vec[seq_pos+j]] * weights_column[j] ;
1785 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_floats)
1791 if (position_weights!=NULL)
1792 return sum*position_weights[weight_pos] ;
1797 template <
class Trie>
1799 int32_t* vec, int32_t len, int32_t seq_pos, int32_t tree_pos,
1801 int32_t mkl_stepsize,
float64_t * weights,
1802 bool degree_times_position_weights)
1804 int32_t tree = trees[tree_pos] ;
1808 if (position_weights!=NULL)
1810 factor *= position_weights[weight_pos] ;
1813 if (!degree_times_position_weights)
1815 for (int32_t j=0; seq_pos+j<len; j++)
1817 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1819 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1821 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1822 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1823 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1825 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1827 if (weights_in_tree)
1828 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1830 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k] ;
1836 tree=TreeMem[tree].children[vec[seq_pos+j]];
1837 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1838 if (weights_in_tree)
1839 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1841 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j] ;
1846 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1849 if (weights_in_tree)
1850 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1852 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j] ;
1859 for (int32_t j=0; seq_pos+j<len; j++)
1861 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1863 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1865 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1866 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1867 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1869 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1871 if (weights_in_tree)
1872 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1874 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k+weight_pos*degree] ;
1880 tree=TreeMem[tree].children[vec[seq_pos+j]];
1881 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1882 if (weights_in_tree)
1883 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight ;
1885 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+weight_pos*degree] ;
1890 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1893 if (weights_in_tree)
1894 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1896 LevelContrib[weight_pos/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j+weight_pos*degree] ;
1903 else if (!degree_times_position_weights)
1905 for (int32_t j=0; seq_pos+j<len; j++)
1907 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1909 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1911 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1912 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1913 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1915 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1917 if (weights_in_tree)
1918 LevelContrib[(j+k)/mkl_stepsize] += factor*TreeMem[tree].weight ;
1920 LevelContrib[(j+k)/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k] ;
1926 tree=TreeMem[tree].children[vec[seq_pos+j]];
1927 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1928 if (weights_in_tree)
1929 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].weight ;
1931 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j] ;
1936 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1939 if (weights_in_tree)
1940 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]] ;
1942 LevelContrib[j/mkl_stepsize] += factor*TreeMem[tree].child_weights[vec[seq_pos+j]]*weights[j] ;
1968 for (int32_t j=0; seq_pos+j<len; j++)
1970 if ((j<degree-1) && (TreeMem[tree].children[vec[seq_pos+j]]!=NO_CHILD))
1972 if (TreeMem[tree].children[vec[seq_pos+j]]<0)
1974 tree = -TreeMem[tree].children[vec[seq_pos+j]];
1975 TRIE_ASSERT_EVERYTHING(TreeMem[tree].has_seq)
1976 for (int32_t k=0; (j+k<degree) && (seq_pos+j+k<length); k++)
1978 if (TreeMem[tree].seq[k]!=vec[seq_pos+j+k])
1980 if (weights_in_tree)
1981 LevelContrib[(j+k+degree*weight_pos)/mkl_stepsize] += factor*TreeMem[tree].weight ;
1983 LevelContrib[(j+k+degree*weight_pos)/mkl_stepsize] += factor*TreeMem[tree].weight*weights[j+k+weight_pos*degree] ;
1989 tree=TreeMem[tree].children[vec[seq_pos+j]];
1990 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
1991 if (weights_in_tree)
1992 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].weight ;
1994 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].weight * weights[j+weight_pos*degree] ;
1999 TRIE_ASSERT_EVERYTHING(!TreeMem[tree].has_seq)
2002 if (weights_in_tree)
2003 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].child_weights[vec[seq_pos+j]] ;
2005 LevelContrib[(j+degree*weight_pos)/mkl_stepsize] += factor * TreeMem[tree].child_weights[vec[seq_pos+j]] * weights[j+weight_pos*degree] ;
2013 template <
class Trie>
2015 Trie* tree, int32_t depth, uint64_t seq,
float64_t value,
2020 if (weights_in_tree || depth==0)
2021 value+=tree->weight;
2024 w=weights[degree-1];
2025 value+=weights[depth-1]*tree->weight;
2028 if (degree-1==depth)
2030 for (int32_t sym=0; sym<4; sym++)
2035 ConsensusEntry entry;
2037 entry.score=value+v;
2038 entry.string=seq | ((uint64_t) sym) << (2*(degree-depth-1));
2046 for (int32_t sym=0; sym<4; sym++)
2048 uint64_t str=seq | ((uint64_t) sym) << (2*(degree-depth-1));
2049 if (tree->children[sym] != NO_CHILD)
2050 fill_backtracking_table_recursion(&TreeMem[tree->children[sym]], depth+1, str, value, table, weights);
2055 template <
class Trie>
2057 int32_t pos, uint64_t seq, int32_t deg,
float64_t* weights)
2063 for (int32_t i=pos; i<pos+deg && i<length; i++)
2066 Trie* tree = &TreeMem[trees[i]];
2068 for (int32_t d=0; d<deg-i+pos; d++)
2072 int32_t sym = (int32_t) (seq >> (2*(deg-1-d-i+pos)) & 3);
2075 if (!weights_in_tree)
2078 ASSERT(tree->children[sym] != NO_CHILD)
2079 tree=&TreeMem[tree->children[sym]];
2080 result+=w*tree->weight;
2087 template <
class Trie>
2092 ASSERT(pos>=0 && pos<length)
2093 ASSERT(!use_compact_terminal_nodes)
2095 Trie* t = &TreeMem[trees[pos]];
2097 fill_backtracking_table_recursion(t, 0, (uint64_t) 0, 0.0, cur, weights);
2103 for (int32_t i=0; i<num_cur; i++)
2106 entry.score+=get_cumulative_score(pos+1, entry.string, degree-1, weights);
2119 for (int32_t i=0; i<num_cur; i++)
2122 uint64_t str_cur= cur->
get_element(i).string >> 2;
2128 for (int32_t j=0; j<num_prev; j++)
2132 ((((uint64_t)0)-1) ^ (((uint64_t) 3) << (2*(degree-1))));
2133 uint64_t str_prev= mask & prev->
get_element(j).string;
2136 if (str_cur == str_prev)
2139 if (bt==-1 || sc>max_score)
2150 ConsensusEntry entry;
2152 entry.score=max_score;
2160 #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...
Matrix::Scalar sum(Matrix m, bool no_diag=false)
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)
static T abs(T a)
return the absolute value of a number