40#include "EST_lattice.h"
58 if(nodes.head() != NULL )
59 return nodes(nodes.head());
61 cerr <<
"LAttice has no nodes !" <<
endl;
85 for (i = 0; i <
g.size(); ++i){
86 for (
j = 0;
j <
g.size(); ++
j){
127 cerr <<
"Built qmap with " << i <<
" entries" <<
endl;
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)
183 cerr <<
"Built nmap with " <<
j <<
" entries" <<
endl;
190Lattice::construct_alphabet(
Bigram &
g)
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));
255 nindex = nmap_name_to_index(
"!ENTER");
256 qindex = qmap_value_to_index(0);
285 alphabet.resize(count);
293 e_move_symbol_index = alphabet_index_lookup(-1,-1);
295 cerr <<
"Alphabet has " << count <<
" symbols " <<
endl;
326 for(i=0; i<nmap.
n(); i++){
332 if(nmap(i) ==
"!ENTER"){
334 symbol = alphabet_index_lookup(i,qmap_value_to_index(0));
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){
364 from_name = nmap_name_to_index(
"!ENTER");
369 to_name = nmap_name_to_index(
"!EXIT");
374 int name = nodes(
n_ptr)->name(nodes(
n_ptr)->name.head());
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);
420 cerr <<
"NFA has " << c1
421 <<
" nodes (" << c3 <<
" final)"
422 <<
" and " << c2 <<
" arcs" <<
endl;
428bool Lattice::determinise()
451 cerr <<
"sorting arc lists" <<
endl;
469 cerr <<
"Could not allocate any more memory";
472 new_node->name = nodes(nodes.head())->name;
489 while((
a_ptr != NULL) &&
490 (
a_ptr->next() != NULL) &&
513 cerr <<
"Could not allocate any more memory";
517 cerr <<
" after making " << count <<
" nodes" <<
endl;
542 cerr <<
"Processing node " << c
580 while((
a_ptr != NULL) &&
581 (
a_ptr->next() != NULL) &&
602 cerr <<
"Could not allocate any more memory";
606 cerr <<
" after making " << count <<
" nodes" <<
endl;
652 cerr <<
"DFA has " << c1
653 <<
" nodes (" << c3 <<
" final)"
654 <<
" and " << c2 <<
" arcs" <<
endl;
661Lattice::link(Node *
n1, Node *
n2,
int label)
671 if( (
n1==NULL) || (
n2==NULL) ){
672 cerr <<
"Can't link null nodes" <<
endl;
691Lattice::sort_arc_lists()
700 sort_by_label(nodes(
n_ptr)->arcs_out);
713Lattice::build_distinguished_state_table(
bool ** &
dst)
723 cerr <<
"Not enough memory" <<
endl;
729 cerr <<
"Not enough memory" <<
endl;
737 cerr <<
"final/non-final scan";
743 else if(!
final(nodes(
n_ptr)) &&
final(nodes(
n2_ptr)))
757 if(!build_transition_function()){
758 cerr <<
"Couldn't build transition function" <<
endl;
762 if(!build_distinguished_state_table_from_transition_function(
dst)){
763 cerr <<
"Couldn't build dst from transition function" <<
endl;
777Lattice::build_distinguished_state_table_direct(
bool ** &
dst)
805 while(
s_ptr != NULL){
810 i1 = node_index(nodes(
n_ptr)->arcs_out(
s_ptr)->to);
826 i1 = node_index(nodes(
n_ptr)->arcs_out(
a_ptr)->to);
835 if( ( (i1>=0) && (
j1>=0) &&
dst[i1][
j1]) ||
836 ( (i1>=0) && (
j1<0) ) ||
837 ( (
j1>=0) && (i1<0) ) )
861Lattice::build_distinguished_state_table_from_transition_function(
bool ** &
dst)
889 if((i2<0) && (
j2>=0)){
894 }
else if((
j2<0) && (i2>=0)){
899 }
else if( (i2>0) && (
j2>0) &&
dst[i2][
j2] ){
928 if(!build_distinguished_state_table(
dst)){
929 cerr <<
"Couldn't build distinguished state table" <<
endl;
941 cerr <<
"There are " << count <<
" undistinguished pairs of nodes and "
957 cerr <<
"merge, processing row " << i <<
" \r";
1004 cerr <<
"merging " << count <<
" nodes out of ";
1017 cerr <<
" leaving " << count <<
endl;
1032 cerr <<
"Minimum state DFA has " << c1
1033 <<
" nodes and " << c2 <<
" arcs " <<
endl;
1044 cerr <<
"Pruned minimum state DFA has " << c1
1045 <<
" nodes and " << c2 <<
" arcs" <<
endl;
1059 if(l.head() == NULL)
1098 nodes(
n2_ptr)->name.clear();
1099 nodes(
n2_ptr)->arcs_out.clear();
1110Lattice::merge_arcs()
1124 cerr <<
"merging arcs from node " << ++count
1125 <<
", before:" <<
count2;
1173Lattice::prune_arc(Node *
node, Arc *
arc)
1175 remove_arc_from_nodes_out_list(
node,
arc);
1191Lattice::remove_arc_from_nodes_out_list(Node *n, Arc *a)
1195 if(n->arcs_out(
a_ptr) == a)
1196 n->arcs_out.remove(
a_ptr);
1225Lattice::nmap_index_to_name(
int index)
1227 if(index < nmap.
n())
1230 cerr <<
"Warning : nmap index " << index <<
" out of range" <<
endl;
1237Lattice::nmap_name_to_index(
const EST_String &name)
1249 if(name > nmap(mid))
1252 else if(name < nmap(mid))
1263 cerr <<
"Lattice::nmap_name_to_index failed for '"
1264 << name <<
"'" <<
endl;
1272 else if(name == nmap(
j))
1275 cerr <<
"Lattice::nmap_name_to_index failed for '"
1276 << name <<
"'" <<
endl;
1289Lattice::qmap_index_to_value(
int index)
1291 if(index < qmap.
n())
1294 cerr <<
"Warning : qmap index " << index <<
" out of range" <<
endl;
1301Lattice::qmap_value_to_index(
float value)
1313 if(value > qmap(mid))
1316 else if(value < qmap(mid))
1327 if(
fabs(qmap(i) - value) <
fabs(qmap(
j) - value) )
1338Lattice::node_index(Node *n)
1342 if(nodes(
n_ptr) == n)
1343 return nodes.index(
n_ptr);
1377 if(nodes(
n2_ptr)->arcs_out(
a_ptr)->label != e_move_symbol_index){
1378 word = alphabet_index_to_symbol(nodes(
n2_ptr)->arcs_out(
a_ptr)->label)->nmap_index;
1398 new_arc->label = e_move_symbol_index;
1408 word = alphabet_index_to_symbol(nodes(
n2_ptr)->arcs_out(
a_ptr)->label)->nmap_index;
1447 if(final_nodes.length() > 1){
1448 cerr <<
" making single EXIT node" <<
endl;
1456 new_arc->label = e_move_symbol_index;
1464 final_nodes.clear();
1479 cerr <<
"HTKified DFA has " << c1
1480 <<
" nodes and " << c2 <<
" arcs" <<
endl;
1486Lattice::final(Node *n)
1490 if(final_nodes(
n_ptr) == n)
1503 name+=nmap_index_to_name(l(
l_ptr)) +
",";
1511Lattice::alphabet_index_lookup(
int nmap_index,
int qmap_index)
1514 sym.nmap_index = nmap_index;
1515 sym.qmap_index = qmap_index;
1517 return alphabet_symbol_to_index(&
sym);
1522Lattice::alphabet_index_to_symbol(
int index)
1524 if(index < alphabet.n())
1525 return &(alphabet[index]);
1527 cerr <<
"Warning : alphabet index " << index <<
" out of range" <<
endl;
1547 if(*
sym > alphabet(mid))
1550 else if(*
sym < alphabet(mid))
1557 if(*
sym == alphabet(i))
1560 cerr <<
"Lattice::alphabet_symbol_to_index failed for '"
1567 if(*
sym == alphabet(i))
1569 else if(*
sym == alphabet(
j))
1572 cerr <<
"Lattice::alphabet_symbol_to_index failed for '"
1575 cerr << i <<
" " << alphabet(i) <<
endl;
1591Lattice::build_transition_function()
1603 cerr <<
"Warning : discarding existing transition function" <<
endl;
1611 cerr <<
"Not enough memory to build transition function"
1618 cerr <<
"building transition function " << (int)((
float)(i+1)*100/(
float)
num_nodes) <<
"% \r";
1620 for(
j=0;
j<alphabet.n();
j++){
1626 tf[i][
j] = node_index(nodes(
n_ptr)->arcs_out(
a_ptr)->to);
1657 if(start_node == NULL){
1658 start_node = nodes(nodes.head());
1664 if(
final(start_node) )
1673 float max=-10000000;
1676 if( alphabet_index_to_symbol(start_node->arcs_out(
a_ptr)->label)->nmap_index
1679 float x = viterbi_transduce(
input,
1682 start_node->arcs_out(
a_ptr)->to)
1683 + qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(
a_ptr)->label)->qmap_index);
1693 path.append(start_node->arcs_out(
best));
1700float Lattice::viterbi_transduce(
EST_Track &observations,
1709 if(start_node == NULL){
1710 start_node = nodes(nodes.head());
1717 if(
final(start_node) )
1726 if(score < -100000){
1731 float max=-10000000;
1735 alphabet_index_to_symbol(start_node->arcs_out(
a_ptr)->label)->nmap_index
1743 float x = viterbi_transduce(observations,
1747 start_node->arcs_out(
a_ptr)->to)
1749 + qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(
a_ptr)->label)->qmap_index)
1761 path.append(start_node->arcs_out(
best));
1764 alphabet_index_to_symbol(start_node->arcs_out(
best)->label)->nmap_index;
1768 score += qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(
best)->label)->qmap_index) +
this_observation;
void resize(int n, int set=1)
resize vector
void resize(int n, int set=1)
INLINE int n() const
number of items in vector.
float & a(int i, int c=0)
int num_frames() const
return number of frames in track