40 #include "EST_lattice.h"
58 if(nodes.head() != NULL )
59 return nodes(nodes.head());
61 cerr <<
"LAttice has no nodes !" << endl;
68 bool Lattice::build_qmap(Bigram &g,
float error_margin)
81 Tlist<float> list_qmap;
83 qmap_error_margin = error_margin;
85 for (i = 0; i < g.size(); ++i){
86 for (j = 0; j < g.size(); ++j){
89 for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
90 if(fabs(list_qmap(l_ptr) - g.p(i,j)) <= error_margin){
96 list_qmap.append(g.p(i,j));
103 for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
104 if(fabs(list_qmap(l_ptr)) <= error_margin){
115 for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
121 for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
122 qmap(i++) = list_qmap(l_ptr);
127 cerr <<
"Built qmap with " << i <<
" entries" << endl;
134 Lattice::build_nmap(Bigram &g)
143 Tlist<EST_String> list_nmap;
146 for (j = 0; j < g.size() - 2; ++j){
147 if(g.words(j) ==
"!ENTER"){
148 cerr <<
"Wordlist contains special word !ENTER" << endl;
151 if(g.words(j) ==
"!EXIT"){
152 cerr <<
"Wordlist contains special word !EXIT" << endl;
161 for (j = 0; j < g.size() - 2; ++j)
162 list_nmap.append(g.words(j));
165 list_nmap.append(
"!ENTER");
166 list_nmap.append(
"!EXIT");
170 cerr << list_nmap << endl;
173 for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
179 for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
180 nmap(j++) = list_nmap(l_ptr);
183 cerr <<
"Built nmap with " << j <<
" entries" << endl;
190 Lattice::construct_alphabet(Bigram &g)
193 int i,j,enteri,exiti,aindex,qindex,nindex,count;
198 if(!build_qmap(g,1.0e-02) || !build_nmap(g))
203 Tlist<symbol_t*> list_alphabet;
208 enteri = g.size() - 2;
209 exiti = g.size() - 1;
214 for (j = 0; j < g.size(); ++j){
216 cerr <<
"constructing alphabet " << (int)((
float)j*100/(
float)g.size()) << "% \r";
219 nindex = nmap_name_to_index("!ENTER");
221 nindex = nmap_name_to_index("!EXIT");
223 nindex = nmap_name_to_index(g.words(j));
225 for (i = 0; i < g.size(); ++i){
227 qindex = qmap_value_to_index(g.p(i,j));
231 for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev()){
232 if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
233 (list_alphabet(a_ptr)->qmap_index == qindex) ){
240 if(list_alphabet(a_ptr)->nmap_index != nindex)
247 sym->qmap_index=qindex;
248 sym->nmap_index=nindex;
249 list_alphabet.append(sym);
255 nindex = nmap_name_to_index(
"!ENTER");
256 qindex = qmap_value_to_index(0);
258 for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev())
259 if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
260 (list_alphabet(a_ptr)->qmap_index == qindex) ){
267 sym->qmap_index=qindex;
268 sym->nmap_index=nindex;
269 list_alphabet.append(sym);
276 list_alphabet.append(sym);
278 ptr_qsort(list_alphabet);
281 for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
285 alphabet.resize(count);
287 for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
288 alphabet(count++) = *(list_alphabet(a_ptr));
291 list_alphabet.clear();
293 e_move_symbol_index = alphabet_index_lookup(-1,-1);
295 cerr <<
"Alphabet has " << count <<
" symbols " << endl;
302 Lattice::construct(Bigram &g)
314 int enteri = g.size() - 2;
315 int exiti = g.size() - 1;
316 int from_name,to_name;
321 Node *enter_node =
new Node;
322 enter_node->name.append(-1);
323 nodes.append(enter_node);
326 for(i=0; i<nmap.
n(); i++){
332 if(nmap(i) ==
"!ENTER"){
334 symbol = alphabet_index_lookup(i,qmap_value_to_index(0));
338 enter_node->arcs_out.append(a);
344 if(nmap(i) ==
"!EXIT")
345 final_nodes.append(n);
351 for (i = 0; i < g.size(); ++i){
352 cerr <<
"building lattice " << (int)((
float)i*100/(
float)g.size()) << "% \r";
353 for (j = 0; j < g.size(); ++j){
357 if((j != enteri) && (i != exiti)){
364 from_name = nmap_name_to_index(
"!ENTER");
366 from_name = nmap_name_to_index(g.words(i));
369 to_name = nmap_name_to_index(
"!EXIT");
371 to_name= nmap_name_to_index(g.words(j));
373 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
374 int name = nodes(n_ptr)->name(nodes(n_ptr)->name.head());
375 if(name == from_name)
382 cerr <<
"Couldn't find 'from' node " << nmap_index_to_name(from_name) << endl;
387 cerr <<
"Couldn't find 'to' node " << nmap_index_to_name(to_name) << endl;
392 symbol = alphabet_index_lookup(to_name,qmap_value_to_index(g.p(i,j)));
394 cerr <<
"Couldn't lookup symbol in alphabet !" << endl;
402 from->arcs_out.append(a);
411 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
413 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
417 for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
420 cerr <<
"NFA has " << c1
421 <<
" nodes (" << c3 <<
" final)"
422 <<
" and " << c2 <<
" arcs" << endl;
428 bool Lattice::determinise()
446 int c,count,current_label,new_arcs_made;
451 cerr <<
"sorting arc lists" << endl;
454 cerr <<
"making new nodes" << endl;
468 if(new_node == NULL){
469 cerr <<
"Could not allocate any more memory";
472 new_node->name = nodes(nodes.head())->name;
473 new_nodes.
append(new_node);
477 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
479 for (a_ptr = nodes(n_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
481 current_label = nodes(n_ptr)->arcs_out(a_ptr)->label;
486 new_name = nodes(n_ptr)->arcs_out(a_ptr)->to->name;
487 if(
final(nodes(n_ptr)->arcs_out(a_ptr)->to) )
489 while((a_ptr != NULL) &&
490 (a_ptr->next() != NULL) &&
491 (nodes(n_ptr)->arcs_out(a_ptr->next())->label == current_label)){
492 merge_sort_unique(new_name,nodes(n_ptr)->arcs_out(a_ptr->next())->to->name);
494 if( !is_final &&
final(nodes(n_ptr)->arcs_out(a_ptr->next())->to) )
503 for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
504 if( new_nodes(n2_ptr)->name == new_name ){
512 if(new_node == NULL){
513 cerr <<
"Could not allocate any more memory";
515 for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
517 cerr <<
" after making " << count <<
" nodes" << endl;
521 new_node->name = new_name;
522 new_nodes.
append(new_node);
525 new_final_nodes.
append(new_node);
539 for (n_ptr = new_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
542 cerr <<
"Processing node " << c
543 <<
" arcs=" << new_arcs_made <<
" \r";
547 for(l_ptr=new_nodes(n_ptr)->name.head(); l_ptr != 0; l_ptr = l_ptr->next()){
549 for(n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
551 if(nodes(n2_ptr)->name(nodes(n2_ptr)->name.head()) ==
552 new_nodes(n_ptr)->name(l_ptr))
553 arc_list += nodes(n2_ptr)->arcs_out;
568 sort_by_label(arc_list);
570 for(a_ptr=arc_list.head();a_ptr!=NULL;a_ptr=a_ptr->next()){
572 current_label=arc_list(a_ptr)->label;
577 new_name2 = arc_list(a_ptr)->to->name;
578 if(
final(arc_list(a_ptr)->to) )
580 while((a_ptr != NULL) &&
581 (a_ptr->next() != NULL) &&
582 (arc_list(a_ptr->next())->label == current_label)){
583 merge_sort_unique(new_name2,arc_list(a_ptr)->to->name);
584 if( !is_final &&
final(arc_list(a_ptr)->to) )
593 for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
594 if( new_nodes(n2_ptr)->name == new_name2 ){
601 if(new_node == NULL){
602 cerr <<
"Could not allocate any more memory";
604 for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
606 cerr <<
" after making " << count <<
" nodes" << endl;
610 new_node->name = new_name2;
611 new_nodes.
append(new_node);
612 link(new_nodes(n_ptr),new_node,current_label);
615 new_final_nodes.
append(new_node);
619 link(new_nodes(n_ptr),new_nodes(n2_ptr),current_label);
632 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
639 final_nodes=new_final_nodes;
640 new_final_nodes.
clear();
643 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
645 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
649 for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
652 cerr <<
"DFA has " << c1
653 <<
" nodes (" << c3 <<
" final)"
654 <<
" and " << c2 <<
" arcs" << endl;
661 Lattice::link(Node *n1, Node *n2,
int label)
671 if( (n1==NULL) || (n2==NULL) ){
672 cerr <<
"Can't link null nodes" << endl;
681 new_arc->label = label;
683 n1->arcs_out.append(new_arc);
691 Lattice::sort_arc_lists()
695 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
700 sort_by_label(nodes(n_ptr)->arcs_out);
713 Lattice::build_distinguished_state_table(
bool ** &dst)
719 int num_nodes = nodes.length();
721 dst =
new bool*[num_nodes];
723 cerr <<
"Not enough memory" << endl;
726 for(i=0;i<num_nodes;i++){
727 dst[i] =
new bool[num_nodes];
729 cerr <<
"Not enough memory" << endl;
732 for(j=0;j<num_nodes;j++)
737 cerr <<
"final/non-final scan";
739 for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
740 for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
742 if(
final(nodes(n_ptr)) && !
final(nodes(n2_ptr)))
744 else if(!
final(nodes(n_ptr)) &&
final(nodes(n2_ptr)))
758 if(!build_transition_function()){
759 cerr <<
"Couldn't build transition function" << endl;
763 if(!build_distinguished_state_table_from_transition_function(dst)){
764 cerr <<
"Couldn't build dst from transition function" << endl;
769 for(i=0;i<num_nodes;i++)
778 Lattice::build_distinguished_state_table_direct(
bool ** &dst)
781 int i,j,i1,j1,scan_count,this_symbol;
795 for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
797 for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
799 cerr <<
"scan " << scan_count <<
" : " << i <<
"," << j <<
" \r";
807 s_ptr=nodes(n_ptr)->arcs_out.head();
808 while(s_ptr != NULL){
812 this_symbol=nodes(n_ptr)->arcs_out(s_ptr)->label;
813 i1 = node_index(nodes(n_ptr)->arcs_out(s_ptr)->to);
816 for(a_ptr=nodes(n2_ptr)->arcs_out.head();
817 a_ptr!=NULL; a_ptr=a_ptr->next())
818 if(nodes(n2_ptr)->arcs_out(a_ptr)->label == this_symbol)
819 j1 = node_index(nodes(n2_ptr)->arcs_out(a_ptr)->to);
822 this_symbol=nodes(n2_ptr)->arcs_out(s_ptr)->label;
823 j1 = node_index(nodes(n2_ptr)->arcs_out(s_ptr)->to);
826 for(a_ptr=nodes(n_ptr)->arcs_out.head();
827 a_ptr!=NULL; a_ptr=a_ptr->next())
828 if(nodes(n_ptr)->arcs_out(a_ptr)->label == this_symbol)
829 i1 = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
838 if( ( (i1>=0) && (j1>=0) && dst[i1][j1]) ||
839 ( (i1>=0) && (j1<0) ) ||
840 ( (j1>=0) && (i1<0) ) )
849 if( (s_ptr==NULL) && (flag2) ){
850 s_ptr=nodes(n2_ptr)->arcs_out.head();
864 Lattice::build_distinguished_state_table_from_transition_function(
bool ** &dst)
866 int i,j,i2,j2,k,scan_count;
867 int num_nodes = nodes.length();
868 int num_symbols = alphabet.n();
878 for(i=0;i<num_nodes-1;i++){
880 cerr <<
"scan " << scan_count <<
" : row "
883 for(j=i+1;j<num_nodes;j++){
887 for(k=0;k<num_symbols;k++){
892 if((i2<0) && (j2>=0)){
897 }
else if((j2<0) && (i2>=0)){
902 }
else if( (i2>0) && (j2>0) && dst[i2][j2] ){
927 int num_nodes = nodes.length();
931 if(!build_distinguished_state_table(dst)){
932 cerr <<
"Couldn't build distinguished state table" << endl;
936 int count=0,count2=0;
937 for(i=0;i<num_nodes-1;i++)
938 for(j=i+1;j<num_nodes;j++)
944 cerr <<
"There are " << count <<
" undistinguished pairs of nodes and "
945 << count2 <<
" distinguished pairs" << endl;
958 for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
960 cerr <<
"merge, processing row " << i <<
" \r";
962 for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
967 if(merge_list.head() == NULL){
969 merge_list.
append(nodes(n_ptr));
970 merge_list.
append(nodes(n2_ptr));
977 bool add1=
false,add2=
false;
978 for(n3_ptr=merge_list.head();n3_ptr!=NULL;n3_ptr=n3_ptr->next()){
979 if(merge_list(n3_ptr) == nodes(n_ptr))
981 if(merge_list(n3_ptr) == nodes(n2_ptr))
987 merge_list.
append(nodes(n_ptr));
989 }
else if(add2 && !add1){
990 merge_list.
append(nodes(n2_ptr));
1001 if(merge_list.head() != NULL){
1005 for(n_ptr=merge_list.head();n_ptr!=NULL;n_ptr=n_ptr->next())
1007 cerr <<
"merging " << count <<
" nodes out of ";
1010 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
1014 merge_nodes(merge_list);
1018 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
1020 cerr <<
" leaving " << count << endl;
1029 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1031 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
1035 cerr <<
"Minimum state DFA has " << c1
1036 <<
" nodes and " << c2 <<
" arcs " << endl;
1041 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1043 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
1047 cerr <<
"Pruned minimum state DFA has " << c1
1048 <<
" nodes and " << c2 <<
" arcs" << endl;
1050 for(i=0;i<num_nodes;i++)
1062 if(l.head() == NULL)
1068 EST_Litem *n_ptr,*n2_ptr,*a_ptr,*a2_ptr;
1070 new_node =
new Node;
1077 for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1080 for(a_ptr=l(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next())
1081 new_node->arcs_out.append(l(n_ptr)->arcs_out(a_ptr));
1084 merge_sort_unique(new_node->name,l(n_ptr)->name);
1087 for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next()){
1088 for(a2_ptr=nodes(n2_ptr)->arcs_out.head();a2_ptr!=NULL;a2_ptr=a2_ptr->next()){
1089 if(nodes(n2_ptr)->arcs_out(a2_ptr)->to == l(n_ptr))
1090 nodes(n2_ptr)->arcs_out(a2_ptr)->to = new_node;
1098 for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1099 for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next())
1100 if(nodes(n2_ptr) == l(n_ptr)){
1101 nodes(n2_ptr)->name.clear();
1102 nodes(n2_ptr)->arcs_out.clear();
1103 delete nodes(n2_ptr);
1104 nodes.remove(n2_ptr);
1108 nodes.append(new_node);
1113 Lattice::merge_arcs()
1121 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1124 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
1127 cerr <<
"merging arcs from node " << ++count
1128 <<
", before:" << count2;
1130 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr->next()!=NULL; a_ptr=a_ptr->next()){
1133 for(a2_ptr=a_ptr->next();a2_ptr!=NULL; a2_ptr=a2_ptr->next())
1135 if((nodes(n_ptr)->arcs_out(a_ptr)->label ==
1136 nodes(n_ptr)->arcs_out(a2_ptr)->label) &&
1138 (nodes(n_ptr)->arcs_out(a_ptr)->to ==
1139 nodes(n_ptr)->arcs_out(a2_ptr)->to) ){
1141 delete nodes(n_ptr)->arcs_out(a2_ptr);
1142 a2_ptr=nodes(n_ptr)->arcs_out.remove(a2_ptr);
1149 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
1152 cerr<<
", after:" << count2 << endl;
1156 cerr <<
" \r" << endl;
1167 for(a_ptr=arcs.head(); a_ptr != 0; a_ptr=a_ptr->next() ){
1168 prune_arc(node, arcs(a_ptr));
1176 Lattice::prune_arc(Node *node, Arc *arc)
1178 remove_arc_from_nodes_out_list(node,arc);
1194 Lattice::remove_arc_from_nodes_out_list(Node *n, Arc *a)
1197 for (a_ptr = n->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
1198 if(n->arcs_out(a_ptr) == a)
1199 n->arcs_out.remove(a_ptr);
1228 Lattice::nmap_index_to_name(
int index)
1230 if(index < nmap.
n())
1233 cerr <<
"Warning : nmap index " << index <<
" out of range" << endl;
1240 Lattice::nmap_name_to_index(
const EST_String &name)
1252 if(name > nmap(mid))
1255 else if(name < nmap(mid))
1266 cerr <<
"Lattice::nmap_name_to_index failed for '"
1267 << name <<
"'" << endl;
1275 else if(name == nmap(j))
1278 cerr <<
"Lattice::nmap_name_to_index failed for '"
1279 << name <<
"'" << endl;
1292 Lattice::qmap_index_to_value(
int index)
1294 if(index < qmap.
n())
1297 cerr <<
"Warning : qmap index " << index <<
" out of range" << endl;
1304 Lattice::qmap_value_to_index(
float value)
1316 if(value > qmap(mid))
1319 else if(value < qmap(mid))
1330 if( fabs(qmap(i) - value) < fabs(qmap(j) - value) )
1341 Lattice::node_index(Node *n)
1344 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
1345 if(nodes(n_ptr) == n)
1346 return nodes.index(n_ptr);
1371 for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
1375 for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
1377 for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
1378 if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
1380 if(nodes(n2_ptr)->arcs_out(a_ptr)->label != e_move_symbol_index){
1381 word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
1383 sort_unique(word_list);
1391 if((word_list.head() != NULL) && word_list.head()->next() != NULL){
1396 for(w_ptr=word_list.head();w_ptr!=NULL;w_ptr=w_ptr->next()){
1399 new_node =
new Node;
1401 new_arc->label = e_move_symbol_index;
1402 new_arc->to = nodes(n_ptr);
1403 new_node->arcs_out.append(new_arc);
1406 for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
1408 for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
1409 if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
1411 word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
1412 if(word == word_list(w_ptr)){
1415 nodes(n2_ptr)->arcs_out(a_ptr)->to = new_node;
1421 nodes.append(new_node);
1430 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1431 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next()){
1450 if(final_nodes.length() > 1){
1451 cerr <<
" making single EXIT node" << endl;
1454 new_node =
new Node;
1456 for(n_ptr=final_nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1459 new_arc->label = e_move_symbol_index;
1460 new_arc->to = final_nodes(n_ptr);
1461 final_nodes(n_ptr)->arcs_out.append(new_arc);
1467 final_nodes.clear();
1470 nodes.append(new_node);
1471 final_nodes.append(new_node);
1476 for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
1478 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
1482 cerr <<
"HTKified DFA has " << c1
1483 <<
" nodes and " << c2 <<
" arcs" << endl;
1489 Lattice::final(Node *n)
1492 for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
1493 if(final_nodes(n_ptr) == n)
1505 for(l_ptr=l.head();l_ptr!=NULL;l_ptr=l_ptr->next())
1506 name+=nmap_index_to_name(l(l_ptr)) +
",";
1514 Lattice::alphabet_index_lookup(
int nmap_index,
int qmap_index)
1517 sym.nmap_index = nmap_index;
1518 sym.qmap_index = qmap_index;
1520 return alphabet_symbol_to_index(&sym);
1525 Lattice::alphabet_index_to_symbol(
int index)
1527 if(index < alphabet.n())
1528 return &(alphabet[index]);
1530 cerr <<
"Warning : alphabet index " << index <<
" out of range" << endl;
1550 if(*sym > alphabet(mid))
1553 else if(*sym < alphabet(mid))
1560 if(*sym == alphabet(i))
1563 cerr <<
"Lattice::alphabet_symbol_to_index failed for '"
1564 << *sym <<
"' 1" << endl;
1570 if(*sym == alphabet(i))
1572 else if(*sym == alphabet(j))
1575 cerr <<
"Lattice::alphabet_symbol_to_index failed for '"
1576 << *sym <<
"' 2" << endl;
1578 cerr << i <<
" " << alphabet(i) << endl;
1579 cerr << j <<
" " << alphabet(j) << endl;
1594 Lattice::build_transition_function()
1602 int num_nodes = nodes.length();
1603 int num_symbols = alphabet.n();
1606 cerr <<
"Warning : discarding existing transition function" << endl;
1609 tf =
new int*[num_nodes];
1610 for(i=0;i<num_nodes;i++)
1611 tf[i] =
new int[num_symbols];
1614 cerr <<
"Not enough memory to build transition function"
1615 <<
"(needed " << num_nodes*num_symbols*
sizeof(int) <<
" bytes)" << endl;
1619 for(i=0,n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next(),i++){
1621 cerr <<
"building transition function " << (int)((
float)(i+1)*100/(
float)num_nodes) <<
"% \r";
1623 for(j=0;j<alphabet.n();j++){
1626 for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next()){
1628 if(j == nodes(n_ptr)->arcs_out(a_ptr)->label){
1629 tf[i][j] = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
1660 if(start_node == NULL){
1661 start_node = nodes(nodes.head());
1662 current_symbol = input.head();
1666 if(current_symbol == NULL){
1667 if(
final(start_node) )
1676 float max=-10000000;
1677 for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
1679 if( alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
1680 == nmap_name_to_index(input(current_symbol)) ){
1682 float x = viterbi_transduce(input,
1684 current_symbol->next(),
1685 start_node->arcs_out(a_ptr)->to)
1686 + qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index);
1696 path.
append(start_node->arcs_out(best));
1703 float Lattice::viterbi_transduce(
EST_Track &observations,
1712 if(start_node == NULL){
1713 start_node = nodes(nodes.head());
1719 if(current_frame == observations.
num_frames()){
1720 if(
final(start_node) )
1729 if(score < -100000){
1734 float max=-10000000;
1735 for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
1737 int observation_element =
1738 alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
1741 float this_observation = observations.
a(current_frame,observation_element);
1746 float x = viterbi_transduce(observations,
1750 start_node->arcs_out(a_ptr)->to)
1752 + qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index)
1764 path.
append(start_node->arcs_out(best));
1766 int observation_element =
1767 alphabet_index_to_symbol(start_node->arcs_out(best)->label)->nmap_index;
1769 float this_observation = observations.
a(current_frame,observation_element);
1771 score += qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(best)->label)->qmap_index) + this_observation;
1776 cerr << max << endl;
float & a(int i, int c=0)
void clear(void)
remove all items in list
void resize(int n, int set=1)
INLINE int n() const
number of items in vector.
void append(const T &item)
add item onto end of list
int num_frames() const
return number of frames in track
void resize(int n, int set=1)
resize vector